1.排序的基本概念

1.1 排序的定義

• 排序，就是重新排列表中的元素，使表中的元素滿足按關鍵字有序的過程。為了查找方便， 通常希望計算機中的表是按關鍵字有序的。
• 穩定性：排列后元素的相對位置不發生改變。穩定性不能衡量一個算法的優劣。
• 在排序過程中，根據數據元素是否完全存放在內存中，可將排序算法分為兩類：①內部排序， 是指在排序期間元素全部存放在內存中的排序；②外部排序，是指在排序期間元素無法全部同時 存放在內存中，必須在排序的過程中根據要求不斷地在內、外存之間移動的排序。
  一般情況下，內部排序算法在執行過程中都要進行兩種操作：比較和移動。通過比較兩個關鍵字的大小，確定對應元素的前后關系，然后通過移動元素以達到有序。當然，并非所有的內部 排序算法都要基于比較操作，事實上，基數排序就不基于比較操作。
  每種排序算法都有各自的優缺點，適合在不同的環境下使用，就其全面性能而言，很難提出 一種被認為是最好的算法。通常可以將排序算法分為插入排序、交換排序、選擇排序、歸并排序 和基數排序五大類。內部排序算法的性能取決于算法的時間復雜度和空間復雜度，而時間復雜度一般是由比較和移動的次數決定的。

2. 插入排序

插入排序是一種簡單直觀的排序算法，其基本思想是每次將一個待排序的記錄按其關鍵字大小插入前面已排好序的子序列，直到全部記錄插入完成。由插入排序的思想可以引申出三個重要的排序算法：直接插入排序、折半插入排序和希爾排序。

2.1 直接插入排序

