數據結構與演算法【Java】05—排序演算法總結
- 2022 年 9 月 4 日
- 筆記
- 數據結構與演算法【Java】
前言
數據 data 結構(structure)是一門 研究組織數據方式的學科，有了程式語言也就有了數據結構.學好數據結構才可以編寫出更加漂亮,更加有效率的程式碼。
- 要學習好數據結構就要多多考慮如何將生活中遇到的問題,用程式去實現解決.
- 程式 = 數據結構 + 演算法
- 數據結構是演算法的基礎, 換言之，想要學好演算法，需要把數據結構學到位
我會用數據結構與演算法【Java】這一系列的部落格記錄自己的學習過程，如有遺留和錯誤歡迎大家提出，我會第一時間改正！！！
註：數據結構與演算法【Java】這一系列的部落格參考於B站尚矽谷的影片，影片原地址為【尚矽谷】數據結構與演算法（Java數據結構與演算法）
上一篇文章數據結構與演算法【Java】04—遞歸
接下來進入正題!
數據結構與演算法【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、時間複雜度
1.一般情況下， 演算法中的基本操作語句的重複執行次數是問題規模 n 的某個函數，用 T(n)表示，若有某個輔
助函數 f(n)，使得當 n 趨近於無窮大時，T(n) / f(n) 的極限值為不等於零的常數，則稱 f(n)是 T(n)的同數量級函數。
記作 T(n)= Ｏ( f(n) )，稱Ｏ( f(n) ) 為演算法的漸進時間複雜度，簡稱時間複雜度。
- T(n) 不同，但時間複雜度可能相同。 如：T(n)=n²+7n+6 與 T(n)=3n²+2n+2 它們的 T(n) 不同，但時間複雜
度相同，都為 O(n² )。 - 計算時間複雜度的方法：
（1） 用常數 1 代替運行時間中的所有加法常數 T(n)=n²+7n+6 => T(n)=n²+7n+1
（2）修改後的運行次數函數中，只保留最高階項 T(n)=n²+7n+1 => T(n) = n²
（3）去除最高階項的係數 T(n) = n² => T(n) = n² => O(n²)
3.4、常見的時間複雜度
- 常數階O(1)
- 對數階O(log2n)
- 線性階O(n)
- 線性對數階O(nlog2n)
- 平方階O(n^2)
- 立方階O(n^3)
- k次方階O(n^k)
- 指數階O(2^n)
說明：
- 常見的演算法時間複雜度由小到大依次為：Ο(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(n²) 就更容易理解了，如果把 O(n) 的程式碼再嵌套循環一遍，它的時間複雜度就是 O(n²)，這段程式碼其實就是嵌套了2層n循環，它的時間複雜度就是 O(n*n)，即 O(n²) 如果將其中一層循環的n改成m，那它的時間複雜度就變成了 O(m*n)
6.立方階O(n^3)、 k次方階O(n^k)
O(n³)相當於三層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(n²)
//定義一個臨時變數
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(n²)
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==false
break;
} 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(n²)
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==false
break;
} else {
flag = false;//重置flag,進行下一次判斷
}
}
}
}
結果展示：
測試冒泡排序O(n²）的速度
為了測試冒泡排序O(n²）的速度，我們隨機生成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 交換
- 選擇排序一共有 數組大小 – 1（
動態圖
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和minIndex
min = arr[j];
}
}
//交換，將最小值依次放在最前面
//優化：如果假定的最小值就是真實的最小值，那麼就不進行交換（這裡假定的最小值是上一輪交換後的下一個值）
if (minIndex != i){
arr[minIndex] = arr[i];
arr[i] = min;
}
//System.out.println("第"+(i+1)+"輪後");
//System.out.println(Arrays.toString(arr));
}
}
}
結果展示
測試選擇排序O(n²）的速度
測試方法同冒泡排序中的方法，我們在測試之前通過分析可以得出選擇排序交換是找到最小（大）值才進行交換，而冒泡排序是相鄰元素之間進行比較交換，所以選擇排序的交換次數應該比冒泡排序少，速度應該更快。
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(n²）的速度
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 -= gap
for (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;
}
}
//(二)
//把有剩餘數據的一邊的數據依次全部填充到temp
while( i <= mid) { //左邊的有序序列還有剩餘的元素，就全部填充到temp
temp[t] = arr[i];
t += 1;
i += 1;
}
while( j <= right) { //右邊的有序序列還有剩餘的元素，就全部填充到temp
temp[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 = 7
while(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，顧
名思義，它是通過鍵值的各個位的值，將要排序的元素分配至某些「桶」中，達到排序的作用
- 基數排序法是屬於穩定性的排序，基數排序法的是效率高的 穩定性排序法
- 基數排序(Radix Sort)是桶排序的擴展
- 基數排序是 1887 年赫爾曼·何樂禮發明的。它是這樣實現的：將整數按位數切割成不同的數字，然後按每個
位數分別比較。
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++) {
// 取出元素放入到arr
arr[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++) {
// 取出元素放入到arr
arr[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]之前，
則稱這種排序演算法是穩定的；否則稱為不穩定的]
- 有負數的數組，我們不用基數排序來進行排序, 如果要支援負數，參考: //code.i-harness.com/zh-CN/q/e98fa9
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、堆排序過程演示
堆排序的基本思想是：
- 將待排序序列構造成一個大根堆
- 此時，整個序列的最大值就是堆頂的根節點。
- 將其與末尾元素進行交換，此時末尾就為最大值。
- 然後將剩餘 n-1 個元素重新構造成一個堆，這樣會得到 n 個元素的次小值。如此反覆執行，便能得到一個有序
序列了。
步驟圖解
要求：給你一個數組 {4,6,8,5,9} , 要求使用堆排序法，將數組升序排序。
- 步驟一 構造初始堆。將給定無序序列構造成一個大根堆（一般升序採用大根堆，降序採用小根堆)。
- 原始的數組 [4, 6, 8, 5, 9]
- .假設給定無序序列結構如下
- .此時我們從最後一個非葉子結點開始（葉結點自然不用調整，第一個非葉子結點
arr.length/2-1=5/2-1=1，也就是下面的 6 結點），從左至右，從下至上進行調整。
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&&num[i]<num[left])
i=left;
if(right<end&&num[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: 佔用額外記憶體
到這裡關於十大排序演算法的知識到這裡就結束了，最後推薦一個數據結構動態可視化的網站幫助大家學習數據結構與演算法//visualgo.net/zh，
排序演算法在數據結構與演算法中十分重要，雖然有一些排序演算法晦澀難懂，但是演算法學習是一個持續的過程，大家一定不要放棄
，相信在大家的不斷學習過程中一定能將這些演算法掌握，希望這篇文章對大家學習有所幫助(๑•̀ㅂ•́)و✧
