【Java筆記】七大排序

- 1. 直接插入排序
- 2. 希爾排序
- 3. 選擇排序
- 4. 堆排序(重要)
- 5. 冒泡排序
- 6. 快速排序（重要）
- - 6.1 Hoare 法
  - - 6.1.1 Hoare 法優化
  - 6.2 挖坑法（重點）
  - 6.3 快速排序的非遞歸寫法
- 7. 歸并排序
- - 海量數據的排序問題
- 8. 總結

1. 直接插入排序

時間復雜度： 最壞情況：O(n ² ) 最壞情況：O(n)
空間復雜度： O(1)
穩定性： 穩定

如果一個排序本身就是穩定的排序那么他可以被實現為不穩定的排序
但是如果一個排序本身就是不穩定的排序那么他就不可能被實現為穩定的排序
當數據趨于有序使用直接插入排序最快

代碼：

	// 1. 直接插入排序public static void insertSort(int[] array) {for (int i = 1; i < array.length; i++) {int tmp = array[i];int j = i - 1;for (; j >= 0; j--) {if (array[j] > tmp) {array[j + 1] = array[j];} else {break;}}array[j + 1] = tmp;}}

過程演示：
在這里插入圖片描述

2. 希爾排序

時間復雜度： O(n ^1.3 ) ~ O(n ^1.5 )
空間復雜度： O(1)
穩定性： 不穩定

	// 2. 希爾排序public static void shellSort(int[] array) {int gap = array.length;while (gap > 0) {gap /= 2;shell(array, gap);}}private static void shell(int[] array, int gap) {for (int i = gap; i < array.length; i++) {int tmp = array[i];int j = i - gap;for (; j >= 0 ; j -= gap) {if (array[j] > tmp) {array[j + gap] = array[j];} else {break;}}array[j + gap] = tmp;}}

演示：
在這里插入圖片描述

3. 選擇排序

時間復雜度： O(n ² )
空間復雜度： O(1)
穩定性： 不穩定

方式一：

	// 3. 選擇排序public static void selectSort(int[] array) {for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i + 1; j < array.length; j++) {if (array[j] < array[minIndex]) {minIndex = j;}}swap(array, i, minIndex);}}private static void swap(int[] array, int i, int minIndex) {int tmp = array[i];array[i] = array[minIndex];array[minIndex] = tmp;}

過程演示：
在這里插入圖片描述
方式二：
時間復雜度： O(n ² )

	// 方式二public static void selectSort2(int[] array) {int left = 0;int right = array.length - 1;while (left < right) {int minIndex = left;int maxIndex = left;for (int i = left + 1; i <= right; i++) {if (array[i] < array[minIndex]) {minIndex = i;}if (array[i] > array[maxIndex]) {maxIndex = i;}}swap(array, left, minIndex);// 第一個數據是最大值if (left == maxIndex) {maxIndex = minIndex;}swap(array, right, maxIndex);left++;right--;}}

過程演示：
在這里插入圖片描述

4. 堆排序(重要)

時間復雜度： O(N*logN )
空間復雜度： O(1)
穩定性： 不穩定

	// 4. 堆排序public static void heapSort(int[] array) {// 創建大根堆creatHeap(array);int end = array.length - 1;while (end > 0) {// 交換swap(array, 0, end);// 向下調整siftDown(array, 0, end);end--;}}private static void creatHeap(int[] array) {for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {// 向下調整siftDown(array, parent, array.length);}}private static void siftDown(int[] array, int parent, int len) {int child = 2 * parent + 1;while (child < len) {// 找到左右孩子的最大值if (child + 1 < len && array[child] < array[child + 1]){child++;}if (array[child] > array[parent]) {swap(array, child, parent);parent = child;child = 2 * parent + 1;} else {break;}}}

5. 冒泡排序

時間復雜度： O(n ² ) 下面代碼最好情況是：O(n)
空間復雜度： O(1)
穩定性： 穩定

	// 5. 冒泡排序public static void bubbleSort(int[] array) {// i 代表的是趟數for (int i = 0; i < array.length - 1; i++) {// 優化boolean flg = false;for (int j = 0; j < array.length - 1 - i; j++) {if (array[j] > array[j + 1]) {swap(array, j, j + 1);flg = true;}}// 如果flg == false，說明沒有進入if語句，表示數組已經有序了，無需再排序，直接break即可if (!flg) {break;}}}

6. 快速排序（重要）

6.1 Hoare 法

時間復雜度： 最壞情況是單分支的樹（1,2,3,4,5）O(n ² ) ，但是一般不會這么用；最好情況是：O(n*logn)
空間復雜度： 最壞情況：單分支的樹O(n)；最好情況O(logn)
穩定性： 不穩定

	// 6. 快速排序// hoare 版public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int left, int right) {if (left >= right) {return;}// 劃分int par = partition(array, left, right);quick(array, left, par - 1);quick(array, par + 1, right);}private static int partition(int[] array, int start, int end) {int i = start; // 保存start初始位置int pivot = array[start];while (start < end) {// 如果數組是1,2,3,4,5加start < end是為了防止越界while (start < end && array[end] >= pivot) {end--;}// 如果數組是5,4,3,2,1加start < end是為了防止越界while (start < end && array[start] <= pivot) {start++;}swap(array, start, end);}// start == endswap(array, i, start);return start;}

過程演示：
在這里插入圖片描述

6.1.1 Hoare 法優化

