1. 排序的概念及引用
1.1 排序的概念
排序:所謂排序,就是使一串記錄,按照其中的某個或某些關鍵字的大小,遞增或遞減的排列起來的操作。
穩定性:假定在待排序的記錄序列中,存在多個具有相同的關鍵字的記錄,若經過排序,這些記錄的相對次序保持不變,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,則稱這種排序算法是穩定的;否則稱為不穩定的。
內部排序:數據元素全部放在內存中的排序。
外部排序:數據元素太多不能同時放在內存中,根據排序過程的要求不能在內外存之間移動數據的排序。
1.2 排序運用
1.3 常見的排序算法
2. 常見排序算法的實現
2.1 插入排序
2.1.1基本思想
直接插入排序是一種簡單的插入排序法,其基本思想是:
把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中,直到所有的記錄插入完為止,得到一個新的有序序列 。實際中我們玩撲克牌時,就用了插入排序的思想。
2.1.2 直接插入排序
當插入第i(i>=1)個元素時,前面的array[0],array[1],…,array[i-1]已經排好序,此時用array[i]的排序碼與array[i-1],array[i-2],…的排序碼順序進行比較,找到插入位置即將array[i]插入,原來位置上的元素順序后移
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;}}
直接插入排序的特性總結:
- 元素集合越接近有序,直接插入排序算法的時間效率越高
- 時間復雜度:O(N^2)
- 空間復雜度:O(1),它是一種穩定的排序算法
- 穩定性:穩定
2.1.3 希爾排序( 縮小增量排序 )
希爾排序法又稱縮小增量法。希爾排序法的基本思想是:先選定一個整數,把待排序文件中所有記錄分成多個組,所有距離為的記錄分在同一組內,并對每一組內的記錄進行排序。然后,取,重復上述分組和排序的工作。當到達=1時,所有記錄在統一組內排好序。
public static void shellSort(int[] array) {int gap = array.length;while (gap > 1) {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;}}
- 希爾排序是對直接插入排序的優化。
- 當gap > 1時都是預排序,目的是讓數組更接近于有序。當gap == 1時,數組已經接近有序的了,這樣就會很
快。這樣整體而言,可以達到優化的效果。我們實現后可以進行性能測試的對比。 - 希爾排序的時間復雜度不好計算,因為gap的取值方法很多,導致很難去計算,因此在好些樹中給出的希爾排
序的時間復雜度都不固定 - 穩定性:不穩定
2.2 選擇排序
2.2.1基本思想
每一次從待排序的數據元素中選出最小(或最大)的一個元素,存放在序列的起始位置,直到全部待排序的數據元素排完 。
2.2.2 直接選擇排序
- 在元素集合array[i]–array[n-1]中選擇關鍵碼最大(小)的數據元素
- 若它不是這組元素中的最后一個(第一個)元素,則將它與這組元素中的最后一個(第一個)元素交換
- 在剩余的array[i]–array[n-2](array[i+1]–array[n-1])集合中,重復上述步驟,直到集合剩余1個元素
public static void selectSort1(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);}}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, minIndex, left);if (maxIndex == left) {maxIndex = minIndex;}swap(array, maxIndex, right);left++;right--;}}private static void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}
【直接選擇排序的特性總結】
- 直接選擇排序思考非常好理解,但是效率不是很好。實際中很少使用
- 時間復雜度:O(N^2)
- 空間復雜度:O(1)
- 穩定性:不穩定
2.2.3 堆排序
堆排序(Heapsort)是指利用堆積樹(堆)這種數據結構所設計的一種排序算法,它是選擇排序的一種。它是通過堆來進行選擇數據。需要注意的是排升序要建大堆,排降序建小堆。
private static void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}public static void heapSort(int[] array) {createBigHeap(array);int end = array.length-1;while (end >= 0) {swap(array, 0, end);shiftDown(0, array, end);end--;}}private static void createBigHeap(int[] array) {for (int parent = (array.length-1-1) / 2; parent >=0 ; parent--) {shiftDown(parent, array, array.length);}}private static void shiftDown(int parent, int[] array, int end) {int child = 2*parent+1;while (child < end) {if (child + 1 < end && array[child] < array[child+1]) {child++;}if (array[child] > array[parent]) {swap(array, child, parent);parent = child;child = 2*parent+1;} else {break;}}}
【冒泡排序的特性總結】
- 冒泡排序是一種非常容易理解的排序
- 時間復雜度:O(N^2)
- 空間復雜度:O(1)
- 穩定性:穩定
2.3 交換排序
基本思想:所謂交換,就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置,交換排序的特點是:將鍵值較大的記錄向序列的尾部移動,鍵值較小的記錄向序列的前部移動。
2.3.1冒泡排序
public static void bubbleSort(int[] array) {boolean flg = false;for (int i = 0; i < array.length-1; i++) {for (int j = 0; j < array.length-1-i; j++) {if (array[j+1] < array[j]) {swap(array, j, j+1);flg =true;}}if (!flg) {break;}}}
【冒泡排序的特性總結】
- 冒泡排序是一種非常容易理解的排序
- 時間復雜度:O(N^2)
- 空間復雜度:O(1)
- 穩定性:穩定
2.3.2 快速排序
快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法,其基本思想為:任取待排序元素序列中的某元素作為基準值,按照該排序碼將待排序集合分割成兩子序列,左子序列中所有元素均小于基準值,右子序列中所有元素均大于基準值,然后最左右子序列重復該過程,直到所有元素都排列在相應位置上為止。
public static void quickSort(int[] array) {quick(array, 0, array.length-1);}private static void quick(int[] array, int start, int end) {if (start >= end) {return;}int par = partition(array, start, end);quick(array, start, par-1);quick(array, par+1, end);
}private static int partition(int[] array, int left, int right) {int tmp = array[left];while (left < right) {while (left < right && array[right] >= tmp) {right--;}array[left] = array[right];while (left < right && array[left] <= tmp) {left++;}array[right] = array[left];}array[left] = tmp;return left;}private static void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;
}
上述為快速排序遞歸實現的主框架,發現與二叉樹前序遍歷規則非常像,同學們在寫遞歸框架時可想想二叉樹前序遍歷規則即可快速寫出來,后序只需分析如何按照基準值來對區間中數據進行劃分的方式即可。
將區間按照基準值劃分為左右兩半部分的常見方式有:
-
Hoare版
public static void quickSort(int[] array) {quick(array, 0, array.length-1);}private static void quick(int[] array, int start, int end) {if (start >= end) {return;}int par = partitionHoare(array, start, end);quick(array, start, par-1);quick(array, par+1, end);
}private static int partitionHoare(int[] array, int left, int right) {int tmp = array[left];int start = left;while(left < right) {while (left < right && array[right] >= tmp) {right--;}while (left < right && array[left] <= tmp) {left++;}swap(array, left, right);}swap(array, start, left);return left;}private static void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}
- 挖坑法
private static int partitionW(int[] array, int left, int right) {int i = left;int j = right;int pivot = array[left];while (i < j) {while (i < j && array[j] >= pivot) {j--;}array[i] = array[j];while (i < j && array[i] <= pivot) {i++;}array[j] = array[i];}array[i] = pivot;return i;}
- 前后指針
private static int partition(int[] array, int left, int right) {int prev = left ;int cur = left+1;while (cur <= right) {if(array[cur] < array[left] && array[++prev] != array[cur]) {swap(array,cur,prev);}cur++;}swap(array,prev,left);return prev;
}
2.3.2 快速排序優化
- 三數取中法選key
- 遞歸到小的子區間時,可以考慮使用插入排序
2.3.3 快速排序非遞歸
void quickSortNonR(int[] a, int left, int right) {Stack<Integer> st = new Stack<>();st.push(left);st.push(right);while (!st.empty()) {right = st.pop();left = st.pop();if(right - left <= 1)continue;int div = PartSort1(a, left, right);// 以基準值為分割點,形成左右兩部分:[left, div) 和 [div+1, right)st.push(div+1);st.push(right);st.push(left);st.push(div);}
}
2.3.4 快速排序總結
-
快速排序整體的綜合性能和使用場景都是比較好的,所以才敢叫快速排序
-
時間復雜度:O(N*logN)
-
空間復雜度:O(logN)
-
穩定性:不穩定
2.4 歸并排序
2.4.1 基本思想
歸并排序(MERGE-SORT)是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法(Divide and Conquer)的一個非常典型的應用。將已有序的子序列合并,得到完全有序的序列;即先使每個子序列有序,再使子序列段間有序。若將兩個有序表合并成一個有序表,稱為二路歸并。 歸并排序核心步驟:
public static void mergeSort(int[] array) {mergeSortFun(array, 0, array.length-1);}private static void mergeSortFun(int[] array, int left, int right) {if (left == right) {return;}int mid = (right + left) / 2;mergeSortFun(array, left, mid);mergeSortFun(array, mid+1, right);merge(array, left, mid, right);}private static void merge(int[] array, int left, int mid, int right) {int[] tmp = new int[right-left+1];int k = 0;int s1 = left;int e1 = mid;int s2 = mid+1;int e2 = right;while (s1<=e1 && s2<=e2) {if (array[s1] <= array[s2]) {tmp[k] = array[s1];k++;s1++;} else {tmp[k] = array[s2];k++;s2++;}}while (s1<=e1) {tmp[k++] = array[s1++];}while (s2<=e2) {tmp[k++] = array[s2++];}if (k >= 0) System.arraycopy(tmp, 0, array, left, k);}
2.4.2 歸并排序總結
- 歸并的缺點在于需要O(N)的空間復雜度,歸并排序的思考更多的是解決在磁盤中的外排序問題。
- 時間復雜度:O(N*logN)
- 空間復雜度:O(N)
- 穩定性:穩定
2.4.3 海量數據的排序問題
外部排序:排序過程需要在磁盤等外部存儲進行的排序
前提:內存只有 1G,需要排序的數據有 100G
因為內存中因為無法把所有數據全部放下,所以需要外部排序,而歸并排序是最常用的外部排序
- 先把文件切分成 200 份,每個 512 M
- 分別對 512 M 排序,因為內存已經可以放的下,所以任意排序方式都可以
- 進行 2路歸并,同時對 200 份有序文件做歸并過程,最終結果就有序了
3. 排序算法復雜度及穩定性分析
排序方法 | 最好時間復雜度 | 平均時間復雜度 | 最壞時間復雜度 | 空間復雜度 | 穩定性 |
---|---|---|---|---|---|
冒泡排序 | O(n) | O(n^2) | O(n^2) | O(1) | 穩定 |
插入排序 | O(n) | O(n^2) | O(n^2) | O(1) | 穩定 |
選擇排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 不穩定 |
希爾排序 | O(n) | O(n^1.3) | O(n^2) | O(1) | 不穩定 |
堆排序 | O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(1) | 不穩定 |
快速排序 | O(n * log(n)) | O(n * log(n)) | O(n^2) | O(log(n)) ~ O(n) | 不穩定 |
歸并排序 | O(n * log(n)) | O(n * log(n)) | O(n * log(n)) | O(n) | 穩定 |