第 7 章排序算法

1、排序算法介紹

1.1、排序算法的簡介

排序也稱排序算法(Sort Algorithm)，排序是将一組資料，依指定的順序進行排列的過程。

1.2、排序算法的分類

内部排序：指将需要處理的所有資料都加載到内部存儲器(記憶體)中進行排序。
外部排序法：資料量過大，無法全部加載到記憶體中，需要借助外部存儲(檔案等)進行排序。
常見的排序算法分類

第 7 章排序算法第 7 章排序算法

2、算法的複雜度

2.1、時間複雜度的度量方法

事後統計的方法：這種方法可行, 但是有兩個問題：
- 一是要想對設計的算法的運作性能進行評測，需要實際運作該程式；
- 二是所得時間的統計量依賴于計算機的硬體、軟體等環境因素, 這種方式，要在同一台計算機的相同狀态下運作，才能比較哪個算法速度更快。
事前估算的方法：通過分析某個算法的時間複雜度來判斷哪個算法更優

2.2、時間頻度

基本介紹時間頻度：一個算法花費的時間與算法中語句的執行次數成正比例，哪個算法中語句執行次數多，它花費時間就多。一個算法中的語句執行次數稱為語句頻度或時間頻度。記為 T(n)。 [舉例說明]
舉例說明-基本案例：比如計算 1-100 所有數字之和，我們設計兩種算法：

第 7 章排序算法第 7 章排序算法

舉例說明-忽略常數項：
- 2n+20 和 2n 随着 n 變大，執行曲線無限接近, 20 可以忽略
- 3n+10 和 3n 随着 n 變大，執行曲線無限接近, 10 可以忽略

第 7 章排序算法第 7 章排序算法

舉例說明-忽略低次項：
- 2n^2+3n+10 和 2n^2 随着 n 變大, 執行曲線無限接近, 可以忽略 3n+10
- n^2+5n+20 和 n^2 随着 n 變大,執行曲線無限接近, 可以忽略 5n+20

第 7 章排序算法第 7 章排序算法

舉例說明-忽略系數：
- 随着 n 值變大， 5n^2+7n 和 3n^2 + 2n ，執行曲線重合, 說明這種情況下, 5 和 3 可以忽略。
- 而 n^3+5n 和 6n^3+4n ，執行曲線分離，說明多少次方式關鍵

第 7 章排序算法第 7 章排序算法

2.3、時間複雜度

一般情況下，算法中的基本操作語句的重複執行次數是問題規模 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 代替運作時間中的所有加法常數 T(n)=n²+7n+6 => T(n)=n²+7n+1
- 修改後的運作次數函數中，隻保留最高階項 T(n)=n²+7n+1 => T(n) = n²
- 去除最高階項的系數 T(n) = n² => T(n) = n² => O(n²)

2.4、常見的時間複雜度

2.4.1、常見時間複雜度概述

常見時間複雜度
- 常數階 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 的不斷增大，上述時間複雜度不斷增大，算法的執行效率越低
- 從圖中可見，我們應該盡可能避免使用指數階的算法

第 7 章排序算法第 7 章排序算法

2.4.2、常數階 O(1)

無論代碼執行了多少行，隻要是沒有循環等複雜結構，那這個代碼的時間複雜度就都是O(1)
代碼在執行的時候，它消耗的時候并不随着某個變量的增長而增長，那麼無論這類代碼有多長，即使有幾萬幾十萬行，都可以用O(1)來表示它的時間複雜度。

第 7 章排序算法第 7 章排序算法

2.4.3、對數階 O(log2n)

第 7 章排序算法第 7 章排序算法

2.4.4、線性階 O(n)

說明：這段代碼，for循環裡面的代碼會執行n遍，是以它消耗的時間是随着n的變化而變化的，是以這類代碼都可以用O(n)來表示它的時間複雜度

第 7 章排序算法第 7 章排序算法

2.4.5、線性對數階 O(nlogN)

說明：線性對數階O(nlogN) 其實非常容易了解，将時間複雜度為O(logn)的代碼循環N遍的話，那麼它的時間複雜度就是 n * O(logN)，也就是了O(nlogN)

第 7 章排序算法第 7 章排序算法

2.4.6、平方階 O(n²)

說明：平方階O(n²) 就更容易了解了，如果把 O(n) 的代碼再嵌套循環一遍，它的時間複雜度就是 O(n²)，這段代碼其實就是嵌套了2層n循環，它的時間複雜度就是 O(n*n)，即 O(n²) 如果将其中一層循環的n改成m，那它的時間複雜度就變成了 O(m*n)

第 7 章排序算法第 7 章排序算法

2.4.7、其他階

立方階 O(n³)、 K 次方階 O(n^k)
說明：參考上面的 O(n²) 去了解就好了， O(n³)相當于三層 n 循環，其它的類似

2.5、平均和最壞時間複雜度

平均時間複雜度是指所有可能的輸入執行個體均以等機率出現的情況下，該算法的運作時間。
最壞情況下的時間複雜度稱最壞時間複雜度。一般讨論的時間複雜度均是最壞情況下的時間複雜度。這樣做的原因是：最壞情況下的時間複雜度是算法在任何輸入執行個體上運作時間的界限，這就保證了算法的運作時間不會比最壞情況更長。
平均時間複雜度和最壞時間複雜度是否一緻，和算法有關(如圖)。

第 7 章排序算法第 7 章排序算法

2.6、算法的空間複雜度

類似于時間複雜度的讨論，一個算法的空間複雜度(Space Complexity)定義為該算法所耗費的存儲空間，它也是問題規模 n 的函數。
空間複雜度(Space Complexity)是對一個算法在運作過程中臨時占用存儲空間大小的量度。有的算法需要占用的臨時工作單元數與解決問題的規模 n 有關，它随着 n 的增大而增大，當 n 較大時，将占用較多的存儲單元，例如快速排序和歸并排序算法, 基數排序就屬于這種情況
在做算法分析時，主要讨論的是時間複雜度。從使用者使用體驗上看，更看重的程式執行的速度。一些緩存産品(redis, memcache)和算法(基數排序)本質就是用空間換時間

3、冒泡排序

3.1、基本介紹

冒泡排序（Bubble Sorting）的基本思想是：通過對待排序序列從前向後（從下标較小的元素開始），依次比較相鄰元素的值，若發現逆序則交換，使值較大的元素逐漸從前移向後部，就象水底下的氣泡一樣逐漸向上冒。
優化：因為排序的過程中，各元素不斷接近自己的位置，如果一趟比較下來沒有進行過交換，就說明序列有序，是以要在排序過程中設定一個标志 flag 判斷元素是否進行過交換。進而減少不必要的比較。 (這裡說的優化，可以在冒泡排序寫好後，再進行)

3.2、冒泡排序圖解

第一趟：
- 從數組 arr 第一個元素開始，與其後面一個元素比較大小
- 如果 arr[i] > arr[i+1] ，則交換，将大的元素換到後面去
- 由于是目前元素與其後面一個元素比較大小，是以隻需要執行 arr.length - 1 次循環
第二趟：
- 從數組 arr 第一個元素開始，與其後面一個元素比較大小
- 由于第一趟排序完成，數組最後一個元素已是最大元素，是以隻需要執行 arr.length - 1 - 1 次循環
啥時候完成？下面兩個條件滿足任意一個即可：
- 當其中有一趟排序沒有元素交換位置時，說明數組已經有序
- 或：按照上述流程，跑完第 arr.length - 1 趟之後
  - 這樣來想：5 個元素的數組，最多隻需要跑 4 趟
  - 為什麼最多隻需要跑 4 趟？因為跑完 4 趟之後，數組第二個元素已經成為了數組第二小的元素，那麼數組自然就是有序數組
  - 即數組長度如果為 n ，那麼則需要跑 n - 1 趟
