数据结构与算法【Java】05---排序算法总结
前言
數據 data 結構(structure)是一門 研究組織數據方式的學科，有了編程語言也就有了數據結構.學好數據結構才可以編寫出更加漂亮,更加有效率的代碼。
- 要學習好數據結構就要多多考慮如何將生活中遇到的問題,用程序去實現解決.
- 程序 = 數據結構 + 算法
- 數據結構是算法的基礎, 換言之，想要學好算法，需要把數據結構學到位
數據結構與算法【Java】05---排序算法
1、排序算法介紹
- 排序也稱排序算法(SortAlgorithm)，排序是將?一組數據?，依?指定的順序?進行?排列?的過程
- 有很多種不同的排序算法，每一種都有各自的優勢和限制
- 下面我們會一一分析不同種的排序算法并比較他們之間的區別
2、排序的分類
內部排序:
指將需要處理的所有數據都加載到 內部存儲器( 內存)中進行排序。
外部排序法：
數據量過大，無法全部加載到內存中，需要借助 外部存儲( 文件等)進行排序。
3、算法的時間復雜度
3.1、度量一個程序(算法)執行時間的兩種方法
- 事后統計：實際運行程序統計時間，但是容易受計算機的軟硬件環境影響
- 事前統計：分析時間復雜度
3.2、時間頻度
-
介紹：一個算法中的語句執行次數稱為語句頻度或時間頻度。記為 T(n)
-
舉例說明：
1、比如計算1-100所有數字之和, 我們設計兩種算法：
（1）T(n)=n+1
? （2）?T(n)=1
?2、時間頻度的表示
? （1）忽略常數項
? 結論:
? 2n+20 和 2n 隨著n 變大，執行曲線無限接近, 20可以忽略
? 3n+10 和 3n 隨著n 變大，執行曲線無限接近, 10可以忽略
? （2）忽略低次項
? 結論:
? 2n^2+3n+10 和 2n^2 隨著n 變大, 執行曲線無限接近, 可以忽略 3n+10
? n^2+5n+20 和 n^2 隨著n 變大,執行曲線無限接近, 可以忽略 5n+20
? （3）忽略系數
? 結論:
? 隨著n值變大，5n^2+7n 和 3n^2 + 2n ，執行曲線重合, 說明 這種情況下, 5和3可以忽略。
? 而n^3+5n 和 6n^3+4n ，執行曲線分離，說明多少次方式關鍵
3.3、時間復雜度
?
.一般情況下， 算法中的基本操作語句的重復執行次數是問題規模 n 的某個函數，用 T(n)表示，若有某個輔助函數 f(n)，使得當 n 趨近于無窮大時，T(n) / f(n) 的極限值為不等于零的常數，則稱 f(n)是 T(n)的同數量級函數。
記作 T(n)= Ｏ( f(n) )，稱Ｏ( f(n) ) 為算法的漸進時間復雜度，簡稱時間復雜度。
度相同，都為 O(n2 )。
（1） 用常數 1 代替運行時間中的所有加法常數 T(n)=n2+7n+6 => T(n)=n2+7n+1
（2）修改后的運行次數函數中，只保留最高階項 T(n)=n2+7n+1 => T(n) = n2
（3）去除最高階項的系數 T(n) = n2 => T(n) = n2 => O(n2)
3.4、常見的時間復雜度
說明：
- 常見的算法時間復雜度由小到大依次為：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(nk) ＜Ο(2n) ，隨著問題規模n的不斷增大，上述時間復雜度不斷增大，算法的執行效率越低
- 從圖中可見，我們應該盡可能避免使用指數階的算法
舉例說明
1.常數階O(1)
無論代碼執行了多少行，只要是沒有循環等復雜結構，那這個代碼的時間復雜度就都是O(1)
上述代碼在執行的時候，它消耗的時候并不隨著某個變量的增長而增長，那么無論這類代碼有多長，即使有幾萬幾十萬行，都可以用O(1)來表示它的時間復雜度
2.對數階O(log2n)
在while循環里面，每次都將?i?乘以 2，乘完之后，?i?距離 n 就越來越近了。假設循環x次之后，?i?就大于 2 了，此時這個循環就退出了，也就是說 2 的 x 次方等于 n，那么 x = log2n也就是說當循環 log2n 次以后，這個代碼就結束了。
因此這個代碼的時間復雜度為：O(log2n) 。 O(log2n) 的這個2 時間上是根據代碼變化的，?i?=?i?* 3 ，則是 O(log3n) .
3.線性階O(n)
這段代碼，for循環里面的代碼會執行n遍，因此它消耗的時間是隨著n的變化而變化的，因此這類代碼都可以用O(n)來表示它的時間復雜度
4.線性對數階O(nlog2n)
線性對數階O(nlogN) 其實非常容易理解，將時間復雜度為O(logn)的代碼循環N遍的話，那么它的時間復雜度就是 n * O(logN)，也就是了O(nlogN)
5.平方階O(n^2)
平方階O(n2) 就更容易理解了，如果把 O(n) 的代碼再嵌套循環一遍，它的時間復雜度就是 O(n2)，這段代碼其實就是嵌套了2層n循環，它的時間復雜度就是 O(n*n)，即 O(n2) 如果將其中一層循環的n改成m，那它的時間復雜度就變成了?O(m*n)
6.立方階O(n^3)、 k次方階O(n^k)
O(n3)相當于三層n循環，其它的類似
3.5、平均時間復雜度和最壞時間復雜度
平均時間復雜度是指所有可能的輸入實例均以等概率出現的情況下，該算法的運行時間
最壞情況下的時間復雜度稱最壞時間復雜度。一般討論的時間復雜度均是最壞情況下的時間復雜度。 這樣做的原因是：最壞情況下的時間復雜度是算法在任何輸入實例上運行時間的界限，這就保證了算法的運行時間不會比最壞情況更長
平均時間復雜度和最壞時間復雜度是否一致，和算法有關
4、算法的空間復雜度
-
類似于時間復雜度的討論，一個算法的空間復雜度(Space Complexity)定義為該算法所耗費的存儲空間，它也是問題規模n的函數
-
空間復雜度(Space Complexity)是對一個算法在運行過程中臨時占用存儲空間大小的量度。有的算法需要占用的臨時工作單元數與解決問題的規模n有關，它隨著n的增大而增大，當n較大時，將占用較多的存儲單元，例如快速排序和歸并排序算法就屬于這種情況
-
在做算法分析時，主要討論的是時間復雜度。從用戶使用體驗上看，更看重的程序執行的速度。一些緩存產品(redis, memcache)和算法(基數排序)本質就是用空間換時間.
5、冒泡排序
5.1、冒泡排序簡介
冒泡排序（Bubble Sorting）的基本思想是：通過對待排序序列從前向后（從下標較小的元素開始）,?依次比較?相鄰元素的值，若發現逆序則?交換?，使值較大的元素逐漸從前移向后部，就象水底下的氣泡一樣逐漸向上冒。
優化：因為排序的過程中，各元素不斷接近自己的位置，如果一趟比較下來沒有進行過交換，就說明序列有序，因此要在排序過程中設置
一個標志?flag?判斷元素是否進行過交換。從而減少不必要的比較。
5.2、冒泡排序過程演示
-
圖解過程
-
過程分析
(1) 一共進行數組的大小?-?1 （?arr.length - 1?）次 大的循環
(2)每一趟排序的次數在逐漸的減少
(3) 優化思路：如果我們發現在某趟排序中，沒有發生一次交換， 可以提前結束冒泡排序
動態圖
?
5.3、冒泡排序代碼實現
未優化
public class Test {public static void main(String[] args) {int arr[] = {3, 9, -1, 10, 20};//冒泡排序，時間復雜度O(n2)//定義一個臨時變量int temp = 0;for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {//如果前面的數比后面的大，就交換if (arr[j] > arr[j + 1]) {temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}System.out.println("第" + (i + 1) + "趟排序后的數組");System.out.println(Arrays.toString(arr));}} }結果展示：
優化
?
public class Test {public static void main(String[] args) {int arr[] = {3, 9, -1, 10, 20};//冒泡排序，時間復雜度O(n2)int temp = 0;//定義一個臨時變量boolean flag = false;//表示變量，表示是否進行過交換for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {//如果前面的數比后面的大，就交換if (arr[j] > arr[j + 1]) {flag = true;temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}System.out.println("第" + (i + 1) + "趟排序后的數組");System.out.println(Arrays.toString(arr));if (!flag) {//在一趟排序中，一次交換都沒有發生過,!flag也可以寫成flag==falsebreak;} else {flag = false;//重置flag,進行下一次判斷}}} }結果展示：
封裝成方法
public class BubbleSort {public static void main(String[] args) {int arr[] = {3, 9, -1, 10, 20};//測試冒泡排序System.out.println("排序前的數組");System.out.println(Arrays.toString(arr));bubbleSort(arr);System.out.println("排序后的數組");System.out.println(Arrays.toString(arr));}//將前面的冒泡排序封裝成一個方法public static void bubbleSort(int arr[]){//冒泡排序，時間復雜度O(n2)int temp = 0;//定義一個臨時變量boolean flag = false;//表示變量，表示是否進行過交換for (int i = 0; i < arr.length - 1; i++) {for (int j = 0; j < arr.length - 1 - i; j++) {//如果前面的數比后面的大，就交換if (arr[j] > arr[j + 1]) {flag = true;temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}//System.out.println("第" + (i + 1) + "趟排序后的數組");//System.out.println(Arrays.toString(arr));if (!flag) {//在一趟排序中，一次交換都沒有發生過,!flag也可以寫成flag==falsebreak;} else {flag = false;//重置flag,進行下一次判斷}}}}?
結果展示：
測試冒泡排序O(n2）的速度
為了測試冒泡排序O(n2）的速度，我們隨機生成80000個數據進行排序，由于打印80000個數據很不方便，我們就輸出排序前后的時間
?
//測試一下冒泡排序的速度O(n^2), 給80000個數據，測試 //創建要給80000個的隨機的數組 int[] arr = new int[80000]; for(int i =0; i < 80000;i++) {arr[i] = (int)(Math.random() * 8000000); //生成一個[0, 8000000) 數 }Date data1 = new Date(); SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss"); String date1Str = simpleDateFormat.format(data1); System.out.println("排序前的時間是=" + date1Str);//測試冒泡排序 bubbleSort(arr);Date data2 = new Date(); String date2Str = simpleDateFormat.format(data2); System.out.println("排序后的時間是=" + date2Str);結果展示：
6、選擇排序
6.1、選擇排序簡介
選擇排序也屬于內部排序法，是從欲排序的數據中，按指定的規則選出某一元素，再依規定交換位置后達到排序的目的
排序思想：
第一次從arr[0]~arr[n-1]中選取最小值，與arr[0]交換， 第二次從arr[1]~arr[n-1]中選取最小值，與arr[1]交換， 第三次從arr[2]~arr[n-1]中選取最小值，與arr[2]交換，…， 第i次從arr[i-1]~arr[n-1]中選取最小值，與arr[i-1]交換，…, 第n-1次從arr[n-2]~arr[n-1]中選取最小值，與arr[n-2]交換， 總共通過n-1次，得到一個按排序碼從小到大排列的有序序列。?
6.2、選擇排序過程演示
- 過程圖解
-
過程分析
-
選擇排序一共有 數組大小 - 1（?arr.length-1?） 輪排序
2. 每1輪排序，又是一個循環, 循環的規則(代碼)
2.1先假定當前這個數是最小數
2.2 然后和后面的每個數進行比較，如果發現有比當前數更小的數，就重新確定最小數，并得到下標
2.3 當遍歷到數組的最后時，就得到本輪最小數和下標
2.4 交換
動態圖
?
6.3、選擇排序代碼實現
優化+封裝
?
public class SelectSort {public static void main(String[] args) {int [] arr = {100,35,120,7};System.out.println("排序前");System.out.println(Arrays.toString(arr));selectSort(arr);System.out.println("排序后");System.out.println(Arrays.toString(arr));}//選擇排序的方法public static void selectSort(int [] arr){for (int i = 0; i < arr.length - 1; i++) {int minIndex = i;int min = arr[i];for (int j = i+1; j < arr.length; j++) {if (min > arr[j]){//說明假定的最小值不是最小minIndex = j;//重置min和minIndexmin = arr[j];}}//交換，將最小值依次放在最前面//優化：如果假定的最小值就是真實的最小值，那么就不進行交換（這里假定的最小值是上一輪交換后的下一個值）if (minIndex != i){arr[minIndex] = arr[i];arr[i] = min;}//System.out.println("第"+(i+1)+"輪后");//System.out.println(Arrays.toString(arr));}} }結果展示
測試選擇排序O(n2）的速度
測試方法同冒泡排序中的方法，我們在測試之前通過分析可以得出選擇排序交換是找到最小（大）值才進行交換，而冒泡排序是相鄰元素之間進行比較交換，所以選擇排序的交換次數應該比冒泡排序少，速度應該更快。
7、插入排序
7.1、插入排序簡介
插入式排序屬于內部排序法，是對于欲排序的元素以插入的方式找尋該元素的適當位置，以達到排序的目的。
排序思想：
插入排序（Insertion Sorting）的基本思想是：把 把 n 個待排序的元素看成為一個有序表和一個無序表，開始時 有
序表中只包含一個元素，無序表中包含有 n-1 個元素，排序過程中每次從無序表中取出第一個元素，把它的排
序碼依次與有序表元素的排序碼進行比較，將它插入到有序表中的適當位置，使之成為新的有序表。
7.2、插入排序過程演示
-
過程圖解
動態圖
?
7.3、插入排序代碼實現
插入排序
public class InsertSort {public static void main(String[] args) {int [] arr = {23,56,189,77,-1,0};insertSort(arr);}//插入排序public static void insertSort(int [] arr){for (int i = 1; i < arr.length ; i++) {//定義待插入的數int insertVal = arr[i];int insertIndex = i - 1;// 給insertVal 找到插入的位置// 說明// 1. insertIndex >= 0 保證在給insertVal 找插入位置，不越界// 2. insertVal < arr[insertIndex] 待插入的數，還沒有找到插入位置// 3. 就需要將 arr[insertIndex] 后移while (insertIndex >=0 && insertVal < arr[insertIndex]){arr[insertIndex + 1] = arr[insertIndex];insertIndex--;}// 當退出while循環時，說明插入的位置找到, insertIndex + 1//這里我們判斷是否需要賦值(加上if語句就是優化)if (insertVal + 1 != i) {arr[insertIndex + 1] = insertVal;}System.out.println("第"+i+"輪插入");System.out.println(Arrays.toString(arr));}}}結果：
測試插入排序O(n2）的速度
?
public static void main(String[] args) {// 創建要給80000個的隨機的數組int[] arr = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int) (Math.random() * 8000000); // 生成一個[0, 8000000) 數}System.out.println("插入排序前");Date data1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String date1Str = simpleDateFormat.format(data1);System.out.println("排序前的時間是=" + date1Str);insertSort(arr); //調用插入排序算法Date data2 = new Date();String date2Str = simpleDateFormat.format(data2);System.out.println("排序后的時間是=" + date2Str);}測試結果：本機耗時約為1s
8、希爾排序
8.1、簡單插入排序存在的問題
我們看簡單的插入排序可能存在的問題.
數組 arr = {2,3,4,5,6,1} 這時需要插入的數 1( 最小), 這樣的過程是：
{2,3,4,5,6,6}
{2,3,4,5,5,6}
{2,3,4,4,5,6}
{2,3,3,4,5,6}
{2,2,3,4,5,6}
{1,2,3,4,5,6}
結論: 當 需要插入的數是較小的數時， 后移的次數明顯增多，對 效率有影響.
8.2、希爾排序簡介
希爾排序是希爾（Donald Shell）于 1959 年提出的一種排序算法。
希爾排序也是一種 插入排序，它是簡單插入排序經過改進之后的一個 更高效的版本，也稱為?縮小增量排序
-
排序思想
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含
的關鍵詞越來越多， 當增量減至 1 時，整個文件恰被分成一組，算法便終止
8.3、希爾排序過程演示
動態圖
?
8.4、希爾排序代碼實現
交換法
public class ShellSort {public static void main(String[] args) {int [] arr = {8,9,1,7,2,3,5,4,6,0};shellSort(arr);}//希爾排序public static void shellSort(int [] arr){int temp = 0;int count = 0;//分組for (int gap = arr.length/2;gap > 0; gap /= 2){//遍歷各組for (int i = gap;i < arr.length;i++){//遍歷各組中的所有元素（共gap組，每組有arr.length/gap個元素，步長是gap）//j -= gap,之前插入排序是index--,因為每次要往前一步，現在是希爾排序，有間隔，所以是j -= gapfor (int j = i - gap; j >= 0 ; j -= gap) {//如果當前元素大于加上步長后的那個元素，說明交換if (arr[j] > arr[j+gap]) {temp = arr[j];arr[j] = arr[j + gap];arr[j + gap] = temp;}}}System.out.println("希爾排序第"+ (++count) +"輪："+ Arrays.toString(arr));}} }結果：
速度測試：本機耗時約為5s,可以看到交換法并沒有對簡單插入排序的速度進行提升，接下來我們來看移動法
移位法（重點）
//希爾排序移動法 public static void shellSort2(int [] arr){int count = 0;//增量gap,并逐步縮小增量for (int gap = arr.length/2;gap > 0; gap /= 2){//從第gap個元素開始，逐個對其所在的組進行直接插入排序for (int i = gap; i < arr.length; i++) {int j = i;int temp = arr[j];if(arr[j] < arr[j -gap]){while (j - gap >= 0 && temp < arr[j - gap]){//移動arr[j] = arr[j - gap];j -= gap;}//當退出while循環后，就給temp找到插入的位置arr[j] = temp;}}System.out.println("希爾排序第"+ (++count) +"輪："+ Arrays.toString(arr));}}結果：
速度測試：本機耗時不到1s,確實提升了簡單插入排序的速度
9、快速排序
9.1、快速排序簡介
快速排序（Quicksort）是對?冒泡排序?的一種改進。基本思想是：通過一趟排序將要排序的數據?分割?成獨立的兩
部分，其中一部分的所有數據都比另外一部分的所有數據都要小，然后再按此方法對這兩部分數據分別進行快速排
序， 整個排序過程可以遞歸進行，以此達到整個數據變成有序序列
9.2、快速排序過程演示
動態圖
?
9.3、快速排序代碼實現
要求：對?10,7,2,4,7,62,3,4,2,1,8,9,19?進行從小到大的排序，要求使用快速排序法
代碼實現
public class QuickSort {public static void main(String[] args){int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};quickSort(arr, 0, arr.length-1);System.out.println("arr="+ Arrays.toString(arr));}public static void quickSort(int[] arr,int low,int high){int i,j,temp,t;if(low>high){return;}i=low;j=high;//temp就是基準位，這里基準位取的是低半區的第一個數據temp = arr[low];while (i<j) {//先看右邊，依次往左遞減while (temp<=arr[j]&&i<j) {j--;}//再看左邊，依次往右遞增while (temp>=arr[i]&&i<j) {i++;}//如果滿足條件則交換if (i<j) {t = arr[j];arr[j] = arr[i];arr[i] = t;}}//最后將基準位與i和j相等位置的數字交換，因為這里基準位取的是低半區的第一個數據arr[low] = arr[i];arr[i] = temp;//遞歸調用左半數組quickSort(arr, low, j-1);//遞歸調用右半數組quickSort(arr, j+1, high);}}結果：
快速排序速度測試O(nlogn)
分析
-
快速排序是基于一種叫做“二分”的思想，快速排序之所比較快，因為相比冒泡排序，每次交換是跳躍式的。
-
每次排序的時候設置一個基準點，將小于等于基準點的數全部放到基準點的左邊，將大于等于基準點的數全部放到基準點的右邊。
-
這樣在每次交換的時候就不會像冒泡排序一樣每次只能在相鄰的數之間進行交換，交換的距離就大的多了。
-
因此總的比較和交換次數就少了，速度自然就提高了。
-
當然在最壞的情況下，仍可能是相鄰的兩個數進行了交換。因此快速排序的最差時間復雜度和冒泡排序是一樣的都是O(N2)，它的平均時間復雜度為O(NlogN)。
-
快速排序理論上速度是優于希爾排序的
10、歸并排序
10.1、歸并排序簡介
歸并排序（MERGE-SORT）是利用歸并的思想實現的排序方法，該算法采用經典的?分治?（divide-and-conquer ）
策略（分治法將問題分(divide)成一些 小的問題然后遞歸求解，而治(conquer)的階段則將分的階段得到的各答案"修
補"在一起，即分而治之)。
10.2、歸并排序過程演示
（1）歸并排序示意圖1
（2）歸并排序示意圖2
來看看治階段，我們需要將兩個已經有序的子序列合并成一個有序序列，比如上圖中的最后一次合并，要將
[4,5,7,8]和[1,2,3,6]兩個已經有序的子序列，合并為最終序列[1,2,3,4,5,6,7,8]，來看下實現步驟
動態圖
?
10.3、歸并排序代碼實現
代碼實現
public class MergetSort {public static void main(String[] args) {int arr[] = {8,4,5,7,1,3,6,2};int temp[] = new int[arr.length]; //歸并排序需要一個額外空間mergeSort(arr, 0, arr.length - 1, temp);System.out.println("歸并排序后="+ Arrays.toString(arr));}//分+合方法public static void mergeSort(int[] arr, int left, int right, int[] temp) {if(left < right) {int mid = (left + right) / 2; //中間索引//向左遞歸進行分解mergeSort(arr, left, mid, temp);//向右遞歸進行分解mergeSort(arr, mid + 1, right, temp);//合并merge(arr, left, mid, right, temp);}}//合并的方法/**** @param arr 排序的原始數組* @param left 左邊有序序列的初始索引* @param mid 中間索引* @param right 右邊索引* @param temp 做中轉的數組*/public static void merge(int[] arr, int left, int mid, int right, int[] temp) {int i = left; // 初始化i, 左邊有序序列的初始索引int j = mid + 1; //初始化j, 右邊有序序列的初始索引int t = 0; // 指向temp數組的當前索引//(一)//先把左右兩邊(有序)的數據按照規則填充到temp數組//直到左右兩邊的有序序列，有一邊處理完畢為止while (i <= mid && j <= right) {//繼續//如果左邊的有序序列的當前元素，小于等于右邊有序序列的當前元素//即將左邊的當前元素，填充到 temp數組//然后 t++, i++if(arr[i] <= arr[j]) {temp[t] = arr[i];t += 1;i += 1;} else { //反之,將右邊有序序列的當前元素，填充到temp數組temp[t] = arr[j];t += 1;j += 1;}}//(二)//把有剩余數據的一邊的數據依次全部填充到tempwhile( i <= mid) { //左邊的有序序列還有剩余的元素，就全部填充到temptemp[t] = arr[i];t += 1;i += 1;}while( j <= right) { //右邊的有序序列還有剩余的元素，就全部填充到temptemp[t] = arr[j];t += 1;j += 1;}//(三)//將temp數組的元素拷貝到arr//注意，并不是每次都拷貝所有t = 0;int tempLeft = left; ////第一次合并 tempLeft = 0 , right = 1 // tempLeft = 2 right = 3 // tL=0 ri=3//最后一次 tempLeft = 0 right = 7while(tempLeft <= right) {arr[tempLeft] = temp[t];t += 1;tempLeft += 1;}}}結果：
歸并排序速度測試O(nlogn)
11、桶排序
11.1、桶排序簡介
-
桶排序(Bucket sort)是將待排序集合中處于同一個值域的元素存入同一個桶中，也就是根據元素值特性將集合拆分為多個區域，則拆分后形成的多個桶，從值域上看是處于有序狀態的。對每個桶中元素進行排序，則所有桶中元素構成的集合是已排序的。
-
如果桶的大小劃分得足夠小，到達每個元素之間的最小差值，則可以保證每一個桶里面所有的數據都是一樣的，入桶后的數據也就不需要再次進行排序，這種情況也就是桶排序時間復雜度最優的情況即O ( n ) .一般情況下桶排序的時間復雜度為O ( n + k) ，其中n為元素個數，k為桶個數。
11.2、桶排序過程演示
排序思想
- 確定桶的大小與個數，一般根據要排序的元素的值域區間取定。
- 設計一種方式使元素能映射至對應值域的桶的索引。
- 遍歷所有元素，將它們入桶。
- 每個桶內元素排序。
- 從桶內依次提取各元素重新排列
過程演示
動態圖
?
11.3、桶排序代碼實現
代碼
public static void main(String[] args) {int[] arr = { 1, 45, 32, 23, 22, 31, 47, 24, 4, 15 };bucketsort(arr);}public static void bucketsort(int[] arr) {ArrayList bucket[] = new ArrayList[5];// 聲明五個桶for (int i = 0; i < bucket.length; i++) {bucket[i] = new ArrayList<Integer>();// 確定桶的格式為ArrayList}for (int i = 0; i < arr.length; i++) {int index = arr[i] / 10;// 確定元素存放的桶號bucket[index].add(arr[i]);// 將元素存入對應的桶中}for (int i = 0; i < bucket.length; i++) {// 遍歷每一個桶bucket[i].sort(null);// 對每一個桶排序for (int i1 = 0; i1 < bucket[i].size(); i1++) {// 遍歷桶中的元素并輸出System.out.print(bucket[i].get(i1) + " ");}}}}結果：
桶排序速度測試
?
public class BucketSort {public static void main(String[] args) {// int[] arr = { 1, 45, 32, 23, 22, 31, 47, 24, 4, 15 }; // bucketsort(arr);int[] arr = new int[80000];for (int i = 0; i < 80000; i++) {arr[i] = (int) (Math.random() * 80000); // 生成一個[0, 8000000) 數}System.out.println("排序前");Date data1 = new Date();SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");String date1Str = simpleDateFormat.format(data1);System.out.println("排序前的時間是=" + date1Str);bucketsort(arr);Date data2 = new Date();String date2Str = simpleDateFormat.format(data2);System.out.println("排序后的時間是=" + date2Str);}public static void bucketsort(int[] arr) {ArrayList bucket[] = new ArrayList[80000];// 聲明五個桶for (int i = 0; i < bucket.length; i++) {bucket[i] = new ArrayList<Integer>();// 確定桶的格式為ArrayList}for (int i = 0; i < arr.length; i++) {int index = arr[i] / 10;// 確定元素存放的桶號bucket[index].add(arr[i]);// 將元素存入對應的桶中}for (int i = 0; i < bucket.length; i++) {// 遍歷每一個桶bucket[i].sort(null);// 對每一個桶排序for (int i1 = 0; i1 < bucket[i].size(); i1++) {// 遍歷桶中的元素并輸出System.out.print(bucket[i].get(i1) + " ");}}}}12、基數排序
12.1、基數排序簡介
? 1.基數排序（radix sort）屬于“分配式排序”（distribution sort），又稱“桶子法”（bucket sort）或 bin sort，顧
? 名思義，它是通過鍵值的各個位的值，將要排序的元素分配至某些“桶”中，達到排序的作用
位數分別比較。
12.2、基數排序過程演示
- 排序思想：
- 將所有待比較數值統一為同樣的數位長度，數位較短的數前面補零然后，從最低位開始，依次進行一次排序這樣從最低位排序一直到最高位排序完成以后, 數列就變成一個有序序列
動態圖
?
12.3、基數排序代碼實現
按每一輪具體分析（推導過程）
public class RadixSort {public static void main(String[] args) {int arr[] = {53,3,542,748,14,214};radixSort(arr);}//基數排序public static void radixSort(int [] arr){//定義一個二維數組，表示是10個桶，每一個桶代表一個一維數組//說明//1. 二維數組包含10個一維數組//2. 為了防止在放入數的時候，數據溢出，則每個一維數組(桶)，大小定為arr.length//3. 很明顯基數排序是使用空間換時間的經典算法int[][] bucket = new int[10][arr.length];//為了記錄每個桶中，實際存放了多少個數據,我們定義一個一維數組來記錄各個桶的每次放入的數據個數//比如：bucketElementCounts[0] , 記錄的就是 bucket[0] 桶的放入數據個數int [] bucketElementCounts = new int[10];//第一輪排序,針對每個元素的個位進行排序for (int i = 0; i < arr.length; i++) {//取出每個元素的個位的值int digitOfElement = arr[i]%10;//放入到對應的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[i];bucketElementCounts[digitOfElement]++;}//按照這個桶的順序(一維數組的下標依次取出數據，放入原來數組)int index = 0;//遍歷每一個桶，并將桶中的數據放入到原數組for (int k = 0; k < bucketElementCounts.length; k++) {//如果桶中有數據，我們才放入到原數組if (bucketElementCounts[k]!=0){//說明第k個桶有數據//循環該桶（即第k個一位數組）for (int j = 0; j < bucketElementCounts[k]; j++) {//取出元素放入到arr中arr[index++] = bucket[k][j];//第k個桶里面的第j個元素}}//第1輪處理后，需要將每個 bucketElementCounts[k] = 0 ！！！！bucketElementCounts[k] = 0;}System.out.println("第1輪，對個位的排序處理 arr =" + Arrays.toString(arr));//第2輪(針對每個元素的十位進行排序處理)for (int j = 0; j < arr.length; j++) {// 取出每個元素的十位的值int digitOfElement = arr[j] / 10 % 10; //748 / 10 => 74 % 10 => 4// 放入到對應的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];bucketElementCounts[digitOfElement]++;}// 按照這個桶的順序(一維數組的下標依次取出數據，放入原來數組)index = 0;// 遍歷每一桶，并將桶中是數據，放入到原數組for (int k = 0; k < bucketElementCounts.length; k++) {// 如果桶中，有數據，我們才放入到原數組if (bucketElementCounts[k] != 0) {// 循環該桶即第k個桶(即第k個一維數組), 放入for (int j = 0; j < bucketElementCounts[k]; j++) {// 取出元素放入到arrarr[index++] = bucket[k][j];}}//第2輪處理后，需要將每個 bucketElementCounts[k] = 0 ！！！！bucketElementCounts[k] = 0;}System.out.println("第2輪，對十位的排序處理 arr =" + Arrays.toString(arr));//第3輪(針對每個元素的百位進行排序處理)for (int j = 0; j < arr.length; j++) {// 取出每個元素的十位的值int digitOfElement = arr[j] / 100 % 10; //748 / 100 => 7// 放入到對應的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];bucketElementCounts[digitOfElement]++;}// 按照這個桶的順序(一維數組的下標依次取出數據，放入原來數組)index = 0;// 遍歷每一桶，并將桶中是數據，放入到原數組for (int k = 0; k < bucketElementCounts.length; k++) {// 如果桶中，有數據，我們才放入到原數組if (bucketElementCounts[k] != 0) {// 循環該桶即第k個桶(即第k個一維數組), 放入for (int j = 0; j < bucketElementCounts[k]; j++) {// 取出元素放入到arrarr[index++] = bucket[k][j];}}//第3輪處理后，需要將每個 bucketElementCounts[k] = 0 ！！！！bucketElementCounts[k] = 0;}System.out.println("第3輪，對百位的排序處理 arr =" + Arrays.toString(arr));} }結果：
最終代碼
import java.util.Arrays;public class RadixSort {public static void main(String[] args) {int arr[] = {53,3,542,748,14,214};radixSort(arr);}//基數排序public static void radixSort(int [] arr){//根據前面的推導過程，我們可以得到最終的基數排序代碼//得到數組中最大的數int max = arr[0]; //假設第一數就是最大數for(int i = 1; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}}//得到最大數是幾位數int maxLength = (max + "").length();//定義一個二維數組，表示是10個桶，每一個桶代表一個一維數組//說明//1. 二維數組包含10個一維數組//2. 為了防止在放入數的時候，數據溢出，則每個一維數組(桶)，大小定為arr.length//3. 很明顯基數排序是使用空間換時間的經典算法int[][] bucket = new int[10][arr.length];//為了記錄每個桶中，實際存放了多少個數據,我們定義一個一維數組來記錄各個桶的每次放入的數據個數//比如：bucketElementCounts[0] , 記錄的就是 bucket[0] 桶的放入數據個數int [] bucketElementCounts = new int[10];//這里使用循環處理一下for (int i = 0, n = 1; i < maxLength; i++,n*=10) {//(針對每個元素的對應位進行排序處理)， 第一次是個位，第二次是十位，第三次是百位..for (int m = 0; m < arr.length; m++) {//取出每個元素的個位的值int digitOfElement = arr[m] / n % 10;//放入到對應的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[m];bucketElementCounts[digitOfElement]++;}//按照這個桶的順序(一維數組的下標依次取出數據，放入原來數組)int index = 0;//遍歷每一個桶，并將桶中的數據放入到原數組for (int k = 0; k < bucketElementCounts.length; k++) {//如果桶中有數據，我們才放入到原數組if (bucketElementCounts[k]!=0){//說明第k個桶有數據//循環該桶（即第k個一位數組）for (int j = 0; j < bucketElementCounts[k]; j++) {//取出元素放入到arr中arr[index++] = bucket[k][j];//第k個桶里面的第j個元素}}//第i+1輪處理后，需要將每個 bucketElementCounts[k] = 0 ！！！！bucketElementCounts[k] = 0;}System.out.println("第"+(i+1)+"輪，對個位的排序處理 arr =" + Arrays.toString(arr));}} }?
結果：
基數排序速度測試O(n*k)
12.4、基數排序說明
基數排序是對傳統桶排序的擴展，速度很快.
基數排序是經典的空間換時間的方式，占用內存很大, 當對海量數據排序時，容易造成 OutOfMemoryError 。
基數排序是穩定的。
[注:假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些
記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且 r[i]在 r[j]之前，而在排序后的序列中，r[i]仍在 r[j]之前，
則稱這種排序算法是穩定的；否則稱為不穩定的]
13、計數排序
13.1、計數排序簡介
-
計數排序是一個非基于比較的排序算法，元素從未排序狀態變為已排序狀態的過程，是由額外空間的輔助和元素本身的值決定的。
-
該算法于1954年由 Harold H. Seward 提出。
-
它的優勢在于在對一定范圍內的整數排序時，它的復雜度為Ο(n+k)（其中k是整數的范圍），快于任何比較排序算法。
-
當然這是一種犧牲空間換取時間的做法，而且當?O(k)>O(nlogn)?的時候其效率反而不如基于比較的排序，因為基于比較的排序的時間復雜度在理論上的下限是?O(nlogn)?。
13.2、計數排序過程演示
排序思想
排序示意圖
詳解過程圖：
先假設 20 個數列為：{9, 3, 5, 4, 9, 1, 2, 7, 8，1，3, 6, 5, 3, 4, 0, 10, 9, 7, 9}。
讓我們先遍歷這個無序的隨機數組，找出最大值為 10 和最小值為 0。這樣我們對應的計數范圍將是 0 ~ 10。然后每一個整數按照其值對號入座，對應數組下標的元素進行加1操作。
比如第一個整數是 9，那么數組下標為 9 的元素加 1，如下圖所示。
第二個整數是 3，那么數組下標為 3 的元素加 1，如下圖所示。
繼續遍歷數列并修改數組......。最終，數列遍歷完畢時，數組的狀態如下圖。
數組中的每一個值，代表了數列中對應整數的出現次數。
有了這個統計結果，排序就很簡單了，直接遍歷數組，輸出數組元素的下標值，元素的值是幾，就輸出幾次。比如統計結果中的 1 為 2，就是數列中有 2 個 1 的意思。這樣我們就得到最終排序好的結果。
0, 1, 1, 2, 3, 3, 3, 4, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9, 9, 10
動態演示：
?
13.3、計數排序代碼實現
代碼
public class CountingSort {public static void main(String[] args) {int []num ={7,4,9,3,2,1,8,6,5,10};long startTime=System.currentTimeMillis();int min=Integer.MAX_VALUE;int max=Integer.MIN_VALUE;//先找出數組中的最大值與最小值for(int i=0;i<num.length;i++) {if(num[i]<min)min=num[i];if(num[i]>max)max=num[i];}//創建一個長度為max-min+1長度的數組來進行計數int []figure=new int [max-min+1];for(int i=0;i<num.length;i++) {//計算每個數據出現的次數figure[num[i]-min]++;}int begin=0;//創建一個新的數組來存儲已經排序完成的結果int []num1=new int [num.length];for(int i=0;i<figure.length;i++) {//循環將數據pop出來if(figure[i]!=0) {for(int j=0;j<figure[i];j++) {num1[begin++]=min+i;}}}System.out.println("數據范圍:"+min+"~"+max);System.out.println("計數結果: ");for(int i=0;i<num.length;i++)System.out.println(" "+num[i]+"出現"+figure[num[i]-min]+"次");System.out.print("排序結果: ");for(int i=0;i<num1.length;i++)System.out.print(num1[i]+" ");System.out.println();long endTime=System.currentTimeMillis();System.out.println("程序運行時間： "+(endTime-startTime)+"ms");}}結果：
14、堆排序
14.1、堆排序簡介
? 1.堆排序是利用堆這種數據結構而設計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復雜度均為 O(nlogn)，它 是不穩定排序。
堆是具有以下性質的完全二叉樹：每個結點的值都大于或等于其左右孩子結點的值，稱為大根堆（或大頂堆）, 注意 : 沒有
要求結點的左孩子的值和右孩子的值的大小關系。
每個結點的值都小于或等于其左右孩子結點的值，稱為小根堆（或小頂堆）
一般升序采用大根堆，降序采用小根堆
14.2、堆排序過程演示
堆排序的基本思想是：
序列了。
步驟圖解
要求：給你一個數組 {4,6,8,5,9} , 要求使用堆排序法，將數組升序排序。
- 步驟一 構造初始堆。將給定無序序列構造成一個大根堆（一般升序采用大根堆，降序采用小根堆)。
- 原始的數組 [4, 6, 8, 5, 9]
3.找到第二個非葉節點 4，由于[4,9,8]中 9 元素最大，4 和 9 交換。
4.這時，交換導致了子根[4,5,6]結構混亂，繼續調整，[4,5,6]中 6 最大，交換 4 和 6。
此時，我們就將一個無序序列構造成了一個大頂堆.
- 步驟二 將堆頂元素與末尾元素進行交換，使末尾元素最大。然后繼續調整堆，再將堆頂元素與末尾元素交換得到第二大元素。如此反復進行交換、重建、交換
1.將堆頂元素 9 和末尾元素 4 進行交換
2.重新調整結構，使其繼續滿足堆定義
3.再將堆頂元素 8 與末尾元素 5 進行交換，得到第二大元素 8
4.后續過程，繼續進行調整，交換，如此反復進行，最終使得整個序列有序
動態演示
?
再簡單總結下堆排序的基本思路：
1).將無序序列構建成一個堆，根據升序降序需求選擇大根堆或小根堆;
2).將堆頂元素與末尾元素交換，將最大元素"沉"到數組末端;
3).重新調整結構，使其滿足堆定義，然后繼續交換堆頂元素與當前末尾元素，反復執行調整+交換步驟，直到整個序列有序
14.3、堆排序代碼實現
堆排序的理解還是比較困難的，尤其是代碼實現過程，下面提供兩種代碼實現，大家可以選擇適合自己的實現方法來理解堆排序
代碼實現（一）
import java.util.Arrays;public class HeapSort {public static void main(String[] args) {//升序--->大頂堆long startTime=System.currentTimeMillis();int arr[] = {5,3,7,1,4,6,2};heapSort(arr);long endTime=System.currentTimeMillis();System.out.println("程序運行時間： "+(endTime-startTime)+"ms");}//編寫一個堆排序的方法public static void heapSort(int arr[]) {int temp = 0;//完成我們最終代碼//將無序序列構建成一個堆，根據升序降序需求選擇大頂堆或小頂堆for(int i = arr.length / 2 -1; i >=0; i--) {adjustHeap(arr, i, arr.length);}/** 2).將堆頂元素與末尾元素交換，將最大元素"沉"到數組末端;3).重新調整結構，使其滿足堆定義，然后繼續交換堆頂元素與當前末尾元素，反復執行調整+交換步驟，直到整個序列有序。*/for(int j = arr.length-1;j >0; j--) {//交換temp = arr[j];arr[j] = arr[0];arr[0] = temp;adjustHeap(arr, 0, j);}System.out.println("數組=" + Arrays.toString(arr));}//將一個數組(二叉樹), 調整成一個大頂堆/*** 功能： 完成 將 以 i 對應的非葉子結點的樹調整成大頂堆* 舉例 int arr[] = {4, 6, 8, 5, 9}; => i = 1 => adjustHeap => 得到 {4, 9, 8, 5, 6}* 如果我們再次調用 adjustHeap 傳入的是 i = 0 => 得到 {4, 9, 8, 5, 6} => {9,6,8,5, 4}* @param arr 待調整的數組* @param i 表示非葉子結點在數組中索引* @param length 表示對多少個元素繼續調整， length 是在逐漸的減少*/public static void adjustHeap(int arr[], int i, int length) {int temp = arr[i];//先取出當前元素的值，保存在臨時變量//開始調整//說明//1. k = i * 2 + 1 k 是 i結點的左子結點for(int k = i * 2 + 1; k < length; k = k * 2 + 1) {if(k+1 < length && arr[k] < arr[k+1]) { //說明左子結點的值小于右子結點的值k++; // k 指向右子結點}if(arr[k] > temp) { //如果子結點大于父結點arr[i] = arr[k]; //把較大的值賦給當前結點i = k; //!!! i 指向 k,繼續循環比較} else {break;//!}}//當for 循環結束后，我們已經將以i 為父結點的樹的最大值，放在了 最頂(局部)arr[i] = temp;//將temp值放到調整后的位置} }?
結果：
代碼實現（二）
?
//交換數組中的元素public static void swap(int[]num ,int i,int j) {int temp=num[i];num[i]=num[j];num[j]=temp;}//將待排序的數組構建成大根堆public static void buildbigheap(int []num,int end) {//從最后一個非葉子節點開始構建,依照從下往上,從右往左的順序for(int i=end/2;i>=0;i--) {adjustnode(i, end, num);}}//調整該節點及其以下的所有節點public static void adjustnode(int i,int end,int []num) {int left=2*i+1;int right=2*i+2;int big=i;//判斷小分支那個是大元素if(left<end&#[i]<num[left])i=left;if(right<end&#[i]<num[right])i=right;if(i!=big) {//交換順序之后需要繼續校驗swap(num, i, big);//重新校驗,防止出現交換之后根節點小于孩子節點的情況adjustnode(i, end, num);}}public static void main(String[] args) {int []num ={5,3,7,1,4,6,2};long startTime=System.currentTimeMillis(); //第一次構建大根堆buildbigheap(num, num.length);for(int j=num.length-1;j>0;j--) {System.out.print("第"+(num.length-j)+"次排序前: ");for(int k=0;k<num.length;k++) {System.out.print(num[k]+" ");}//交換隊頭已經排序得到的最大元素與隊尾元素swap(num, 0, j);System.out.print("第"+(num.length-j)+"次排序后: ");for(int k=0;k<num.length;k++) {System.out.print(num[k]+" ");}System.out.println();//交換結束之后,大根堆已經被破壞,需要開始重新構建大根堆buildbigheap(num,j);}long endTime=System.currentTimeMillis(); System.out.println("程序運行時間： "+(endTime-startTime)+"ms"); }結果：
15、十大排序算法總結
15.1、十大排序算法分類
（1）按照是否是比較算法分類
（2）按照算法是否穩定分類
如何區分算法是否穩定？
通俗來講就是數據相對于原來的相對位置沒有發生變化
15.2、十大算法的平均時間復雜度
下面這張圖說明了各個排序算法的時間復雜度等各項衡量算法的指標，希望大家記住！！！
術語解釋：
1）穩定：如果 a 原本在 b 前面，而 a=b，排序之后 a 仍然在 b 的前面；
2) 不穩定：如果 a 原本在 b 的前面，而 a=b，排序之后 a 可能會出現在 b 的后面；
3) 內排序：所有排序操作都在內存中完成；
4) 外排序：由于數據太大，因此把數據放在磁盤中，而排序通過磁盤和內存的數據傳輸才能進行；
5) 時間復雜度： 一個算法執行所耗費的時間。
6) 空間復雜度：運行完一個程序所需內存的大小。
7) n: 數據規模
8) k: “桶”的個數
9) In-place: 不占用額外內存
10) Out-place: 占用額外內存
到這里關于十大排序算法的知識到這里就結束了。
總結
以上是生活随笔為你收集整理的数据结构与算法【Java】05---排序算法总结的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 超美的WPF控件库
- 下一篇： 今日分享|闪魔钢化膜5.8又来了/iPh