一、排序的概念及引用
1、排序的概念
排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。
穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩 定的；否則稱為不穩定的。
內部排序：數據元素全部放在內存中的排序。
外部排序：數據元素太多不能同時放在內存中，根據排序過程的要求不能在內外存之間移動數據的排序。
2、常見的排序算法
二、常見排序算法的實現
1、插入排序
1.1基本思想：
直接插入排序是一種簡單的插入排序法，其基本思想是：
把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到 一個新的有序序列 。實際中我們玩撲克牌時，就用了插入排序的思想。
1.2直接插入排序
當插入第i(i>=1)個元素時，前面的array[0],array[1],…,array[i-1]已經排好序，此時用array[i]的排序碼與array[i 1],array[i-2],…的排序碼順序進行比較，找到插入位置即將array[i]插入，原來位置上的元素順序后移
直接插入排序的特性總結：
（1）元素集合越接近有序，直接插入排序算法的時間效率越高
（2）時間復雜度：O(N^2)
（3）空間復雜度：O(1)，它是一種穩定的排序算法
（4）穩定性：穩定
1.3希爾排序( 縮小增量排序 )
希爾排序法又稱縮小增量法。希爾排序法的基本思想是：先選定一個整數，把待排序文件中所有記錄分成多個組， 所有距離為的記錄分在同一組內，并對每一組內的記錄進行排序。然后，取，重復上述分組和排序的工作。當到達 =1時，所有記錄在統一組內排好序。
希爾排序的特性總結：
（1）希爾排序是對直接插入排序的優化。
（2）當gap > 1時都是預排序，目的是讓數組更接近于有序。當gap == 1時，數組已經接近有序的了，這樣就會很 快。這樣整體而言，可以達到優化的效果。我們實現后可以進行性能測試的對比。
（3）希爾排序的時間復雜度不好計算，因為gap的取值方法很多，導致很難去計算，因此在好些樹中給出的希爾排序的時間復雜度都不固定，我們暫時就按照：O（n^1.25）到O（1.6*n^1.25）來算。
（4）穩定性：不穩定
2、選擇排序
2.1基本思想
每一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，直到全部待排序的數據元素排完 。
2.2直接選擇排序
（1）在元素集合array[i]--array[n-1]中選擇關鍵碼最大(小)的數據元素
（2）若它不是這組元素中的最后一個(第一個)元素，則將它與這組元素中的最后一個（第一個）元素交換
（3）在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重復上述步驟，直到集合剩余1個元素
【直接選擇排序的特性總結】
（1）直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用
（2）時間復雜度：O(N^2)
（3）空間復雜度：O(1)
（4）穩定性：不穩定
2.3堆排序
堆排序(Heapsort)是指利用堆積樹（堆）這種數據結構所設計的一種排序算法，它是選擇排序的一種。它是通過堆來進行選擇數據。需要注意的是排升序要建大堆，排降序建小堆。
【直接選擇排序的特性總結】
（1）堆排序使用堆來選數，效率就高了很多。
（2）時間復雜度：O(N*logN)
（3）空間復雜度：O(1)
（4）穩定性：不穩定
3、交換排序
基本思想：所謂交換，就是根據序列中兩個記錄鍵值的比較結果來對換這兩個記錄在序列中的位置，交換排序的特點是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動。
3.1冒泡排序
【冒泡排序的特性總結】
（1）冒泡排序是一種非常容易理解的排序
（2）時間復雜度：O(N^2)
（3）空間復雜度：O(1)
（4）穩定性：穩定
3.2快速排序
快速排序是Hoare于1962年提出的一種二叉樹結構的交換排序方法，其基本思想為：任取待排序元素序列中的某元 素作為基準值，按照該排序碼將待排序集合分割成兩子序列，左子序列中所有元素均小于基準值，右子序列中所有 元素均大于基準值，然后最左右子序列重復該過程，直到所有元素都排列在相應位置上為止。
// 假設按照升序對array數組中[left, right)區間中的元素進行排序void QuickSort(int[] array, int left, int right){if(right - left <= 1)return;// 按照基準值對array數組的 [left, right)區間中的元素進行劃分int div = partion(array, left, right);// 劃分成功后以div為邊界形成了左右兩部分 [left, div) 和 [div+1, right)// 遞歸排[left, div)QuickSort(array, left, div);// 遞歸排[div+1, right)QuickSort(array, div+1, right);}上述為快速排序遞歸實現的主框架，發現與二叉樹前序遍歷規則非常像，同學們在寫遞歸框架時可想想二叉樹前序 遍歷規則即可快速寫出來，后序只需分析如何按照基準值來對區間中數據進行劃分的方式即可。
將區間按照基準值劃分為左右兩半部分的常見方式有：
（1）Hoare版
private static int partition(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--;}while (i < j && array[i] <= pivot) {i++;}swap(array, i, j);}swap(array, i, left);return i;}（2）挖坑法
private static int partition(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;}（3）前后指針
寫法一：
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;}寫法二：
private static int partition(int[] array, int left, int right) {int d = left + 1;int pivot = array[left];for (int i = left + 1; i <= right; i++) {if (array[i] < pivot) {swap(array, i, d);d++;}}swap(array, d - 1, left);return d - 1;}3.3快速排序優化
（1）三數取中法選key
（2）遞歸到小的子區間時，可以考慮使用插入排序
3.4快速排序非遞歸
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);}}3.5快速排序總結
（1）快速排序整體的綜合性能和使用場景都是比較好的，所以才敢叫快速排序
（2）時間復雜度：O(N*logN)
（3）空間復雜度：O(logN)
（4）穩定性：不穩定
4、歸并排序
4.1基本思想
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并。
4.2歸并排序總結
（1）歸并的缺點在于需要O(N)的空間復雜度，歸并排序的思考更多的是解決在磁盤中的外排序問題。
（2）時間復雜度：O(N*logN)
（3）空間復雜度：O(N)
（4）穩定性：穩定
4.3海量數據的排序問題
外部排序：排序過程需要在磁盤等外部存儲進行的排序
前提：內存只有 1G，需要排序的數據有 100G
因為內存中因為無法把所有數據全部放下，所以需要外部排序，而歸并排序是最常用的外部排序
????????????????（1）先把文件切分成 200 份，每個 512 M
????????????????（2）分別對 512 M 排序，因為內存已經可以放的下，所以任意排序方式都可以
????????????????（3）進行 2路歸并，同時對 200 份有序文件做歸并過程，最終結果就有序了
三、排序算法復雜度及穩定性分析
)