總結：兩層 for 循環
- 第一層 for 循環控制走多少趟：for (int i = 0; i < arr.length - 1; i++) {
- 第二層 for 循環實作針對該趟循環，進行冒泡：for (int j = 0; j < arr.length - 1 - i; j++) {
僞代碼：

for (int i = 0; i < ; i++) {
    for (int j = 0; j < arr.length - 1 - i; j++) {
        // 執行冒泡操作
    }
    if(/* 該趟沒有交換 */) {
        // 數組已然有序，跳出循環
    }
}

第 7 章排序算法第 7 章排序算法

3.3、代碼實作

3.3.1、了解冒泡排序

上面的例子不好，我們把數組改成：int arr[] = { 3, 9, -1, 10, -2 }; 這樣更能說明冒泡排序的特點

public static void main(String[] args) {
	int arr[] = { 3, 9, -1, 10, -2 };
	int temp;

	// 為了容量了解，我們把冒泡排序的演變過程，給大家展示
	System.out.println("排序前");
	System.out.println(Arrays.toString(arr));

	// 第一趟排序，就是将最大的數排在倒數第一位
	for (int j = 0; j < arr.length - 1; j++) {
		// 如果前面的數比後面的數大，則交換
		if (arr[j] > arr[j + 1]) {
			temp = arr[j];
			arr[j] = arr[j + 1];
			arr[j + 1] = temp;
		}
	}
	System.out.println("第一趟排序後的數組");
	System.out.println(Arrays.toString(arr));

	// 第二趟排序，就是将第二大的數排在倒數第二位
	for (int j = 0; j < arr.length - 1 - 1; j++) {
		// 如果前面的數比後面的數大，則交換
		if (arr[j] > arr[j + 1]) {
			temp = arr[j];
			arr[j] = arr[j + 1];
			arr[j + 1] = temp;
		}
	}
	System.out.println("第二趟排序後的數組");
	System.out.println(Arrays.toString(arr));

	// 第三趟排序，就是将第三大的數排在倒數第三位
	for (int j = 0; j < arr.length - 1 - 2; j++) {
		// 如果前面的數比後面的數大，則交換
		if (arr[j] > arr[j + 1]) {
			temp = arr[j];
			arr[j] = arr[j + 1];
			arr[j + 1] = temp;
		}
	}
	System.out.println("第三趟排序後的數組");
	System.out.println(Arrays.toString(arr));

	// 第四趟排序，就是将第4大的數排在倒數第4位
	for (int j = 0; j < arr.length - 1 - 3; j++) {
		// 如果前面的數比後面的數大，則交換
		if (arr[j] > arr[j + 1]) {
			temp = arr[j];
			arr[j] = arr[j + 1];
			arr[j + 1] = temp;
		}
	}
	System.out.println("第四趟排序後的數組");
	System.out.println(Arrays.toString(arr));
}

程式運作結果

排序前
[3, 9, -1, 10, -2]
第一趟排序後的數組
[3, -1, 9, -2, 10]
第二趟排序後的數組
[-1, 3, -2, 9, 10]
第三趟排序後的數組
[-1, -2, 3, 9, 10]
第四趟排序後的數組
[-2, -1, 3, 9, 10]

3.3.2、編寫冒泡排序

測試極端情況

public static void main(String[] args) {
	int arr[] = { 1, 2, 3, 4, 5, 6 };

	// 為了容量了解，我們把冒泡排序的演變過程，給大家展示
	System.out.println("排序前");
	System.out.println(Arrays.toString(arr));

	bubbleSort(arr);
}

// 将前面額冒泡排序算法，封裝成一個方法
public static void bubbleSort(int[] arr) {
	// 冒泡排序 的時間複雜度 O(n^2), 自己寫出
	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) { // 在一趟排序中，一次交換都沒有發生過
			break;
		} else {
			flag = false; // 重置flag!!!, 進行下次判斷
		}
	}
}

程式運作結果

排序前
[1, 2, 3, 4, 5, 6]
第1趟排序後的數組
[1, 2, 3, 4, 5, 6]

3.3.3、測試冒泡排序性能

測試代碼

public static void main(String[] args) {

	// 測試一下冒泡排序的速度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 date1 = new Date();
	SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
	String date1Str = simpleDateFormat.format(date1);
	System.out.println("排序前的時間是=" + date1Str);

	// 測試冒泡排序
	bubbleSort(arr);

	Date date2 = new Date();
	String date2Str = simpleDateFormat.format(date2);
	System.out.println("排序後的時間是=" + date2Str);

}

// 将前面額冒泡排序算法，封裝成一個方法
public static void bubbleSort(int[] arr) {
	// 冒泡排序 的時間複雜度 O(n^2), 自己寫出
	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;
			}
		}
		if (!flag) { // 在一趟排序中，一次交換都沒有發生過
			break;
		} else {
			flag = false; // 重置flag!!!, 進行下次判斷
		}
	}
}

程式運作結果

排序前的時間是=2020-07-15 11:44:08
排序後的時間是=2020-07-15 11:44:16

4、選擇排序

4.1、選擇排序基本介紹

選擇式排序也屬于内部排序法，是從欲排序的資料中，按指定的規則選出某一進制素，再依規定交換位置後達到排序的目的。

4.2、選擇排序思想

選擇排序（select sorting）也是一種簡單的排序方法。它的基本思想是（n 是數組大小）：
- 第一次從 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 次，得到一個按排序碼從小到大排列的有序序列。

4.3、選擇排序圖解

