Java十大經(jīng)典排序算法的實現(xiàn)圖解
前言
本文章主要是講解我個人在學習Java開發(fā)環(huán)境的排序算法時做的一些準備，以及個人的心得體會，匯集成本篇文章，作為自己對排序算法理解的總結(jié)與筆記。
內(nèi)容主要是關于十大經(jīng)典排序算法的簡介、原理、動靜態(tài)圖解和源碼實現(xiàn)的分析。
對于一名程序員來講，我們都知道數(shù)據(jù)結(jié)構(gòu)與算法起初是用于C語言居多，然而在Java語言下使用算法的案例卻很少，因此，特別整理了在Java開發(fā)環(huán)境的排序算法，供大家一起學習探討。
一、排序算法
1.排序算法概述（百度百科）
所謂排序算法，即通過特定的算法因式將一組或多組數(shù)據(jù)按照既定模式進行重新排序。這種新序列遵循著一定的規(guī)則，體現(xiàn)出一定的規(guī)律，因此，經(jīng)處理后的數(shù)據(jù)便于篩選和計算，大大提高了計算效率。對于排序，我們首先要求其具有一定的穩(wěn)定性，即當兩個相同的元素同時出現(xiàn)于某個序列之中，則經(jīng)過一定的排序算法之后，兩者在排序前后的相對位置不發(fā)生變化。換言之，即便是兩個完全相同的元素，它們在排序過程中也是各有區(qū)別的，不允許混淆不清。
2.《數(shù)據(jù)結(jié)構(gòu)與算法》中的排序算法
常見的排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。
算法圖解（菜鳥教程借圖）：
圖解分析：
3.算法分析
時間復雜度
平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。
線性對數(shù)階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之間的常數(shù)。 希爾排序
線性階 (O(n)) 排序 基數(shù)排序，此外還有桶、箱排序。
關于穩(wěn)定性
穩(wěn)定的排序算法：冒泡排序、插入排序、歸并排序和基數(shù)排序。
不是穩(wěn)定的排序算法：選擇排序、快速排序、希爾排序、堆排序。
名詞解釋：
- n：數(shù)據(jù)規(guī)模
- k："桶"的個數(shù)
- In-place：占用常數(shù)內(nèi)存，不占用額外內(nèi)存
- Out-place：占用額外內(nèi)存
- 穩(wěn)定性：排序后 2 個相等鍵值的順序和排序之前它們的順序相同
平均時間復雜度是指所有可能的輸入實例均以等概率的出現(xiàn)情況下得到算法的運行時間
最壞時間復雜度，一般討論的時間復雜度均是最壞情況下的時間復雜度，這樣做的原因是最壞情況下的時間復雜度是算法在任何輸入實例上運行的界限，這就保證了算法的運行時間不會比最壞情況更長。
平均時間復雜度和最壞時間復雜度是否一樣，這就需要根據(jù)算法不同而不同了。
二、十大經(jīng)典排序算法（Java開發(fā)版）
PS：案例均以數(shù)組{15，63，97，12，235，66}排序為例
1.冒泡排序
冒泡排序（Bubble Sort），是一種計算機科學領域的較簡單的排序算法。
它重復地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果順序（如從大到小、首字母從Z到A）錯誤就把他們交換過來。走訪元素的工作是重復地進行直到?jīng)]有相鄰元素需要交換，也就是說該元素列已經(jīng)排序完成。
這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。
1.1實現(xiàn)原理
- 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
- 對每一對相鄰元素做同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應該會是最大的數(shù)。
- 針對所有的元素重復以上的步驟，除了最后一個。
- 持續(xù)每次對越來越少的元素重復上面的步驟，直到?jīng)]有任何一對數(shù)字需要比較。
1.2動圖演示
1.3實例展示
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arrays =new int[]{15,63,97,12,235,66};
for (int i=0;i<arrays.length-1;i++){
// 控制比較次數(shù),三者交換，實現(xiàn)排序
for(int j=0;j<arrays.length-1-i;j++){
if (arrays[j] > arrays[j+1]){
int temp = 0;//類似空桶
temp = arrays[j]; //A桶中水倒入空桶C中
arrays[j] = arrays[j+1];//把B桶的水倒入A桶中
arrays[j+1] = temp;//把C桶的水倒入B桶中
}
}
}
System.out.println(Arrays.toString(arrays));
}
}排序結(jié)果展示：
2.快速排序
快速排序（Quicksort），計算機科學詞匯，適用領域Pascal，c++等語言，是對冒泡排序算法的一種改進。
2.1實現(xiàn)原理
快速排序是對冒泡排序的一種改進。通過一趟排序?qū)⒁判虻臄?shù)據(jù)分割成獨立的兩部分，其中一部分的所有數(shù)據(jù)都比另一部分所有的數(shù)據(jù)都要小，然后再按此方法對這兩部分數(shù)據(jù)分別進行快速排序，整個排序過程可以遞歸進行，以此達到整個數(shù)據(jù)變成有序序列
2.2 動圖演示
2.3實例展示
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arrays = new int[]{15,63,97,12,235,66};
sort(arrays,0,arrays.length-1);
System.out.println(Arrays.toString(arrays));
}
public static void sort(int[] arrays,int left,int right){
int l = left;
int r = right;
int pivot = arrays[(left+right)/2];
int temp = 0;
while (l<r){
//在左邊查找小于中間值的
while(arrays[l]<pivot){
l++;
}
//查詢右邊小于中間值
while (arrays[r]>pivot){
r--;
}
if (l>=r){
break;
}
temp = arrays[l];
arrays[l] = arrays[r];
arrays[r] = temp;
// 交換完數(shù)據(jù)arrays[l] = pivot
if (arrays[l]==pivot){
r--;
}
if (arrays[r]==pivot){
l++;
}
if (r==l){
l++;
r--;
}
if (left<r){
sort(arrays,left,r);
}
if (right>l){
sort(arrays,l,right);
}
}
}
}排序結(jié)果展示：
3.基數(shù)排序
基數(shù)排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或bin sort，顧名思義，它是透過鍵值的部份資訊，將要排序的元素分配至某些“桶”中，藉以達到排序的作用，基數(shù)排序法是屬于穩(wěn)定性的排序，其時間復雜度為O (nlog(r)m)，其中r為所采取的基數(shù)，而m為堆數(shù)，在某些時候，基數(shù)排序法的效率高于其它的穩(wěn)定性排序法。
基數(shù)排序是1887年赫爾曼、何樂禮發(fā)明的。思想是講整數(shù)按位數(shù)切割成不同的數(shù)字，然后按每個位數(shù)分別比較。
3.1實現(xiàn)原理
講所有的待比較數(shù)值統(tǒng)一設置為同樣的數(shù)位長度，位數(shù)比較短的數(shù)前面補零，然后從最地位開始依次進行一次排序，這樣從最低位排序一直到最高位排序完成以后，數(shù)列就變成一個有序序列。
3.2 動圖演示
3.3實例展示
import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;
public class BasicSort {
public static void main(String[] args) {
int[] arrays = new int[]{15,63,97,12,235,66};
SimpleDateFormat simpleDateFormat =new SimpleDateFormat("yyyy-mm-dd HH:MM:ss:SS");
System.out.println("開始排序前:"+simpleDateFormat.format(new Date()));
sort(arrays);
System.out.println("排序結(jié)束:"+simpleDateFormat.format(new Date()));
}
// 1.獲取原序列的最大位多少
// @param arrays
public static void sort(int[] arrays){
// 獲取最大位數(shù)
int max = 0;
for(int i=0;i<arrays.length;i++){
if (arrays[i]>max){
max = arrays[i];
}
}
// 獲取字符串長度，所以把int類型轉(zhuǎn)字符串類型
int maxLength = (max+"").length();
// 定義二維數(shù)組，大小10，表示10個桶，每一個桶則是一個數(shù)組
// [[],[],[],[],[]...]
int[][] bucket = new int[10][arrays.length];
// 輔助數(shù)組
int[] bucketElementCount = new int[10];
// 循環(huán)獲取無序數(shù)列
for (int j=0;j<arrays.length;j++){
int locationElement = arrays[j]%10;
// 放入桶中
bucket[locationElement][bucketElementCount[locationElement]] = arrays[j] ;
bucketElementCount[locationElement]++;
}
// 遍歷每一個桶，講元素存放原數(shù)組中
int index = 0;
for (int k = 0;k<bucketElementCount.length;k++){
if (bucketElementCount[k] !=0){
for (int l = 0;l<bucketElementCount[k];l++){
arrays[index++] = bucket[k][l];
}
}
bucketElementCount[k] = 0;
}
System.out.println(Arrays.toString(arrays));
// 第一輪針對個位數(shù)進行比較
for (int j = 0;j<arrays.length;j++){
int locationElement = arrays[j]/1%10;
bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
bucketElementCount[locationElement]++;
}
// 取出來按照桶的順序放回原數(shù)組中
int indx = 0;
for (int k = 0;k<bucketElementCount.length;k++){
if (bucketElementCount[k] !=0){
for (int l=0;l<bucketElementCount[k];l++){
arrays[indx++] = bucket[k][l];
}
}
bucketElementCount[k] = 0;
}
// 判斷十位數(shù)
for (int j = 0;j<arrays.length;j++){
int locationElement = arrays[j]/10%10;
bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
bucketElementCount[locationElement]++;
}
// 取出來按照桶的順序放回原數(shù)組中
indx = 0;
for (int k = 0;k<bucketElementCount.length;k++){
if (bucketElementCount[k] !=0){
for (int l=0;l<bucketElementCount[k];l++){
arrays[indx++] = bucket[k][l];
}
}
bucketElementCount[k] = 0;
}
// 獲取百位數(shù)比較
for (int j = 0;j<arrays.length;j++){
int locationElement = arrays[j]/100%10;
bucket[locationElement][bucketElementCount[locationElement]] = arrays[j];
bucketElementCount[locationElement]++;
}
// 取出來按照桶的順序放回原數(shù)組中
indx = 0;
for (int k = 0;k<bucketElementCount.length;k++){
if (bucketElementCount[k] !=0){
for (int l=0;l<bucketElementCount[k];l++){
arrays[indx++] = bucket[k][l];
}
}
bucketElementCount[k] = 0;
}
System.out.println("基數(shù)排序后的順序:"+Arrays.toString(arrays));
}
}排序結(jié)果展示：
4.插入排序
插入排序，一般也被稱為直接插入排序。對于少量元素的排序，它是一個有效的算法 。插入排序是一種最簡單的排序方法，它的基本思想是將一個記錄插入到已經(jīng)排好序的有序表中，從而一個新的、記錄數(shù)增1的有序表。在其實現(xiàn)過程使用雙層循環(huán)，外層循環(huán)對除了第一個元素之外的所有元素，內(nèi)層循環(huán)對當前元素前面有序表進行待插入位置查找，并進行移動 。
4.1實現(xiàn)原理
插入排序的工作方式像許多人排序一手撲克牌。開始時，我們的左手為空并且桌子上的牌面向下。然后，我們每次從桌子上拿走一張牌并將它插入左手中正確的位置。為了找到一張牌的正確位置，我們從右到左將它與已在手中的每張牌進行比較。拿在左手上的牌總是排序好的，原來這些牌是桌子上牌堆中頂部的牌。
插入排序是指在待排序的元素中，假設前面n-1(其中n>=2)個數(shù)已經(jīng)是排好順序的，現(xiàn)將第n個數(shù)插到前面已經(jīng)排好的序列中，然后找到合適自己的位置，使得插入第n個數(shù)的這個序列也是排好順序的。按照此法對所有元素進行插入，直到整個序列排為有序的過程，稱為插入排序。
4.2 動圖演示
4.3實例展示
public class InsertSort {
public static void main(String[] args) {
int[] array = new int[]{15,63,97,12,235,66};
//控制拿去每一個元素
for(int i=1;i<array.length;i++){
//比較次數(shù)
for (int j=i;j>=1;j--){
//是否小于前面的元素
if (array[j]<array[j-1]){
int temp = 0;
temp = array[j];
array[j] = array[j-1];
array[j-1] = temp;
}else {
//continue 與 break
break;
}
}
}
System.out.println("排序后的結(jié)果："+ Arrays.toString(array));
}
}排序結(jié)果展示：
5.選擇排序
選擇排序（Selection sort）是一種簡單直觀的排序算法。它的工作原理是：第一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小（大）元素，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素的個數(shù)為零。選擇排序是不穩(wěn)定的排序方法。
5.1實現(xiàn)原理
第一次從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小（大）元素，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數(shù)據(jù)元素的個數(shù)為零。選擇排序是不穩(wěn)定的排序方法。
5.2 動圖演示
5.3實例展示
import java.util.Arrays;
public class SelectSort {
public static void main(String[] args) {
int[] arr = new int[]{15,63,97,12,235,66};
for (int i=0;i<arr.length;i++){
for (int j=arr.length-1;j>i;j--){
if (arr[j]<arr[i]){
int temp = 0;
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
}
}
}
System.out.println("選擇排序后的結(jié)果:"+ Arrays.toString(arr));
}
}排序結(jié)果展示：
6.希爾排序
希爾排序(Shell's Sort)是插入排序的一種又稱“縮小增量排序”（Diminishing Increment Sort），是插入排序算法的一種更高效的改進版本。希爾排序是非穩(wěn)定排序算法。該方法因 D.L.Shell 于 1959 年提出而得名。
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至 1 時，整個文件恰被分成一組，算法便終止。
6.1實現(xiàn)原理
先取一個小于n的整數(shù)d1作為第一個增量，把文件的全部記錄分組。所有距離為d1的倍數(shù)的記錄放在同一個組中。先在各組內(nèi)進行直接插入排序；然后，取第二個增量d2
般的初次取序列的一半為增量，以后每次減半，直到增量為1。
6.2 動圖演示
6.3實例展示
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int[] array = new int[]{15,63,97,12,235,66};
// 實現(xiàn)增量變化
for (int gap = array.length/2;gap>0;gap/=2){
for (int i=gap;i<array.length;i++){
for (int j=i-gap;j>=0;j-=gap){
if (array[j]>array[j+gap]){
int temp = 0;
temp = array[j];
array[j] = array[j+gap];
array[j+gap] = temp;
}
}
}
}
System.out.println(Arrays.toString(array));
}
}排序結(jié)果展示：
7.歸并排序
歸并排序（Merge Sort）是建立在歸并操作上的一種有效，穩(wěn)定的排序算法，該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
7.1實現(xiàn)原理
- 第一步：申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
- 第二步：設定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
- 第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置重復步驟3直到某一指針超出序列尾將另一序列剩下的所有元素直接復制到合并序列尾
我們需要將兩個已經(jīng)有序的子序列合并成一個有序序列，比如上圖最后一次合并，將[2,4,5,6]和[1,3,7,8]已經(jīng)有序的子序列合并最終序列[1,2,3,4,5,6,7,8]
7.2 動圖演示
7.3實例展示
import java.util.Arrays;
public class MSort {
public static void main(String[] args) {
int[] array = new int[]{15,63,97,12,235,66};
//臨時數(shù)組
int[] temp = new int[array.length];
sort(array,0,array.length-1,temp);
System.out.println(Arrays.toString(array));
}
public static void sort(int[] array,int left,int right,int[] temp){
if (left<right){
// 求出中間值
int mid = (left+right)/2;
// 向左邊分解
sort(array,left,mid,temp);
// 向右邊分解
sort(array,mid+1,right,temp);
// 合并數(shù)據(jù)
sum(array,left,right,mid,temp);
}
}
/**
* 合并元素
* @param array
* @param left
* @param right
* @param mid
* @param temp
*/
public static void sum(int[] array,int left,int right,int mid,int[] temp){
int i = left;
int j = mid+1;
// 指向臨時數(shù)組下標
int t = 0;
// 開始循環(huán)比較左右兩遍數(shù)組元素比較
while (i<=mid && j<=right){
if (array[i]<=array[j]){
temp[t] = array[i];
t++;
i++;
}else {
temp[t] = array[j];
t++;
j++;
}
}
// 把剩余的元素直接存放在臨時數(shù)組中
while(i<=mid){
temp[t] = array[i];
t++;
i++;
}
while (j<=right){
temp[t] = array[j];
t++;
j++;
}
// 臨時數(shù)組中的元素拷貝至原數(shù)組中
int tempIndex = left;
int k = 0;
while (tempIndex<=right){
array[tempIndex] = temp[k];
k++;
tempIndex++;
}
}
75 }排序結(jié)果展示：
8.計數(shù)排序
計數(shù)排序是一個非基于比較的排序算法，該算法于1954年由 Harold H. Seward 提出。它的優(yōu)勢在于在對一定范圍內(nèi)的整數(shù)排序時，它的復雜度為Ο(n+k)（其中k是整數(shù)的范圍），快于任何比較排序算法。 當然這是一種犧牲空間換取時間的做法，而且當O(k)>O(n*log(n))的時候其效率反而不如基于比較的排序（基于比較的排序的時間復雜度在理論上的下限是O(n*log(n)), 如歸并排序，堆排序）
8.1實現(xiàn)原理
假設輸入的線性表L的長度為n，L=L1,L2,..,Ln；線性表的元素屬于有限偏序集S，|S|=k且k=O(n)，S={S1,S2,..Sk}；則計數(shù)排序可以描述如下：
- 掃描整個集合S，對每一個Si∈S，找到在線性表L中小于等于Si的元素的個數(shù)T(Si)；
- 掃描整個線性表L，對L中的每一個元素Li，將Li放在輸出線性表的第T(Li)個位置上，并將T(Li)減1。
8.2 動圖演示
8.3實例展示
public class CountSort {
public static void main(String[]args){
//排序的數(shù)組
int a[]={15,63,97,12,235,66};
int b[]=countSort(a);
for(int i:b){
System.out.print( i+",");
}
System.out.println();
}
public static int[] countSort(int[]a){
int b[] = new int[a.length];
int max = a[0],min = a[0];
for(int i:a){
if(i>max){
max=i;
}
if(i<min){
min=i;
}
}//這里k的大小是要排序的數(shù)組中，元素大小的極值差+1
int k=max-min+1;
int c[]=new int[k];
for(int i=0;i<a.length;++i){
c[a[i]-min]+=1;//優(yōu)化過的地方，減小了數(shù)組c的大小
}
for(int i=1;i<c.length;++i){
c[i]=c[i]+c[i-1];
}
for(int i=a.length-1;i>=0;--i){
b[--c[a[i]-min]]=a[i];//按存取的方式取出c的元素
}
return b;
}
}排序結(jié)果展示：
9.堆排序
堆排序（英語:Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設計的一種排序算法。堆是一個近似完全二叉樹的結(jié)構(gòu)，并同時滿足堆積的性質(zhì)：即子結(jié)點的鍵值或索引總是小于（或者大于）它的父節(jié)點。
9.1實現(xiàn)原理
- 創(chuàng)建一個堆 H[0……n-1]；
- 把堆首（最大值）和堆尾互換；
- 把堆的尺寸縮小 1，并調(diào)用 shift_down(0)，目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應位置；
- 重復步驟 2，直到堆的尺寸為 1。
9.2 動圖演示
9.3實例展示
public static int[] heapSort(int[] array) {
//這里元素的索引是從0開始的,所以最后一個非葉子結(jié)點array.length/2 - 1
for (int i = array.length / 2 - 1; i >= 0; i--) {
adjustHeap(array, i, array.length); //調(diào)整堆
}
// 上述邏輯，建堆結(jié)束
// 下面，開始排序邏輯
for (int j = array.length - 1; j > 0; j--) {
// 元素交換,作用是去掉大頂堆
// 把大頂堆的根元素，放到數(shù)組的最后；換句話說，就是每一次的堆調(diào)整之后，都會有一個元素到達自己的最終位置
swap(array, 0, j);
// 元素交換之后，毫無疑問，最后一個元素無需再考慮排序問題了。
// 接下來我們需要排序的，就是已經(jīng)去掉了部分元素的堆了，這也是為什么此方法放在循環(huán)里的原因
// 而這里，實質(zhì)上是自上而下，自左向右進行調(diào)整的
adjustHeap(array, 0, j);
}
return array;
}
/**
* 整個堆排序最關鍵的地方
* @param array 待組堆
* @param i 起始結(jié)點
* @param length 堆的長度
*/
public static void adjustHeap(int[] array, int i, int length) {
// 先把當前元素取出來，因為當前元素可能要一直移動
int temp = array[i];
for (int k = 2 * i + 1; k < length; k = 2 * k + 1) { //2*i+1為左子樹i的左子樹(因為i是從0開始的),2*k+1為k的左子樹
// 讓k先指向子節(jié)點中最大的節(jié)點
if (k + 1 < length && array[k] < array[k + 1]) { //如果有右子樹,并且右子樹大于左子樹
k++;
}
//如果發(fā)現(xiàn)結(jié)點(左右子結(jié)點)大于根結(jié)點，則進行值的交換
if (array[k] > temp) {
swap(array, i, k);
// 如果子節(jié)點更換了，那么，以子節(jié)點為根的子樹會受到影響,所以，循環(huán)對子節(jié)點所在的樹繼續(xù)進行判斷
i = k;
} else { //不用交換，直接終止循環(huán)
break;
}
}
}
/**
* 交換元素
* @param arr
* @param a 元素的下標
* @param b 元素的下標
*/
public static void swap(int[] arr, int a, int b) {
int temp = arr[a];
arr[a] = arr[b];
arr[b] = temp;
}排序結(jié)果展示：
10.桶排序
桶排序 (Bucket sort)或所謂的箱排序，是一個排序算法，工作的原理是將數(shù)組分到有限數(shù)量的桶子里。每個桶子再個別排序（有可能再使用別的排序算法或是以遞歸方式繼續(xù)使用桶排序進行排序）。桶排序是鴿巢排序的一種歸納結(jié)果。當要被排序的數(shù)組內(nèi)的數(shù)值是均勻分配的時候，桶排序使用線性時間（Θ（n））。但桶排序并不是 比較排序，他不受到 O(n log n) 下限的影響。
10.1實現(xiàn)原理
假定：輸入是由一個隨機過程產(chǎn)生的[0, 1)區(qū)間上均勻分布的實數(shù)。將區(qū)間[0, 1)劃分為n個大小相等的子區(qū)間（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…將n個輸入元素分配到這些桶中，對桶中元素進行排序，然后依次連接桶輸入0 ≤A[1..n] <1輔助數(shù)組B[0..n-1]是一指針數(shù)組，指向桶（鏈表）。
10.2 動圖演示
然后，元素在每個桶中排序：
10.3實例展示
public static void basket(int data[])//data為待排序數(shù)組
{
int n=data.length;
int bask[][]=new int[10][n];
int index[]=new int[10];
int max=Integer.MIN_VALUE;
for(int i=0;i<n;i++)
{
max=max>(Integer.toString(data[i]).length())?max:(Integer.toString(data[i]).length());
}
String str;
for(int i=max-1;i>=0;i--)
{
for(int j=0;j<n;j++)
{
str="";
if(Integer.toString(data[j]).length()<max)
{
for(int k=0;k<max-Integer.toString(data[j]).length();k++)
str+="0";
}
str+=Integer.toString(data[j]);
bask[str.charAt(i)-'0'][index[str.charAt(i)-'0']++]=data[j];
}
int pos=0;
for(int j=0;j<10;j++)
{
for(int k=0;k<index[j];k++)
{
data[pos++]=bask[j][k];
}
}
for(intx=0;x<10;x++)index[x]=0;
}
}排序結(jié)果展示：
以上就是Java十大經(jīng)典排序算法的實現(xiàn)圖解的詳細內(nèi)容，更多關于Java排序算法的資料請關注腳本之家其它相關文章！
相關文章
今天小編就為大家分享一篇關于Java算法之串的簡單處理，小編覺得內(nèi)容挺不錯的，現(xiàn)在分享給大家，具有很好的參考價值，需要的朋友一起跟隨小編來看看吧2019-03-03
這篇文章主要介紹了Java 遍歷 String 字符串所有字符的操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-10-10
這篇文章主要介紹了Java二維數(shù)組查找功能代碼實現(xiàn),文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-06-06
這篇文章主要介紹了MyBatis-Plus代碼生成器的使用詳解，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-11-11
這篇文章主要為大家介紹了Netty實戰(zhàn)源碼解析NIO編程的核心組件及關系詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-12-12
java實現(xiàn)多線程的兩種方式繼承Thread類和實現(xiàn)Runnable接口的方法
下面小編就為大家?guī)硪黄猨ava實現(xiàn)多線程的兩種方式繼承Thread類和實現(xiàn)Runnable接口的方法。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-09-09
這篇文章主要為大家詳細介紹了OPENCV+JAVA實現(xiàn)人臉識別，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-02-02
詳解Java是如何通過接口來創(chuàng)建代理并進行http請求
今天給大家?guī)淼闹R是關于Java的,文章圍繞Java是如何通過接口來創(chuàng)建代理并進行http請求展開,文中有非常詳細的介紹及代碼示例,需要的朋友可以參考下2021-06-06
這篇文章主要介紹了IDEA代碼規(guī)范插件P3C+代碼注釋模板配置方法,本文通過圖文并茂的形式給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-01-01
SpringBoot Mybatis如何配置多數(shù)據(jù)源并分包
這篇文章主要介紹了SpringBoot Mybatis如何配置多數(shù)據(jù)源并分包,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-05-05