Java十大經(jīng)典排序算法的實現(xiàn)圖解
前言
本文章主要是講解我個人在學(xué)習(xí)Java開發(fā)環(huán)境的排序算法時做的一些準備，以及個人的心得體會，匯集成本篇文章，作為自己對排序算法理解的總結(jié)與筆記。
內(nèi)容主要是關(guān)于十大經(jīng)典排序算法的簡介、原理、動靜態(tài)圖解和源碼實現(xiàn)的分析。
對于一名程序員來講，我們都知道數(shù)據(jù)結(jié)構(gòu)與算法起初是用于C語言居多，然而在Java語言下使用算法的案例卻很少，因此，特別整理了在Java開發(fā)環(huán)境的排序算法，供大家一起學(xué)習(xí)探討。
一、排序算法
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.算法分析
時間復(fù)雜度
平方階 (O(n2)) 排序 各類簡單排序：直接插入、直接選擇和冒泡排序。
線性對數(shù)階 (O(nlog2n)) 排序 快速排序、堆排序和歸并排序；
O(n1+§)) 排序，§ 是介于 0 和 1 之間的常數(shù)。 希爾排序
線性階 (O(n)) 排序 基數(shù)排序，此外還有桶、箱排序。
關(guān)于穩(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 個相等鍵值的順序和排序之前它們的順序相同
平均時間復(fù)雜度是指所有可能的輸入實例均以等概率的出現(xiàn)情況下得到算法的運行時間
最壞時間復(fù)雜度，一般討論的時間復(fù)雜度均是最壞情況下的時間復(fù)雜度，這樣做的原因是最壞情況下的時間復(fù)雜度是算法在任何輸入實例上運行的界限，這就保證了算法的運行時間不會比最壞情況更長。
平均時間復(fù)雜度和最壞時間復(fù)雜度是否一樣，這就需要根據(jù)算法不同而不同了。
二、十大經(jīng)典排序算法（Java開發(fā)版）
PS：案例均以數(shù)組{15，63，97，12，235，66}排序為例
1.冒泡排序
冒泡排序（Bubble Sort），是一種計算機科學(xué)領(lǐng)域的較簡單的排序算法。
它重復(fù)地走訪過要排序的元素列，依次比較兩個相鄰的元素，如果順序（如從大到小、首字母從Z到A）錯誤就把他們交換過來。走訪元素的工作是重復(fù)地進行直到?jīng)]有相鄰元素需要交換，也就是說該元素列已經(jīng)排序完成。
這個算法的名字由來是因為越小的元素會經(jīng)由交換慢慢“浮”到數(shù)列的頂端（升序或降序排列），就如同碳酸飲料中二氧化碳的氣泡最終會上浮到頂端一樣，故名“冒泡排序”。
1.1實現(xiàn)原理
- 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
- 對每一對相鄰元素做同樣的工作，從開始第一對到結(jié)尾的最后一對。在這一點，最后的元素應(yīng)該會是最大的數(shù)。
- 針對所有的元素重復(fù)以上的步驟，除了最后一個。
- 持續(xù)每次對越來越少的元素重復(fù)上面的步驟，直到?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），計算機科學(xué)詞匯，適用領(lǐng)域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)定性的排序，其時間復(fù)雜度為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ù)前面補零，然后從最地位開始依次進行一次排序，這樣從最低位排序一直到最高位排序完成以后，數(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)原理
插入排序的工作方式像許多人排序一手撲克牌。開始時，我們的左手為空并且桌子上的牌面向下。然后，我們每次從桌子上拿走一張牌并將它插入左手中正確的位置。為了找到一張牌的正確位置，我們從右到左將它與已在手中的每張牌進行比較。拿在左手上的牌總是排序好的，原來這些牌是桌子上牌堆中頂部的牌。
插入排序是指在待排序的元素中，假設(shè)前面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 年提出而得名。
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當增量減至 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）的一個非常典型的應(yīng)用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
7.1實現(xiàn)原理
- 第一步：申請空間，使其大小為兩個已經(jīng)排序序列之和，該空間用來存放合并后的序列
- 第二步：設(shè)定兩個指針，最初位置分別為兩個已經(jīng)排序序列的起始位置
- 第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置重復(fù)步驟3直到某一指針超出序列尾將另一序列剩下的所有元素直接復(fù)制到合并序列尾
我們需要將兩個已經(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ù)排序時，它的復(fù)雜度為Ο(n+k)（其中k是整數(shù)的范圍），快于任何比較排序算法。 當然這是一種犧牲空間換取時間的做法，而且當O(k)>O(n*log(n))的時候其效率反而不如基于比較的排序（基于比較的排序的時間復(fù)雜度在理論上的下限是O(n*log(n)), 如歸并排序，堆排序）
8.1實現(xiàn)原理
假設(shè)輸入的線性表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)所設(shè)計的一種排序算法。堆是一個近似完全二叉樹的結(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)整到相應(yīng)位置；
- 重復(fù)步驟 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;
}
/**
* 整個堆排序最關(guān)鍵的地方
* @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)容，更多關(guān)于Java排序算法的資料請關(guān)注腳本之家其它相關(guān)文章！
相關(guān)文章
java常用工具類 Random隨機數(shù)、MD5加密工具類
這篇文章主要為大家詳細介紹了Java常用工具類，Random隨機數(shù)工具類、MD5加密工具類，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-05-05
不喜歡羅里吧嗦，講的很精簡易懂。從基礎(chǔ)開始講，后續(xù)會講到JAVA高級，中間會穿插面試題和項目實戰(zhàn)，希望能給大家?guī)韼椭?/div> 2022-03-03
基于Java的打包jar、war、ear包的作用與區(qū)別詳解
本篇文章，小編為大家介紹，基于Java的打包jar、war、ear包的作用與區(qū)別詳解。需要的朋友參考下2013-04-04
使用Spring Expression Language (SpEL)全面解析表達式
這篇文章主要介紹了使用Spring Expression Language (SpEL)全面解析表達式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-02-02
Springboot 中使用 Aop代碼實戰(zhàn)教程
AOP的編程思想是把對類對象的橫切問題點，從業(yè)務(wù)邏輯中分離出來，從而達到解耦的目的，增加代碼的復(fù)用性，提高開發(fā)效率，這篇文章主要介紹了Springboot中使用Aop代碼實戰(zhàn)教程，需要的朋友可以參考下2023-07-07
springboot~nexus項目打包要注意的地方示例代碼詳解
這篇文章主要介紹了springboot~nexus項目打包要注意的地方,本文通過實例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-07-07
Java通過匿名類來實現(xiàn)回調(diào)函數(shù)實例總結(jié)
這篇文章主要介紹了Java通過匿名類來實現(xiàn)回調(diào)函數(shù)的例子，回調(diào)函數(shù)就是一種函數(shù)簽名（若干個輸入?yún)?shù)、一個輸出參數(shù)）的規(guī)范，java雖不存在函數(shù)聲明，但是java可以用接口來強制規(guī)范。具體操作步驟大家可查看下文的詳細講解，感興趣的小伙伴們可以參考一下。2017-08-08
equals方法是java.lang.Object類的方法,下面這篇文章主要給大家介紹了關(guān)于Java中equals()方法的相關(guān)資料,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2021-12-12
JDBC（Java Database Connectivity），即Java數(shù)據(jù)庫連接，是一種用于執(zhí)行SQL語句的Java API，可以為多種關(guān)系數(shù)據(jù)庫提供同一訪問，它由一組用Java語言編寫的類和接口組成。2017-05-05
Intellj Idea中的maven工程Java文件顏色不對,未被識別的解決
這篇文章主要介紹了Intellj Idea中的maven工程Java文件顏色不對,未被識別的解決，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-08-08最新評論