選擇排序流程：
- 第一次循環，預設 arr[0] 是最小的元素，将其與 arr[1]~arr[n-1] 進行比較，找到最小的元素，并與 arr[0] 的位置位置
- 第二次循環，預設 arr[1] 是最小的元素，将其與 arr[2]~arr[n-1] 進行比較，找到最小的元素，并與 arr[1] 的位置位置
- 第 i 次循環，預設 arr[i] 是最小的元素，将其與 arr[i+1]~arr[n-1] 進行比較，找到最小的元素，并與 arr[i] 的位置位置
- 直到循環執行 n - 1 次
總結：兩層 for 循環
- 第一層 for 循環控制走多少趟：for (int i = 0; i < arr.length - 1; i++) {
  - 從數組第一個元素開始，因為每次都是拿目前元素 arr[j] 和其後一個元素 arr[j+1] 進行比較
  - 到數組倒數第二個元素結束，将 arr[arr.length - 2] 與 arr[arr.length - 1] 進行比較後，數組就已經是有序數組
  - 如果數組大小為 n ，那麼執行完第 n - 1 趟時，數組就已經是有序數組
- 第二層 for 循環控制從第幾個元素開始執行選擇排序：for (int j = i + 1; j < arr.length; j++)
  - 每次進入第二層 for 循環時，先假設目前元素 arr[i] 是最小的元素：min = arr[i]; ，并記錄最小元素的下标：index = i;
  - 然後依次和其後面的元素 arr[j] 比較，如果找到比 arr[i] 小的元素，則更新最小值和最小值的索引：min = arr[j]; index = j ;

第 7 章排序算法第 7 章排序算法

4.4、代碼實作

4.4.1、了解選擇排序

一步一步了解選擇排序算法

//選擇排序
public class SelectSort {

	public static void main(String[] args) {
        
		int[] arr = { 101, 34, 119, 1 };
		selectSort(arr);
        
	}

	// 選擇排序
	public static void selectSort(int[] arr) {
        
		// 使用逐漸推導的方式來，講解選擇排序
		// 第1輪
		// 原始的數組 ： 101, 34, 119, 1
		// 第一輪排序 : 1, 34, 119, 101
		// 算法 先簡單--》 做複雜， 就是可以把一個複雜的算法，拆分成簡單的問題-》逐漸解決

		// 第1輪
		int minIndex = 0;
		int min = arr[0];
		for (int j = 0 + 1; j < arr.length; j++) {
			if (min > arr[j]) { // 說明假定的最小值，并不是最小
				min = arr[j]; // 重置min
				minIndex = j; // 重置minIndex
			}
		}
		// 将最小值，放在arr[0], 即交換
		if (minIndex != 0) {
			arr[minIndex] = arr[0];
			arr[0] = min;
		}
		System.out.println("第1輪後~~");
		System.out.println(Arrays.toString(arr));// 1, 34, 119, 101

		// 第2輪
		minIndex = 1;
		min = arr[1];
		for (int j = 1 + 1; j < arr.length; j++) {
			if (min > arr[j]) { // 說明假定的最小值，并不是最小
				min = arr[j]; // 重置min
				minIndex = j; // 重置minIndex
			}
		}
		// 将最小值，放在arr[0], 即交換
		if (minIndex != 1) {
			arr[minIndex] = arr[1];
			arr[1] = min;
		}
		System.out.println("第2輪後~~");
		System.out.println(Arrays.toString(arr));// 1, 34, 119, 101

		// 第3輪
		minIndex = 2;
		min = arr[2];
		for (int j = 2 + 1; j < arr.length; j++) {
			if (min > arr[j]) { // 說明假定的最小值，并不是最小
				min = arr[j]; // 重置min
				minIndex = j; // 重置minIndex
			}
		}
		// 将最小值，放在arr[0], 即交換
		if (minIndex != 2) {
			arr[minIndex] = arr[2];
			arr[2] = min;
		}
		System.out.println("第3輪後~~");
		System.out.println(Arrays.toString(arr));// 1, 34, 101, 119
	}

}

程式運作結果

第1輪後~~
[1, 34, 119, 101]
第2輪後~~
[1, 34, 119, 101]
第3輪後~~
[1, 34, 101, 119]

4.4.2、編寫選擇排序

編寫選擇排序算法

//選擇排序
public class SelectSort {

	public static void main(String[] args) {
		int[] arr = { 101, 34, 119, 1 };
		selectSort(arr);
	}

	// 選擇排序
	public static void selectSort(int[] arr) {

		// 在推導的過程，我們發現了規律，是以，可以使用for來解決
		// 選擇排序時間複雜度是 O(n^2)
		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]) { // 說明假定的最小值，并不是最小
					min = arr[j]; // 重置min
					minIndex = j; // 重置minIndex
				}
			}

			// 将最小值，放在arr[0], 即交換
			if (minIndex != i) {
				arr[minIndex] = arr[i];
				arr[i] = min;
			}

			System.out.println("第" + (i + 1) + "輪後~~");
			System.out.println(Arrays.toString(arr));
		}

	}
}

程式運作結果

第1輪後~~
[1, 34, 119, 101]
第2輪後~~
[1, 34, 119, 101]
第3輪後~~
[1, 34, 101, 119]

4.4.3、測試選擇排序性能

測試代碼

//選擇排序
public class SelectSort {

	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) 數
		}
		
		Date data1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(data1);
		System.out.println("排序前的時間是=" + date1Str);

		selectSort(arr);

		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序前的時間是=" + date2Str);

	}

	// 選擇排序
	public static void selectSort(int[] arr) {

		// 在推導的過程，我們發現了規律，是以，可以使用for來解決
		// 選擇排序時間複雜度是 O(n^2)
		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]) { // 說明假定的最小值，并不是最小
					min = arr[j]; // 重置min
					minIndex = j; // 重置minIndex
				}
			}

			// 将最小值，放在arr[0], 即交換
			if (minIndex != i) {
				arr[minIndex] = arr[i];
				arr[i] = min;
			}
		}

	}
}

程式運作結果

排序前的時間是=2020-07-15 19:59:19
排序前的時間是=2020-07-15 19:59:20

4.5、總結

由于選擇排序算法在最内層的 for 循環中，滿足 if (min > arr[j]) { 條件後，隻需要記錄最小值和最小值在數組中的索引，無需像冒泡排序那樣每次都要執行交換操作，是以選擇排序算法的執行速度比冒泡排序算法快一些

5、插入排序

5.1、插入排序基本介紹

插入式排序屬于内部排序法，是對于欲排序的元素以插入的方式找尋該元素的适當位置，以達到排序的目的。

5.2、插入排序思想

插入排序（Insertion Sorting）的基本思想是：把 n 個待排序的元素看成為一個有序表和一個無序表
開始時有序表中隻包含一個元素，無序表中包含有 n-1 個元素，排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼進行比較，将它插入到有序表中的适當位置，使之成為新的有序表

5.3、插入排序圖解

插入排序邏輯：
- 首先，将數組分為兩個數組，前部分有序數組，後部分是無序數組，我們的目的就是一點一點取出無序數組中的值，将其放到有序數組中區
- 第一趟：arr[0] 作為有序數組的元素，arr[1] 作為無序數組中第一個元素，将 arr[1] 與 arr[0] 比較，目标是将 arr[1] 插入到有序數組中
- 第一趟：arr[0] 和 arr[1] 作為有序數組的元素，arr[2] 作為無序數組中第一個元素，将 arr[2] 與 arr[0] 和 arr[1] 比較，目标是将 arr[2] 插入到有序數組中
- 第 i 趟：arr[0]~arr[i] 作為有序數組的元素，arr[i+1] 作為無序數組中第一個元素，将 arr[i+1] 與 arr[0]~arr[i] 比較，目标是将 arr[i+1] 插入到有序數組中
- 第 n-1 趟：此時有序數組為 arr[0]~arr[n-2] ，無序數組為 arr[n-1] ，将無序數組中最後一個元素插入到有序數組中即可
- 如何進行插入？
  - 假設有個指針（index），指向無序數組中的第一個元素，即 arr[index] 是無序數組中的第一個元素，我們定義一個變量來存儲該值：int insertVal = arr[index];，現在要将其插入到前面的有序數組中
  - 将 index 前移一步，則指向有序數組最後一個元素，我們定義一個新的變量來存儲該指針：insertIndex = index - 1; ，即 arr[insertIndex] 是有序數組最後一個元素
  - 我們需要找到一個比 insertVal 小的值，并将 insertVal 插入在該值後面：
    - 如果 insertVal > arr[insertIndex] ，執行插入
    - 如果 insertVal < arr[insertIndex] ，将有序數組後移，騰出插入空間，insertIndex 指針前移，再看看前一個元素滿不滿足條件，直到找到插入位置
    - 即循環終止條件為找到插入位置，又分為兩種情況：
      - 在有序數組中間找到插入位置
      - insertVal 比有序數組中所有的數都小，插入在數組第一個位置（insertIndex = 0 的情況）
總結：兩層循環
- for 循環控制走多少趟：for(int i = 1; i < arr.length; i++) { ，從數組第一個元素開始到數組最後一個元素結束
- while 循環不斷将指針前移，在有序數組中尋找插入位置，并執行插入：
  
  while (insertIndex >= 0 && insertVal < arr[insertIndex]) {

第 7 章排序算法第 7 章排序算法

5.4、代碼實作

5.4.1、了解插入排序

了解插入排序算法

public class InsertSort {

	public static void main(String[] args) {
        
		int[] arr = { 101, 34, 119, 1 };
		insertSort(arr);

	}

	// 插入排序
	public static void insertSort(int[] arr) {

		// 使用逐漸推導的方式來講解，便利了解
		// 第1輪 {101, 34, 119, 1}; => {34, 101, 119, 1}

		// {101, 34, 119, 1}; => {101,101,119,1}
		// 定義待插入的數
		int insertVal = arr[1];
		int insertIndex = 1 - 1; // 即arr[1]的前面這個數的下标

		// 給insertVal 找到插入的位置
		// 說明
		// 1. insertIndex >= 0 保證在給insertVal 找插入位置，不越界
		// 2. insertVal < arr[insertIndex] 待插入的數，還沒有找到插入位置
		// 3. 就需要将 arr[insertIndex] 後移
		while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
			arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
			insertIndex--;
		}
		// 當退出while循環時，說明插入的位置找到, insertIndex + 1
		// 舉例：了解不了，我們一會 debug
		arr[insertIndex + 1] = insertVal;

		System.out.println("第1輪插入");
		System.out.println(Arrays.toString(arr));

		// 第2輪
		insertVal = arr[2];
		insertIndex = 2 - 1;

		while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
			arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
			insertIndex--;
		}

		arr[insertIndex + 1] = insertVal;
		System.out.println("第2輪插入");
		System.out.println(Arrays.toString(arr));

		// 第3輪
		insertVal = arr[3];
		insertIndex = 3 - 1;

		while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
			arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
			insertIndex--;
		}

		arr[insertIndex + 1] = insertVal;
		System.out.println("第3輪插入");
		System.out.println(Arrays.toString(arr));

	}

}