三數取中法：找到三個數，分別是start、end、mid下標對應的值，找到三個數的中位數作為劃分基準

	// hoare 法優化// 三數取中法找到劃分基準public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int left, int right) {if (left >= right) {return;}// 優化二// 當節點數小于某一個閾值，沒有必要進行遞歸，直接使用插入排序效率更高，因為所有排序都是越排越有序的！if (right - left + 1 < 7) {insertSort1(array, left, right);return;}// 優化一int index = midThreeNum(array, left, right);swap(array, left, index);// 劃分int par = partition(array, left, right);quick(array, left, par - 1);quick(array, par + 1, right);}// 找到三個數，分別是start、end、mid下標對應的值，找到三個數的中位數作為劃分基準private static int midThreeNum(int[] array, int start, int end) {int mid = (start + end) / 2;// 3 < 5  start == 3  end == 5   x == midif (array[start] < array[end]) {if (array[mid] < array[start]) {// x < 3 < 5return start;} else if (array[mid] > array[end]) {// 3 < 5 < xreturn end;} else {// 3 < x < 5return mid;}} else {// 5 > 3  start == 5  end == 3  x == midif (array[mid] > array[start]) {// x > 5 > 3return start;} else if (array[mid] < array[end]) {// 5 > 3 > xreturn end;} else {// 5 > x > 3return mid;}}}// 直接插入排序public static void insertSort1(int[] array, int start, int end) {for (int i = start + 1; i <= end; i++) {int tmp = array[i];int j = i - 1;for (; j >= start; j--) {if (array[j] > tmp) {array[j + 1] = array[j];} else {break;}}array[j + 1] = tmp;}}private static int partition(int[] array, int start, int end) {int i = start;int pivot = array[start];while (start < end) {while (start < end && array[end] >= pivot) {end--;}while (start < end && array[start] <= pivot) {start++;}swap(array, start, end);}// start == endswap(array, i, start);return start;}

6.2 挖坑法（重點）

	// 挖坑法public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int left, int right) {if (left >= right) {return;}// 劃分int par = partition(array, left, right);quick(array, left, par - 1);quick(array, par + 1, right);}private static int partition(int[] array, int start, int end) {int pivot = array[start];while (start < end) {while (start < end && array[end] >= pivot) {end--;}array[start] = array[end];while (start < end && array[start] <= pivot) {start++;}array[end] = array[start];}array[start] = pivot;return start;}

過程演示：
在這里插入圖片描述

6.3 快速排序的非遞歸寫法

	// 快速排序的非遞歸寫法public static void quicksort2(int[] array) {int left = 0;int right = array.length - 1;// 找到一個基準值int par = partition(array, left, right);Stack<Integer> stack = new Stack<>();// 判斷一下par左邊是否只有一個元素了，如果只有一個元素則沒必要繼續排序了，否則將入棧if (par > left + 1) {stack.push(left);stack.push(par - 1);}if (par < right - 1) {stack.push(par + 1);stack.push(right);}while (!stack.isEmpty()) {right = stack.pop();left = stack.pop();par = partition(array, left, right);if (par > left + 1) {stack.push(left);stack.push(par - 1);}if (par < right - 1) {stack.push(par + 1);stack.push(right);}} }

過程演示：
在這里插入圖片描述

7. 歸并排序

時間復雜度： O(n*logn)
空間復雜度： O(n)
穩定性： 穩定

	// 7. 歸并排序public static void mergeSort(int[] array) {mergeSortFunc(array, 0, array.length - 1);}private static void mergeSortFunc(int[] array, int left, int right) {if (left == right) {return;}int mid = (left + right) / 2;// 分解mergeSortFunc(array, left, mid);mergeSortFunc(array, mid + 1, right);// 合并merge(array, left, right, mid);}private static void merge(int[] array, int left, int right, int mid) {int start1 = left;int end1 = mid;int start2 = mid + 1;int end2 = right;int[] tmpArr = new int[right - left + 1];int k = 0;// 此時2個數組都只收有一個數據while (start1 <= end1 && start2 <= end2) {if (array[start1] <= array[start2]) {tmpArr[k++] = array[start1++];} else {tmpArr[k++] = array[start2++];}}// 一個數組被遍歷完while (start1 <= end1) {tmpArr[k++] = array[start1++];}while (start2 <= end2) {tmpArr[k++] = array[start2++];}// 保證tmpArr當中的元素是有序的for (int i = 0; i < tmpArr.length; i++) {array[i + left] = tmpArr[i];}}

過程演示：
在這里插入圖片描述

海量數據的排序問題

外部排序：排序過程需要在磁盤等外部存儲進行的排序

在內存只有 1G，需要排序的數據有 100G 的情況下

因為內存中因為無法把所有數據全部放下，所以需要外部排序，而歸并排序是最常用的外部排序

先把文件切分成 200 份，每個 512 M
分別對 512 M 排序，因為內存已經可以放的下，所以任意排序方式都可以
進行 2路歸并，同時對 200 份有序文件做歸并過程，最終結果就有序了

8. 總結

排序方法	平均時間復雜度	空間復雜度	穩定性
直接插入排序	O(n²)	O(1)	穩定
希爾排序	O(n ^1.3 ) ~ O(n ^1.5 )	O(1)	不穩定
選擇排序	O(n²)	O(1)	不穩定
堆排序	O(nlogn)	O(1)	不穩定
冒泡排序	O(n²)	O(1)	穩定
快速排序	最壞O(n²)，最好O(nlogn)	單分支的樹O(n)，最好情況O(logn)	不穩定
歸并排序	O(nlogn)	O(n)	穩定