• 實現對L[1…n]的排序，可以將L(2)～L(n)依次插入前面已排好序的子序列，初始L[1] 可以視為一個已排好序的子序列。上述操作執行n-1次就能得到一個有序的表。插入排序在實現 上通常采用原地排序(空間復雜度為 O(1),因而在從后往前的比較過程中，需要反復把已排序 元素逐步向后挪位，為新元素提供插入空間。
• 比較次數和移動次數取決于待排序表的初始狀態。
• 空間復雜度O(1)
• 時間復雜度：最好O(n) 平均O(n²) 最差O(n²)
• 穩定性：穩定
• 適用性：鏈式存儲和順序存儲都適用，鏈式存儲不用移動元素

   static void insertSort(int[] A, int n) {int j, temp;//從第二個位置開始判斷并插入到前面的有序隊列中for (int i = 1; i < n; i++) {//如果發現當前的比有序隊列還小,就進行插入操作if (A[i] < A[i - 1]) {//temp存的是待插入元素temp = A[i];//一個個比較直到找到temp的位置，只要temp小于有序元素，就向后移一位 12355for (j = i - 1; j >= 0 && temp < A[j]; j--) {A[j + 1] = A[j];}//最終的A[j + 1] = temp;}}}

2.2 折半插入排序

• 從直接插入排序算法中，不難看出每趟插入的過程中都進行了兩項工作：①從前面的有序子 表中查找出待插入元素應該被插入的位置；②給插入位置騰出空間，將待插入元素復制到表中的 插入位置。注意到在該算法中，總是邊比較邊移動元素。下面將比較和移動操作分離，即先折半 查找出元素的待插入位置，然后統一地移動待插入位置之后的所有元素。當排序表為順序表時， 可以對直接插入排序算法做如下改進：因為是順序存儲的線性表，所以查找有序子表時可以用折 半查找來實現。
• 比較次數與待排序表的初始狀態無關。
• 空間復雜度O(1)
• 時間復雜度：最好O(n) 平均O(n²) 最差O(n²)
• 穩定性：穩定
• 適用性：順序存儲

  static void halfInsertSort(int[] A, int n) {int j, temp, low, high, mid;for (int i = 1; i < n; i++) {if (A[i] < A[i - 1]) {temp = A[i];low = 0;high = i - 1;//查找待排元素位置while (low <= high) {//這個寫法主要是為了避免high特別大的情況，防止溢出 high比low多的分一半給low也就是兩人各自一半mid = low + (high - low) / 2;if (temp < A[mid]) {high = mid - 1;} else {low = mid + 1;}}//最終high的下一個位置就是待插入位置，這里只需要記住high最終會停在真實位置的前一個位置，所以大于high的都向后移動for (j = i - 1; j > high; j--) {A[j + 1] = A[j];}//這里high的下一個位置就是temp真正的位置A[high + 1] = temp;}}}

2.3 希爾排序

從前面的分析可知，直接插入排序算法的時間復雜度為O(n²),但若待排序列為“正序”時， 其時間效率可提高至O(n),由此可見它更適用于基本有序的排序表和數據量不大的排序表。希 排序正是基于這兩點分析對直接插入排序進行改進而得來的，又稱縮小增量排序。

• 希爾排序的基本思想是：先將待排序表分割成若干形如L[i,i+d,i+2d,…,i+kd]的“特殊” 子表，即把相隔某個“增量”的記錄組成一個子表，對各個子表分別進行直接插入排序，當整個 表中的元素已呈“基本有序”時，再對全體記錄進行一次直接插入排序。
• 空間復雜度O(1)
• 時間復雜度：最好O(n^1.3) 最差O(n²)
• 穩定性：不穩定
• 適用性：順序存儲

  public static void shellSort(int[] arr, int n) {// 初始步長int gap = n / 2;// 循環減小增量while (gap > 0) {// 對每個組進行直接插入排序  2, 4, 3, 5, 1, 6for (int i = gap; i < n; i++) {int temp = arr[i];int j = i;/*** 將arr[i]插入到已排序的序列中* arr[j - gap] > temp這里的意思是步長前元素與步長元素比較如果大于步長元素,* 則說明不是有序的，將原本的元素放入步長位置* 且j恢復到原來的位置，繼續比較*/while (j >= gap && arr[j - gap] > temp) {arr[j] = arr[j - gap];j -= gap;}//這里其實就是與最初的元素互換位置arr[j] = temp;System.out.println(Arrays.toString(arr));}// 減小步長gap /= 2;}}

3. 交換排序

所謂交換，是指根據序列中兩個元素關鍵字的比較結果來對換這兩個記錄在序列中的位置。 基于交換的排序算法很多，本書主要介紹冒泡排序和快速排序。

3.1 冒泡排序

冒泡排序的基本思想是：從后往前(或從前往后)兩兩比較相鄰元素的值，若為逆序(即 A[i-1]>A[i]),則交換它們，直到序列比較完。我們稱它為第一趟冒泡，結果是將最小的元素交換到待排序列的第一個位置(或將最大的元素交換到待排序列的最后一個位置),關鍵字最小 的元素如氣泡一般逐漸往上“漂浮”至“水面”(或關鍵字最大的元素如石頭一般下沉至水底)。 下一趟冒泡時，前一趟確定的最小元素不再參與比較，每趟冒泡的結果是把序列中的最小元素(或 最大元素)放到了序列的最終位置……這樣最多做n-1趟冒泡就能把所有元素排好序。

• 空間復雜度O(1)
• 時間復雜度：最好O(n²) 最差O(n²)
• 穩定性：穩定
• 適用性：順序存儲和鏈式存儲

    static void bubbleSort(int[] arr, int n) {//給個標記 防止在某一趟已經排好序了還繼續無用的循環 查看是否有元素交換boolean flag = false;for (int i = 0; i < n - 1; i++) {//這里的n-i-1是因為每一趟都會將最大的元素排到最后，也就是只需要排剩下的n-i-1個元素for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {//進入這個if分支里邊，則說明有元素進行了交換//所以將flag=trueflag = true;int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}//在進行完一輪的排序之后，判斷本輪是否發生了元素之間的交換//如果沒有發生交換，說明數組已經是有序的了，則直接結束排序if (!flag) {break;} else {//如果發生了交換，那么在下一輪排序之前將flag再次置為false//以便記錄下一輪排序的時候是否會發生交換flag = false;}}}

3.2 快速排序

快速排序(以下有時簡稱快排)的基本思想是基于分治法的：在待排序表L[1…n]中任取一 個元素 pivot 作為樞軸(或稱基準，通常取首元素),通過一趟排序將待排序表劃分為獨立的兩 部分L[1…k-1]和L[k+1…n],使得L[1…k-1]中的所有元素小于pivot,L[k+1…n]中的所有 元素大于或等于pivot,則pivot放在了其最終位置L(k)上，這個過程稱為一次劃分。然后分 別遞歸地對兩個子表重復上述過程，直至每部分內只有一個元素或為空為止，即所有元素放在了 其最終位置上。

• 快速排序是所有內部排序算法中平均性能最優的排序算法。
• 空間復雜度O(1)
• 時間復雜度：最好O(log₂ⁿ) 最差O(n²)
• 穩定性：不穩定
• 適用性：快速排序僅適用于順序存儲的線性表。

 /*** 快速排序*/private static void quickSort(int[] arr, int low, int high) {if (low < high) {int pivot = partition(arr, low, high);quickSort(arr, low, pivot - 1);quickSort(arr, pivot + 1, high);}}/*** 分區操作，找到基準元素的正確位置，并返回該位置** @param arr* @param low* @param high* @return*/static int partition(int[] arr, int low, int high) {int pivot = arr[low];int i = low;int j = high;while (i < j) {while (i < j && arr[j] >= pivot) {j--;}while (i < j && arr[i] <= pivot) {i++;}if (i < j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}}arr[low] = arr[i];arr[i] = pivot;return i;}

4. 選擇排序

選擇排序的基本思想是：每一趟(如第i趟)在后面n-i+1(i=1,2,…,n-1)個待排序元 素中選取關鍵字最小的元素，作為有序子序列的第i個元素，直到第n-1趟做完，待排序元素只 剩下1個，就不用再選。

4.1 簡單選擇排序

假設排序表為 L[1.n],第i趟排序即從L[i…n]中選擇關鍵字最小的元素與L(i)交換，每一趟排序可以確定一個元素的最終位置，這樣經過n-1趟排序就可使得整個排序表有序。

• 空間復雜度O(1)
• 時間復雜度：最好O(n²) 最差O(n²)
• 穩定性：不穩定
• 適用性：簡單選擇排序適用于順序存儲和鏈式存儲的線性表，以及關鍵字較少的情況。

    static void selectSort(int[] arr, int n) {for (int i = 0; i < n - 1; i++) {int min = i;for (int j = i + 1; j < n; j++) {if (arr[j] < arr[min]) {min = j;}}if (min != i) {int temp = arr[i];arr[i] = arr[min];arr[min] = temp;}}}

4.2 堆排序

堆的定義如下，n個關鍵字序列L[1…n]稱為堆，當且僅當該序列滿足：
①L(i)>=L(2i)且L(i)>=L(2i+1)或
② L(i)<=L(2i)且L(i)<=L(2i+1)(1≤i≤Ln/2」)
可以將堆視為一棵完全二叉樹，滿足條件①的堆稱為大根堆(大頂堆),大根堆的最大元素 存放在根結點，且其任意一個非根結點的值小于或等于其雙親結點值。滿足條件②的堆稱為小根 堆(小頂堆),小根堆的定義剛好相反，根結點是最小元素。

堆排序的思路很簡單：首先將存放在L[1-n]中的n個元素建成初始堆，因為堆本身的特點 (以大頂堆為例),所以堆頂元素就是最大值。輸出堆頂元素后，通常將堆底元素送入堆頂，此時 根結點已不滿足大頂堆的性質，堆被破壞，將堆頂元素向下調整使其繼續保持大頂堆的性質，再 輸出堆頂元素。如此重復，直到堆中僅剩一個元素為止。可見，堆排序需要解決兩個問題：①如何將無序序列構造成初始堆?②輸出堆頂元素后，如何將剩余元素調整成新的堆?

• 空間復雜度O(1)
• 時間復雜度：最好O(nlog₂ⁿ) 平均O(nlog₂ⁿ) 最壞O(nlog₂ⁿ)
• 穩定性：不穩定
• 適用性：適用于順序存儲。

  public static void heapSort(int[] arr, int n) {//初始化堆for (int i = n / 2 - 1; i >= 0; i--) {adjustHeap(arr, i, n);}for (int i = n - 1; i > 0; i--) {int temp = arr[0];arr[0] = arr[i];arr[i] = temp;adjustHeap(arr, 0, i);}}public static void adjustHeap(int[] arr, int i, int n) {while (true) {int l = 2 * i + 1;int r = 2 * i + 2;int index = i;if (l < n && arr[l] > arr[index]) {index = l;}if (r < n && arr[r] > arr[index]) {index = r;}if (i != index) {int temp = arr[index];arr[index] = arr[i];arr[i] = temp;i = index;} else {break;}}}

5. 歸并排序、基數排序和計數排序

5.1 歸并排序

歸并排序與上述基于交換、選擇等排序的思想不一樣，歸并的含義是將兩個或兩個以上的有 序表合并成一個新的有序表。假定待排序表含有n個記錄，則可將其視為n個有序的子表，每個 子表的長度為1,然后兩兩歸并，得到「n/2]個長度為2或1的有序表；繼續兩兩歸并……如此重 復，直到合并成一個長度為n的有序表為止，這種排序算法稱為二路歸并排序。

• 空間復雜度O(n)
• 時間復雜度：O(nlog₂ⁿ)
• 穩定性：穩定
• 適用性：適用于順序存儲和鏈式存儲。

public static void mergeSort(int[] arr, int left, int right) {//確保不會越界if (left < right) {//從中間劃分兩個序列int mid = left + (right - left) / 2;//左邊部分mergeSort(arr, left, mid);//右邊部分mergeSort(arr, mid + 1, right);merge(arr, left, mid, right);}}public static void merge(int[] arr, int left, int mid, int right) {int[] temp = new int[right - left + 1];//左邊子數組的第一個元素。int i = left;//右邊子數組的第一個元素int j = mid + 1;int k = 0;//當 i 和 j 都在各自子數組范圍內時循環。while (i <= mid && j <= right) {//誰小把誰放進temp數組if (arr[i] <= arr[j]) {temp[k++] = arr[i++];} else {temp[k++] = arr[j++];}}//走到這里說明上面有一個已經放完了所有元素,可能另外一個數組還有元素則繼續加入temp數組while (i <= mid) {temp[k++] = arr[i++];}while (j <= right) {temp[k++] = arr[j++];}// 將臨時數組的結果拷貝回原數組for (int m = 0; m < temp.length; m++) {arr[left + m] = temp[m];}}

4.2 基數排序

基數排序是一種很特別的排序算法，它不基于比較和移動進行排序，而基于關鍵字各位的大 小進行排序。基數排序是一種借助多關鍵字排序的思想對單邏輯關鍵字進行排序的方法。

• 空間復雜度O?
• 時間復雜度：O(d(n+r))
• 穩定性：穩定
• 適用性：適用于順序存儲和鏈式存儲。

4.3 計數排序

計數排序也是一種不基于比較的排序算法。計數排序的思想是：對每個待排序元素x,統計 小于x的元素個數，利用該信息就可確定x的最終位置。例如，若有8個元素小于x,則x就排 在第9號位置上。當有幾個元素相同時，該排序方案還需做一定的優化。

   static int[] countSort(int[] arr) {//1.得到數列的最大值與最小值，并算出差值dint max = arr[0];int min = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}if (arr[i] < min) {min = arr[i];}}int d = max - min;//2.創建基于差值長度的統計數組并統計填充對應元素個數int[] countArray = new int[d + 1];for (int i = 0; i < arr.length; i++) {countArray[arr[i] - min]++;}//3.統計數組變形，后面的元素等于前面的元素之和for (int i = 1; i < countArray.length; i++) {countArray[i] = countArray[i] + countArray[i - 1];}int[] output = new int[arr.length];//保證原來元素的順序 保持穩定for (int i = arr.length - 1; i >= 0; i--) {//arr[i] - min真正在countArray中的索引位置output[countArray[arr[i] - min] - 1] = arr[i];//避免相同的元素放在同一個位置 應該放在自己對應的位置countArray[arr[i] - min]--;}return output;}

6. 各種內部排序算法的比較及應用

1. 從時間復雜度看：簡單選擇排序、直接插入排序和冒泡排序平均情況下的時間復雜度都為 O(n²),且實現過程也較為簡單，但直接插入排序和冒泡排序最好情況下的時間復雜度可以達到 O(n),而簡單選擇排序則與序列的初始狀態無關。希爾排序作為插入排序的拓展，對較大規模的 數據都可以達到很高的效率，但目前未得出其精確的漸近時間。堆排序利用了一種稱為堆的數據 結構，可以在線性時間內完成建堆，且在O(nlog2n)內完成排序過程。快速排序基于分治的思想， 雖然最壞情況下的時間復雜度會達到O(n²),但快速排序的平均性能可以達到O(nlogn),在實際 應用中常常優于其他排序算法。歸并排序同樣基于分治的思想，但由于其分割子序列與初始序列 的排列無關，因此它的最好、最壞和平均時間復雜度均為O(nlog2n)。
2. 從空間復雜度看：簡單選擇排序、插入排序、冒泡排序、希爾排序和堆排序都僅需借助常數 個輔助空間。快速排序需要借助一個遞歸工作棧，平均大小為
   O(log2n),當然在最壞情況下可能會增長到O(n)。二路歸并排序在合并操作中需要借助較多的輔助空間用于元素復制，大小為0(n),
   雖然有方法能克服這個缺點，但其代價是算法會很復雜而且時間復雜度會增加。
3. 從穩定性看：插入排序、冒泡排序、歸并排序和基數排序是穩定的排序算法，而簡單選擇排 序、快速排序、希爾排序和堆排序都是不穩定的排序算法。平均時間復雜度為O(nlogn)的穩定排
   序算法只有歸并排序，對于不穩定的排序算法，只需舉出一個不穩定的實例即可。
4. 從適用性看：折半插入排序、希爾排序、快速排序和堆排序適用于順序存儲。直接插入排序、冒泡排序、簡單選擇排序、歸并排序和基數排序既適用于順序存儲，又適用于鏈式存儲。
   

7. 外部排序

① 外部排序指的是大文件的排序，即待排序的記錄存儲在外存中，待排序的文件無法一次性裝入內存，需要在內存和外存之間進行多次數據交換，以達到排序整個文件的目的。
② 為減少平衡歸并中外存讀/寫次數所采取的方法：增大歸并路數和減少歸并段個數。
③ 利用敗者樹增大歸并路數。
④ 利用置換-選擇排序增大歸并段長度來減少歸并段個數。 ⑤ 由長度不等的歸并段進行多路平衡歸并，需要構造最佳歸并樹。
許多應用中，經常需要對大文件進行排序，因為文件中的記錄很多，無法將整個文件復制進內存中進行排序。因此，需要將待排序的記錄存儲在外存上，排序時再把數據一部分一部分地調入內存進行排序，在排序過 程中需要多次進行內存和外存之間的交換。這種排序算法就稱為外部排序。

8. 一些常見結論

• 選擇排序、快速排序、希爾排序、堆排序不是穩定的排序算法。【選快希堆】
• 冒泡排序、插入排序、歸并排序、基數排序是穩定的排序算法。【直冒歸基】
• 簡單選擇排序則與序列的初始狀態無關