程式運作結果

第1輪插入
[34, 101, 119, 1]
第2輪插入
[34, 101, 119, 1]
第3輪插入
[1, 34, 101, 119]

5.4.2、編寫插入排序

編寫插入排序算法

public class InsertSort {

	public static void main(String[] args) {
        
		int[] arr = { 101, 34, 119, 1 };
		insertSort(arr);

	}

	// 插入排序
	public static void insertSort(int[] arr) {
		int insertVal = 0;
		int insertIndex = 0;
		//使用for循環來把代碼簡化
		for(int i = 1; i < arr.length; i++) {
			//定義待插入的數
			insertVal = arr[i];
			insertIndex = i - 1; // 即arr[1]的前面這個數的下标
	
			// 給insertVal 找到插入的位置
			// 說明
			// 1. insertIndex >= 0 保證在給insertVal 找插入位置，不越界
			// 2. insertVal < arr[insertIndex] 待插入的數，還沒有找到插入位置
			// 3. 就需要将 arr[insertIndex] 後移
			while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
				arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
				insertIndex--;
			}
			// 當退出while循環時，說明插入的位置找到, insertIndex + 1
			// 因為我們找到的元素，即下标為 insertIndex 的元素值比 insertVal 小
             // 是以我們要将 insertVal 插入到 insertIndex + 1 的位置
			arr[insertIndex + 1] = insertVal;
			System.out.println("第"+i+"輪插入");
			System.out.println(Arrays.toString(arr));
		}

	}

}

程式運作結果

第1輪插入
[34, 101, 119, 1]
第2輪插入
[34, 101, 119, 1]
第3輪插入
[1, 34, 101, 119]

5.4.3、測試插入排序性能

測試插入排序性能

public class InsertSort {

	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);

	}

	// 插入排序
	public static void insertSort(int[] arr) {
		int insertVal = 0;
		int insertIndex = 0;
		//使用for循環來把代碼簡化
		for(int i = 1; i < arr.length; i++) {
			//定義待插入的數
			insertVal = arr[i];
			insertIndex = i - 1; // 即arr[1]的前面這個數的下标
	
			// 給insertVal 找到插入的位置
			// 說明
			// 1. insertIndex >= 0 保證在給insertVal 找插入位置，不越界
			// 2. insertVal < arr[insertIndex] 待插入的數，還沒有找到插入位置
			// 3. 就需要将 arr[insertIndex] 後移
			while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
				arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
				insertIndex--;
			}
			// 當退出while循環時，說明插入的位置找到, insertIndex + 1
			// 舉例：了解不了，我們一會 debug
			//這裡我們判斷是否需要指派
			arr[insertIndex + 1] = insertVal;
		}

	}

}

程式運作結果

插入排序前
排序前的時間是=2020-07-15 21:49:48
排序前的時間是=2020-07-15 21:49:50

5.5、總結

插入排序在尋找插入位置時，需要對數組元素進行整體挪位，是以效率比選擇排序稍低

6、希爾排序

6.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}

6.2、希爾排序基本介紹

希爾排序是希爾（Donald Shell）于 1959 年提出的一種排序算法。希爾排序也是一種插入排序，它是簡單插入排序經過改進之後的一個更高效的版本，也稱為縮小增量排序。

6.3、希爾排序基本思想

希爾排序按照增量将數組進行分組，對每組使用直接插入排序算法排序；随着增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至 1 時，整個檔案恰被分成一組，算法便終止

6.4、希爾排序圖解（交換法）

第一次：gap = arr.length/5 = 5 ，将數組分為五組，每個數組元素的索引相差 5
- 如何完成第一次的排序？
  - 仔細想想，我們需要用一次循環将每組中的元素排序
  - 總共有五組，我們又需要一次循環
  - 是以完成每次排序，需要兩層循環
- 程式代碼如下，把 i ，j 都看作是輔助指針：
  - i 與 j 配合使用，可以将指針從數組第一個元素，移動至最後一個元素，目的：把數組周遊一遍
  - j 與 i 配合使用，每次都從數組索引 i 處往前周遊，每次向前移動 gap 個位置，然後進行交換（冒泡排序的意思）：看看前面的元素有沒有比我的值大，如果前面的元素比我的值大，我就要和他交換位置，跑到前面去
```
// 希爾排序的第1輪排序
// 因為第1輪排序，是将10個資料分成了 5組
for (int i = 5; i < arr.length; i++) {
    // 周遊各組中所有的元素(共5組，每組有2個元素), 步長5
    for (int j = i - 5; j >= 0; j -= 5) {
        // 如果目前元素大于加上步長後的那個元素，說明交換
        if (arr[j] > arr[j + 5]) {
            temp = arr[j];
            arr[j] = arr[j + 5];
            arr[j + 5] = temp;
        }
    }
}
           
```
第二次：gap = gap /2 = 2; ，将數組分為兩組，每個數組元素的索引相差 2
- 第一組：
  - i = 2 時，數組從索引 2 處往前周遊，間隔為 2 ：将 arr[0]、arr[2] 排序
  - i = 4 時，數組從索引 4 處往前周遊，間隔為 2 ：将 arr[0]、arr[2]、arr[4] 排序
  - i = 6 時，數組從索引 6 處往前周遊，間隔為 2 ：将 arr[0]、arr[2]、arr[4]、arr[6] 排序
  - i = 8 時，數組從索引 8 處往前周遊，間隔為 2 ：将 arr[0]、arr[2]、arr[4]、arr[6]、arr[8] 排序
- 第二組：
  - i = 3 時，數組從索引 3 處往前周遊，間隔為 2 ：将 arr[1]、arr[3] 排序
  - i = 5 時，數組從索引 5 處往前周遊，間隔為 2 ：将 arr[1]、arr[3]、arr[5] 排序
  - i = 7 時，數組從索引 7 處往前周遊，間隔為 2 ：将 arr[1]、arr[3]、arr[5]、arr[7] 排序
  - i = 9 時，數組從索引 9 處往前周遊，間隔為 2 ：将 arr[1]、arr[3]、arr[5]、arr[7]、arr[9] 排序

// 希爾排序的第2輪排序
// 因為第2輪排序，是将10個資料分成了 5/2 = 2組
for (int i = 2; i < arr.length; i++) {
    // 周遊各組中所有的元素(共5組，每組有2個元素), 步長5
    for (int j = i - 2; j >= 0; j -= 2) {
        // 如果目前元素大于加上步長後的那個元素，說明交換
        if (arr[j] > arr[j + 2]) {
            temp = arr[j];
            arr[j] = arr[j + 2];
            arr[j + 2] = temp;
        }
    }
}
System.out.println("希爾排序2輪後=" + Arrays.toString(arr));

第三次：gap = gap /2 = 1; ，将數組分為一組，每個數組元素的索引相差 1 ，對于交換法而言，這就是異常冒泡排序
- i = 1 時，數組從索引 1 處往前周遊，間隔為 1 ：将 arr[0]、arr[1] 排序
- i = 2 時，數組從索引 2 處往前周遊，間隔為 1 ：将 arr[0]、arr[1]、arr[2] 排序
- i = 3 時，數組從索引 3 處往前周遊，間隔為 1 ：将 arr[0]、arr[1]、arr[2]、arr[3] 排序
- …

// 希爾排序的第3輪排序
// 因為第3輪排序，是将10個資料分成了 2/2 = 1組
for (int i = 1; i < arr.length; i++) {
    // 周遊各組中所有的元素(共5組，每組有2個元素), 步長5
    for (int j = i - 1; j >= 0; j -= 1) {
        // 如果目前元素大于加上步長後的那個元素，說明交換
        if (arr[j] > arr[j + 1]) {
            temp = arr[j];
            arr[j] = arr[j + 1];
            arr[j + 1] = temp;
        }
    }
}
System.out.println("希爾排序3輪後=" + Arrays.toString(arr));

總結：每次使用循環改變 gap 的值（初始值：數組大小/2 ，之後：gap = gap/2），然後在改變 gap 的循環中嵌套上面的雙層 for 循環

改變 gap ：for (int gap = arr.length / 2; gap > 0; gap /= 2) {
内層循環：實作對每組數組的排序

for (int i = gap; i < arr.length; i++) {
    // 周遊各組中所有的元素(共gap組，每組有？個元素), 步長gap
    for (int j = i - gap; j >= 0; j -= gap) {

希爾排序僞代碼

for (int gap = arr.length / 2; gap > 0; gap /= 2) {
    for (int i = gap; i < arr.length; i++) {
    	// 周遊各組中所有的元素(共gap組，每組有？個元素), 步長gap
    	for (int j = i - gap; j >= 0; j -= gap) {
            // 對每組進行冒泡排序
        }
    }
}

第 7 章排序算法第 7 章排序算法

6.5、代碼實作

6.5.1、了解希爾排序（交換法）

了解基于交換法的希爾排序

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;

		// 希爾排序的第1輪排序
		// 因為第1輪排序，是将10個資料分成了 5組
		for (int i = 5; i < arr.length; i++) {
			// 周遊各組中所有的元素(共5組，每組有2個元素), 步長5
			for (int j = i - 5; j >= 0; j -= 5) {
				// 如果目前元素大于加上步長後的那個元素，說明交換
				if (arr[j] > arr[j + 5]) {
					temp = arr[j];
					arr[j] = arr[j + 5];
					arr[j + 5] = temp;
				}
			}
		}
		System.out.println("希爾排序1輪後=" + Arrays.toString(arr));

		// 希爾排序的第2輪排序
		// 因為第2輪排序，是将10個資料分成了 5/2 = 2組
		for (int i = 2; i < arr.length; i++) {
			// 周遊各組中所有的元素(共5組，每組有2個元素), 步長5
			for (int j = i - 2; j >= 0; j -= 2) {
				// 如果目前元素大于加上步長後的那個元素，說明交換
				if (arr[j] > arr[j + 2]) {
					temp = arr[j];
					arr[j] = arr[j + 2];
					arr[j + 2] = temp;
				}
			}
		}
		System.out.println("希爾排序2輪後=" + Arrays.toString(arr));

		// 希爾排序的第3輪排序
		// 因為第3輪排序，是将10個資料分成了 2/2 = 1組
		for (int i = 1; i < arr.length; i++) {
			// 周遊各組中所有的元素(共5組，每組有2個元素), 步長5
			for (int j = i - 1; j >= 0; j -= 1) {
				// 如果目前元素大于加上步長後的那個元素，說明交換
				if (arr[j] > arr[j + 1]) {
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
		System.out.println("希爾排序3輪後=" + Arrays.toString(arr));

	}
}

程式運作結果

希爾排序1輪後=[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
希爾排序2輪後=[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
希爾排序3輪後=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

6.5.2、編寫希爾排序（交換法）

編寫基于交換法的希爾排序算法

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組，每組有？個元素), 步長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));
		}
        
}

程式運作結果

希爾排序第1輪 =[3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
希爾排序第2輪 =[0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
希爾排序第3輪 =[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

6.5.3、測試希爾排序（交換法）性能

測試基于交換法的希爾排序算法性能

public class ShellSort {

	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 date1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(date1);
		System.out.println("排序前的時間是=" + date1Str);

		shellSort(arr); // 交換式

		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序前的時間是=" + date2Str);

	}

	// 使用逐漸推導的方式來編寫希爾排序
	// 希爾排序時， 對有序序列在插入時采用交換法,
	// 思路(算法) ===> 代碼
	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組，每組有？個元素), 步長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;
					}
				}
			}
		}
	}
    
}

程式運作結果

排序前
排序前的時間是=2020-07-16 10:22:27
排序前的時間是=2020-07-16 10:22:33

分析：由于使用交換法實作希爾排序算法，是以基于交換法的希爾排序算法比簡單選擇排序算法更慢，是以我們一定要編寫基于插入法的希爾排序算法

6.5.4、編寫希爾排序（插入法）

編寫基于插入法的希爾排序算法：
- 記錄目前位置的元素值 int temp = arr[j]; ，從目前元素前一個位置開始，往前尋找，每次移動 gap 個距離
  - 如果 temp < arr[j - gap] ：
    - 将數組元素後移，騰出插入空間：arr[j] = arr[j - gap];
    - 然後繼續往前找：j -= gap;
  - 如果 temp > arr[j - gap] ，找到插入位置，執行插入 arr[j] = temp; ，因為在上一步已經騰出了插入空間，并且将指針 j 前移，是以可直接插入
  - 如果找到數組最前面還是沒有找到插入位置：j - gap < 0 ，則證明 temp 需要插入在數組最前面
- 僅僅就是将之前交換法的冒泡操作替換成了插入操作

public class ShellSort {

	public static void main(String[] args) {

		int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
		
		System.out.println("排序前");
		System.out.println(Arrays.toString(arr));
		
		shellSort(arr);
		
		System.out.println("排序前");
		System.out.println(Arrays.toString(arr));

	}

	// 對交換式的希爾排序進行優化->移位法
	public static void shellSort(int[] arr) {
		// 增量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;
					}
					// temp 比 arr[j - gap] 大，是以需要插入在 j 的位置
					arr[j] = temp;
				}

			}
		}
	}

}

程式運作結果

排序前
[8, 9, 1, 7, 2, 3, 5, 4, 6, 0]
排序前
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

6.5.5、測試希爾排序（插入法）性能

測試基于插入法的希爾排序算法性能

public class ShellSort {

	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 date1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(date1);
		System.out.println("排序前的時間是=" + date1Str);

		shellSort(arr); // 交換式

		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序前的時間是=" + date2Str);

	}

	// 對交換式的希爾排序進行優化->移位法
	public static void shellSort(int[] arr) {
		// 增量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;
				}

			}
		}
	}

}

程式運作結果：1s 都不到，果然快啊

排序前
排序前的時間是=2020-07-16 11:02:20
排序前的時間是=2020-07-16 11:02:20

八百萬個資料的測試結果

排序前
排序前的時間是=2020-07-16 14:38:55
排序前的時間是=2020-07-16 14:38:57

7、快速排序

7.1、快排簡介

快速排序是由東尼·霍爾所發展的一種排序算法。在平均狀況下，排序 n 個項目要 Ο(nlogn) 次比較。在最壞狀況下則需要 Ο(n2) 次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他 Ο(nlogn) 算法更快，因為它的内部循環（inner loop）可以在大部分的架構上很有效率地被實作出來。
快速排序使用分治法（Divide and conquer）政策來把一個串行（list）分為兩個子串行（sub-lists）。
快速排序又是一種分而治之思想在排序算法上的典型應用。本質上來看，快速排序應該算是在冒泡排序基礎上的遞歸分治法。
快速排序的名字起的是簡單粗暴，因為一聽到這個名字你就知道它存在的意義，就是快，而且效率高！它是處理大資料最快的排序算法之一了。
雖然 Worst Case 的時間複雜度達到了 O(n²)，但是人家就是優秀，在大多數情況下都比平均時間複雜度為 O(n logn) 的排序算法表現要更好，可是這是為什麼呢，我也不知道。好在我的強迫症又犯了，查了 N 多資料終于在《算法藝術與資訊學競賽》上找到了滿意的答案：
快速排序的最壞運作情況是 O(n²)，比如說順序數列的快排。但它的平攤期望時間是 O(nlogn)，且 O(nlogn) 記号中隐含的常數因子很小，比複雜度穩定等于 O(nlogn) 的歸并排序要小很多。是以，對絕大多數順序性較弱的随機數列而言，快速排序總是優于歸并排序。

7.2、代碼思路

從數列中挑出一個元素，稱為 “基準”（pivot）;
重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。
在這個分區退出之後，該基準就處于數列的中間位置。這個稱為分區（partition）操作；
遞歸地（recursive）把小于基準值元素的子數列和大于基準值元素的子數列排序；

第 7 章排序算法第 7 章排序算法

快排流程分析

以 {25, 84, 21, 47, 15, 27, 68, 35, 20} 數列為例（下面的流程和上面的動圖其實不太一樣，不過大體思想是一樣的）

第一趟：val = 25; 先取出來儲存着
- {20, 84, 21, 47, 15, 27, 68, 35, 20}
- {20, 84, 21, 47, 15, 27, 68, 35, 84}
- {20, 15, 21, 47, 15, 27, 68, 35, 84}
- {20, 15, 21, 47, 47, 27, 68, 35, 84}
- {20, 15, 21, 25, 47, 27, 68, 35, 84}
第二趟：val = 20; 先取出來儲存着
- {15, 15, 21}
- {15, 20, 21}
以此類推 …

7.3、代碼實作

7.3.1、編寫快排算法

快排代碼

private static void quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int partitionIndex = partition(arr, left, right);
        quickSort(arr, left, partitionIndex - 1);
        quickSort(arr, partitionIndex + 1, right);
    }
}

private static int partition(int[] arr, int left, int right) {
    int pivot = arr[left];
    //終止while循環以後left和right一定相等的
    while (left < right) {
        while (left < right && arr[right] >= pivot) {
            --right;
        }
        arr[left] = arr[right];
        while (left < right && arr[left] <= pivot) {
            ++left;
        }
        arr[right] = arr[left];
    }
    arr[left] = pivot;
    //right可以改為left
    return left;
}

測試代碼

public static void main(String[] args) {
    int[] arr = {25, 84, 21, 47, 15, 27, 68, 35, 20};
    quickSort(arr, 0, arr.length - 1);
    System.out.println(Arrays.toString(arr));
}

程式輸出

arr=[15, 20, 21, 25, 27, 35, 47, 68, 84]

7.3.2、測試快速排序性能

編測試快速排序算法性能

public class QuickSort {

	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 date1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(date1);
		System.out.println("排序前的時間是=" + date1Str);

		quickSort(arr, 0, arr.length - 1); // 交換式

		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序前的時間是=" + date2Str);

	}

	private static void quickSort(int[] arr, int left, int right) {
		if (left < right) {
			int partitionIndex = partition(arr, left, right);
			quickSort(arr, left, partitionIndex - 1);
			quickSort(arr, partitionIndex + 1, right);
		}
	}

	private static int partition(int[] arr, int left, int right) {
		int pivot = arr[left];
		// 終止while循環以後left和right一定相等的
		while (left < right) {
			while (left < right && arr[right] >= pivot) {
				--right;
			}
			arr[left] = arr[right];
			while (left < right && arr[left] <= pivot) {
				++left;
			}
			arr[right] = arr[left];
		}
		arr[left] = pivot;
		// right可以改為left
		return left;
	}
}

程式運作結果：卧槽，八百個資料隻需要 1s ，甚至可能還不到。。。

排序前
排序前的時間是=2020-08-06 18:43:44
排序前的時間是=2020-08-06 18:43:44

8、歸并排序

8.1、歸并排序基本介紹

歸并排序（MERGE-SORT）是利用歸并的思想實作的排序方法，該算法采用經典的分治（divide-and-conquer）政策
分治法将問題分(divide)成一些小的問題然後遞歸求解，而治(conquer)的階段則将分的階段得到的各答案"修補"在一起，即分而治之

8.2、歸并排序思想

分 --> 治

第 7 章排序算法第 7 章排序算法

8.3、歸并排序代碼思路

合并時，其實是拿着原數組（arr）中兩個相鄰的子數組（arr1、arr2）進行合并，我們使用三個指針，來表示兩個子數組在原數組中的位置
- arr[left] ~ arr[mid] 為 arr1
- arr[mid + 1] ~ arr[right] 為 arr2
如何合并？
- 首先，需要一個臨時的 temp 數組，其大小與原數組 arr 一樣
- 定義輔助指針 i 周遊 arr1 ，定義輔助指針 j 周遊 arr2 ，原則就是，把 arr1 和 arr2 中的數往 temp 中放，使得 temp[left] ~ temp[right] 是有序數組
- 最後把 temp 臨時數組中的資料拷貝回原數組中（個人認為，最後一下次再拷貝回去就行。。。）
如何分？
- 向左遞歸拆分：mergeSort(arr, left, mid, temp);
- 向右遞歸拆分：mergeSort(arr, mid + 1, right, temp);

第 7 章排序算法第 7 章排序算法

8.4、代碼實作

8.4.1、編寫歸并排序算法

歸并排序算法實作代碼

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;
		}

	}

}

程式運作結果

歸并排序後=[1, 2, 3, 4, 5, 6, 7, 8]

8.4.2、測試歸并排序性能

測試歸并排序算法的性能

public class MergetSort {

	public static void main(String[] args) {
		
		// 測試快排的執行速度
		// 建立要給80000個的随機的數組
		int[] arr = new int[8000000];
		for (int i = 0; i < 8000000; 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);

		int temp[] = new int[arr.length]; // 歸并排序需要一個額外空間
		mergeSort(arr, 0, arr.length - 1, temp);

		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序前的時間是=" + date2Str);

		// 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;
		}

	}

}

程式運作結果：八百萬資料用了 1s ，也挺快

排序前
排序前的時間是=2020-07-16 16:18:32
排序前的時間是=2020-07-16 16:18:33

8.5、總結

先将數組分為左右兩半，先執行左半邊遞歸：
- 首先執行左遞歸到最深層，條件 if (left < right) 不滿足，開始執行合并，合并 { 8, 4 } 到臨時數組 temp 中，變為有序數組 { 4, 8 } ，再拷貝回原數組 arr 中
- 然後執行最深層的右遞歸，條件 if (left < right) 不滿足，開始執行合并，合并 { 5, 7 } 到臨時數組 temp 中，變為有序數組 { 2, 7 } ，再拷貝回原數組 arr 中
- 合并完後，遞歸回溯至上一節，開始執行合并，合并 { 4, 5, 7, 8 } 到臨時數組 temp 中，變為有序數組 { 4, 5, 7, 8 } ，再拷貝回原數組 arr 中
右左半邊的遞歸也是同樣的道理

第 7 章排序算法第 7 章排序算法

9、基數排序

9.1、基數排序基本介紹

基數排序（radix sort）屬于“配置設定式排序” （distribution sort），又稱“桶子法” （bucket sort）或 bin sort，顧名思義，它是通過鍵值的各個位的值，将要排序的元素配置設定至某些“桶” 中，達到排序的作用
基數排序法是屬于穩定性的排序，基數排序法的是效率高的穩定性排序法
基數排序(Radix Sort)是桶排序的擴充
基數排序是 1887 年赫爾曼· 何樂禮發明的。它是這樣實作的：将整數按位數切割成不同的數字，然後按每個位數分别比較。

9.2、基數排序思想

将所有待比較數值統一為同樣的數位長度，數位較短的數前面補零。
然後，從最低位開始，依次進行一次排序。這樣從最低位排序一直到最高位排序完成以後, 數列就變成一個有序序列。

9.3、基數排序圖解

有 10 個桶，對應編号為 0~9
步驟
- 第一步：根據原數組 arr 中每個元素的個位數，将其依次放入 0~9 号桶中（每個桶從前往後放），放置完畢後，再将桶中的資料依次取出（每個桶從前往後取），放回原數組 arr 中，這樣原數組 arr 中個位數的元素就已經按照順序排好了
- 第二步：根據原數組 arr 中每個元素的十位數，将其依次放入 0~9 号桶中（每個桶從前往後放），放置完畢後，再将桶中的資料依次取出（每個桶從前往後取），放回原數組 arr 中，這樣原數組 arr 中十位數 + 個位數的元素就已經按照順序排好了
- 第三步：根據原數組 arr 中每個元素的百位數，将其依次放入 0~9 号桶中（每個桶從前往後放），放置完畢後，再将桶中的資料依次取出（每個桶從前往後取），放回原數組 arr 中，這樣原數組 arr 中百位數 + 十位數 + 個位數的元素就已經按照順序排好了
- …
何時排序完畢？當數組中最長位數的元素處理完畢，排序完成
桶的容量如何确定？假設數組每個元素位數相同，那麼單個桶最大容量即為數組容量，我們用一個二維數組來表示桶： int[][] bucket = new int[10][arr.length];
我們如何知道每桶中裝了幾個元素？這也需要記錄，用一個一維數組來記錄： int[] bucketElementCounts = new int[10];
總結：
- 假設數組中元素的最長位數為 maxLength ，則處理完 maxLength 位數後，數組排序完畢：*for(int i = 0 , n = 1; i < maxLength; i++, n = 10) {
- 使用一個 for 循環處理原一維數組 arr ，将其放入桶中
  
  for(int j = 0; j < arr.length; j++) {
- 使用兩層 for 循環，處理 10 個桶，将其中的元素放回原一維數組中
  
  for (int k = 0; k < bucketElementCounts.length; k++) {
  
  if (bucketElementCounts[k] != 0) {
  
  for (int l = 0; l < bucketElementCounts[k]; l++) {

第 7 章排序算法第 7 章排序算法

9.4、代碼實作

9.4.1、了解基數排序

逐漸分解，了解基數排序算法

public class RadixSort {

	public static void main(String[] args) {
		
		int arr[] = { 53, 3, 542, 748, 14, 214};
		radixSort(arr);
		System.out.println("基數排序後 " + Arrays.toString(arr));
	
	}

	//基數排序方法
	public static void radixSort(int[] arr) {
		
//		//根據前面的推導過程，我們可以得到最終的基數排序代碼
		
		//1. 得到數組中最大的數的位數
		int max = arr[0]; //假設第一數就是最大數
		for(int i = 1; i < arr.length; i++) {
			if (arr[i] > max) {
				max = arr[i];
			}
		}
		
		//定義一個二維數組，表示10個桶, 每個桶就是一個一維數組
		//說明
		//1. 二維數組包含10個一維數組
		//2. 為了防止在放入數的時候，資料溢出，則每個一維數組(桶)，大小定為arr.length
		//3. 名明确，基數排序是使用空間換時間的經典算法
		int[][] bucket = new int[10][arr.length];
		
		//為了記錄每個桶中，實際存放了多少個資料,我們定義一個一維數組來記錄各個桶的每次放入的資料個數
		//可以這裡了解
		//比如：bucketElementCounts[0] , 記錄的就是  bucket[0] 桶的放入資料個數
		int[] bucketElementCounts = new int[10];
		
		
		//第1輪(針對每個元素的個位進行排序處理)
		for(int j = 0; j < arr.length; j++) {
			//取出每個元素的個位的值
			int digitOfElement = arr[j] / 1 % 10;
			//放入到對應的桶中
			bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
			bucketElementCounts[digitOfElement]++;
		}
		//按照這個桶的順序(一維數組的下标依次取出資料，放入原來數組)
		int index = 0;
		//周遊每一桶，并将桶中是資料，放入到原數組
		for(int k = 0; k < bucketElementCounts.length; k++) {
			//如果桶中，有資料，我們才放入到原數組
			if(bucketElementCounts[k] != 0) {
				//循環該桶即第k個桶(即第k個一維數組), 放入
				for(int l = 0; l < bucketElementCounts[k]; l++) {
					//取出元素放入到arr
					arr[index++] = bucket[k][l];
				}
			}
			//第l輪處理後，需要将每個 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 l = 0; l < bucketElementCounts[k]; l++) {
					// 取出元素放入到arr
					arr[index++] = bucket[k][l];
				}
			}
			//第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 % 10 = 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 l = 0; l < bucketElementCounts[k]; l++) {
					// 取出元素放入到arr
					arr[index++] = bucket[k][l];
				}
			}
			//第3輪處理後，需要将每個 bucketElementCounts[k] = 0 ！！！！
			bucketElementCounts[k] = 0;
		}
		System.out.println("第3輪，對個位的排序處理 arr =" + Arrays.toString(arr));
	}
	
}

程式運作結果

第1輪，對個位的排序處理 arr =[542, 53, 3, 14, 214, 748]
第2輪，對個位的排序處理 arr =[3, 14, 214, 542, 748, 53]
第3輪，對個位的排序處理 arr =[3, 14, 53, 214, 542, 748]
基數排序後 [3, 14, 53, 214, 542, 748]

9.4.2、編寫基數排序

編寫基數排序算法

public class RadixSort {

	public static void main(String[] args) {

		int arr[] = { 53, 3, 542, 748, 14, 214 };
		radixSort(arr);
		System.out.println("基數排序後 " + Arrays.toString(arr));

	}

	// 基數排序方法
	public static void radixSort(int[] arr) {
		
		//根據前面的推導過程，我們可以得到最終的基數排序代碼	
		//1. 得到數組中最大的數的位數
		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];
		
		
		// n=1 表示處理個位，n=10表示處理十位，n=100表示處理百位 ......
		for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) {
			//(針對每個元素的對應位進行排序處理)， 第一次是個位，第二次是十位，第三次是百位..
			for(int j = 0; j < arr.length; j++) {
				//取出每個元素的對應位的值
				int digitOfElement = arr[j] / n % 10;
				//放入到對應的桶中
				bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
				bucketElementCounts[digitOfElement]++;
			}
			//按照這個桶的順序(一維數組的下标依次取出資料，放入原來數組)
			int index = 0;
			//周遊每一桶，并将桶中的資料，放入到原數組
			for(int k = 0; k < bucketElementCounts.length; k++) {
				//如果桶中，有資料，我們才放入到原數組
				// 周遊第k個桶(即第k個一維數組), 将桶中的資料放回原數組中
				for (int l = 0; l < bucketElementCounts[k]; l++) {
					// 取出元素放入到arr
					arr[index++] = bucket[k][l];
				}
				//第i+1輪處理後，需要将每個 bucketElementCounts[k] = 0 ！！！！
				bucketElementCounts[k] = 0;				
			}
			System.out.println("第"+(i+1)+"輪，對個位的排序處理 arr =" + Arrays.toString(arr));
		}
	}
	
}

程式運作結果

第1輪，對個位的排序處理 arr =[542, 53, 3, 14, 214, 748]
第2輪，對個位的排序處理 arr =[3, 14, 214, 542, 748, 53]
第3輪，對個位的排序處理 arr =[3, 14, 53, 214, 542, 748]
基數排序後 [3, 14, 53, 214, 542, 748]

9.4.3、測試基數排序性能

測試基數排序算法的性能

public class RadixSort {

	public static void main(String[] args) {

		// 80000000 * 11 * 4 / 1024 / 1024 / 1024 =3.3G 
		int[] arr = new int[8000000];
		for (int i = 0; i < 8000000; 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);
		
		radixSort(arr);
		
		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序前的時間是=" + date2Str);
		

	}

	// 基數排序方法
	public static void radixSort(int[] arr) {
		
		//根據前面的推導過程，我們可以得到最終的基數排序代碼	
		//1. 得到數組中最大的數的位數
		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];
		
		
		// n=1 表示處理個位，n=10表示處理十位，n=100表示處理百位 ......
		for(int i = 0 , n = 1; i < maxLength; i++, n *= 10) {
			//(針對每個元素的對應位進行排序處理)， 第一次是個位，第二次是十位，第三次是百位..
			for(int j = 0; j < arr.length; j++) {
				//取出每個元素的對應位的值
				int digitOfElement = arr[j] / n % 10;
				//放入到對應的桶中
				bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
				bucketElementCounts[digitOfElement]++;
			}
			//按照這個桶的順序(一維數組的下标依次取出資料，放入原來數組)
			int index = 0;
			//周遊每一桶，并将桶中的資料，放入到原數組
			for(int k = 0; k < bucketElementCounts.length; k++) {
				//如果桶中，有資料，我們才放入到原數組
				// 周遊第k個桶(即第k個一維數組), 将桶中的資料放回原數組中
				for (int l = 0; l < bucketElementCounts[k]; l++) {
					// 取出元素放入到arr
					arr[index++] = bucket[k][l];
				}
				//第i+1輪處理後，需要将每個 bucketElementCounts[k] = 0 ！！！！
				bucketElementCounts[k] = 0;				
			}
			System.out.println("第"+(i+1)+"輪，對個位的排序處理 arr =" + Arrays.toString(arr));
		}
	}
	
}

程式運作結果：可以啊，八百萬資料 1s 就排好了，但是太占空間了

排序前
排序前的時間是=2020-07-16 18:16:21
排序前的時間是=2020-07-16 18:16:22

9.5、基數排序的說明

基數排序是對傳統桶排序的擴充，速度很快
基數排序是經典的空間換時間的方式，占用記憶體很大，當對海量資料排序時，容易造成 OutOfMemoryError 。
基數排序時穩定的。 [注：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中， r[i]=r[j]，且 r[i]在 r[j]之前，而在排序後的序列中， r[i]仍在 r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的]
有負數的數組，我們不用基數排序來進行排序, 如果要支援負數，參考: https://code.i-harness.com/zh-CN/q/e98fa9

10、常用排序算法總結和對比

10.1、排序算法的比較圖

第 7 章排序算法第 7 章排序算法

10.2、相關術語解釋

穩定：如果 a 原本在 b 前面，而 a=b，排序之後 a 仍然在 b 的前面；
不穩定：如果 a 原本在 b 的前面，而 a=b，排序之後 a 可能會出現在 b 的後面；
内排序：所有排序操作都在記憶體中完成；
外排序：由于資料太大，是以把資料放在磁盤中，而排序通過磁盤和記憶體的資料傳輸才能進行；
時間複雜度：一個算法執行所耗費的時間。
空間複雜度：運作完一個程式所需記憶體的大小。
n: 資料規模
k: “桶” 的個數
In-place：不占用額外記憶體
Out-place：占用額外記憶體

第 7 章 排序算法第 7 章 排序算法

第 7 章 排序算法

1、排序算法介紹

1.1、排序算法的簡介

1.2、排序算法的分類

2、算法的複雜度

2.1、時間複雜度的度量方法

2.2、時間頻度

2.3、時間複雜度

2.4、常見的時間複雜度

2.4.1、常見時間複雜度概述

2.4.2、常數階 O(1)

2.4.3、對數階 O(log2n)

2.4.4、線性階 O(n)

2.4.5、線性對數階 O(nlogN)

2.4.6、平方階 O(n²)

2.4.7、其他階

2.5、平均和最壞時間複雜度

2.6、算法的空間複雜度

3、冒泡排序

3.1、基本介紹

3.2、冒泡排序圖解

3.3、代碼實作

3.3.1、了解冒泡排序

3.3.2、編寫冒泡排序

3.3.3、測試冒泡排序性能

4、選擇排序

4.1、選擇排序基本介紹

4.2、選擇排序思想

4.3、選擇排序圖解

4.4、代碼實作

4.4.1、了解選擇排序

4.4.2、編寫選擇排序

4.4.3、測試選擇排序性能

4.5、總結

5、插入排序

5.1、插入排序基本介紹

5.2、插入排序思想

5.3、插入排序圖解

5.4、代碼實作

5.4.1、了解插入排序

5.4.2、編寫插入排序

5.4.3、測試插入排序性能

5.5、總結

6、希爾排序

6.1、簡單插入排序問題

6.2、希爾排序基本介紹

6.3、希爾排序基本思想

6.4、希爾排序圖解（交換法）

6.5、代碼實作

6.5.1、了解希爾排序（交換法）

6.5.2、編寫希爾排序（交換法）

6.5.3、測試希爾排序（交換法）性能

6.5.4、編寫希爾排序（插入法）

6.5.5、測試希爾排序（插入法）性能

7、快速排序

7.1、快排簡介

7.2、代碼思路

7.3、代碼實作

7.3.1、編寫快排算法

7.3.2、測試快速排序性能

8、歸并排序

8.1、歸并排序基本介紹

8.2、歸并排序思想

8.3、歸并排序代碼思路

8.4、代碼實作

8.4.1、編寫歸并排序算法

8.4.2、測試歸并排序性能

8.5、總結

9、基數排序

9.1、基數排序基本介紹

9.2、基數排序思想

9.3、基數排序圖解

9.4、代碼實作

9.4.1、了解基數排序

9.4.2、編寫基數排序

9.4.3、測試基數排序性能

9.5、基數排序的說明

10、常用排序算法總結和對比

10.1、排序算法的比較圖

第 7 章排序算法第 7 章排序算法

第 7 章排序算法