排序的簡單理解（上）

1. 排序的概念及引用

1.1 排序的概念

????????排序：所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作（按照我們的需求能夠有序的將數據信息排列起來）。

????????穩定性：假定在待排序的記錄序列中，存在多個具有相同的關鍵字的記錄，若經過排序，這些記錄的相對次序保持不變，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，則稱這種排序算法是穩定的；否則稱為不穩定的（如果一份數據中有多個相同的數據，在經過排序后這幾個數據的先后邏輯順序沒有發生改變就稱為該算法穩定性強）。

????????

????????內部排序：數據元素全部放在內存中的排序。

????????外部排序：數據元素太多不能同時放在內存中，根據排序過程的要求不能在內外存之間移動數據的排序。

1.2?常見的排序算法

? ? ? ? 我們本次學習主要學習一下四類七種排序算法；

? ? ? ? 下文我們將詳細的介紹不同的排序算法及實現?

2. 插入排序

2.1 直接插入排序

???????? 直接插入排序是一種簡單的插入排序法，其基本思想是：把待排序的記錄按其關鍵碼值的大小逐個插入到一個已經排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。實際中我們玩撲克牌時，就用了插入排序的思想

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

2.1.1 詳細思路與圖解分析

????????把n個待排序的元素看成為一個有序表和一個無序表，開始時有序表中只包含一個元素（默認），無序表中包含n-1個元素，排序過程中每次從無序表中取出第一個元素，把它的排序碼依次與有序表元素的排序碼從后往前一一進行比較，將它插入到有序表中的適當位置，使之成為一個新的有序表。

????????以序列：{55, 85, 21, 12, 5}?為例，?圖解如下：

? ? ? ??

????????紅色部分為每輪認定的有序部分，其余顏色為認定的無序部分。綠色標識為每輪遍歷的無序序列的位置，將該位置的元素逐一與有序部分進行比較，找到合適的位置進行順序表的插入操作。?

? ? ? ? 代碼一：

 public static void insertSort(int[] array){//判斷數組為空，無法排序if (array.length <1){return;}for (int i = 1; i < array.length; i++) {//定義待插入位置和待插入的數值int insertIndex = i-1;//arr[i]前面的位置,便于插入int insertValue = array[i];//現將待插入的數值保存到變量中//給insertValue找到待插入的位置//1.insertIndex > 0防止越界//2.insertValue < arr[insertIndex] 說明還未找到待插入的位置，// 還要繼續與前面的那個位置進行比較，直到insertValue > arr[insertIndex]//說明找到了要插入的點的索引while (insertIndex >= 0 && insertValue < array[insertIndex]){array[insertIndex+1] = array[insertIndex];insertIndex--;}if (insertIndex != i){//要插入的位置insertindex與剛開始的該元素存放的位置不一樣//我們比insertindex位置大，所以要插到他后面，所以加一array[insertIndex+1] = insertValue; //插入}System.out.println("第" + i + "輪: " + Arrays.toString(array));}}

? ? ? ? 測試代碼如下：

public static void main(String[] args) {int[] array = {55, 85, 21, 12, 5};System.out.println("排序前: " + Arrays.toString(array));insertSort(array);System.out.println("排序后: " + Arrays.toString(array));}

? ? ? ? ?實現效果如下：

? ? ? ? ??

? ? ? ? 代碼二展示（簡單易理解）：

 public static void instersort(int[] arr){for (int i = 1; i <arr.length ; i++) {int tmp=arr[i];int j = i-1;for (; j>=0 ; j--) {if(arr[j]>tmp){arr[j+1]=arr[j];}else{break;}}arr[j+1]=tmp;}}

? ? ? ? 結果展示：

? ? ? ? ??

2.2.2 分析與總結

/*** 時間復雜度：*    最壞情況下：O(n^2)  5   4   3   2   1*    最好情況下：O(n)   當前數據越有序，排序越快   1  2  3  4  5*    適用于：待排序序列  已經基本上趨于有序了！* 空間復雜度： O(1)* 穩定性：穩定的*/

以下是動圖展示：

2.2?希爾排序( 縮小增量排序 )

2.2.1 詳細思路與圖解分析

????????希爾排序法又稱縮小增量法。

????????希爾排序是基于插入排序的以下兩點性質而提出改進方法的：

插入排序在對幾乎已經排好序的數據操作時，效率高，即可以達到線性排序的效率；
但插入排序一般來說是低效的，因為插入排序每次只能將數據移動一位；

????????希爾排序法的基本思想是：把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至 1 時，整個文件恰被分成一組，算法便終止。希爾排序是非穩定排序算法。

????????以序列:?{8, 9, 1, 7, 2, 3, 5, 6, 4, 0}?為例

1、初始步長gap = length/2 ＝ 5，意味著將整個數組分為了5組，即[8，3]，[9，5]，[1，6]，[7，4]，[2，0]，對每組進行插入排序，得到序列：{3，5，1，4，0，8，9，6，7，2}，可以看到：3，5，4，0這些小元素都被提到前面了

2、縮小增量gap = 5/2 = 2，數組被分為兩組，即[3，1，0，9，7]，[5，4，8，6，2]，對這兩組分別進行直接插入排序，可以看到，整個數組的有序程度更進一步了

3、再次縮小增量，gap = 2/2 = 1，此時整個數組為[0，2，1，4，3，5，7，6，9，8]，進行一次插入排序，即可實現數組的有序化（僅需要簡單微調，而無需大量移動操作）

? ? ? ? 代碼一實現如下：

public static void shellSort(int[] arr){//設定步長for (int gap = arr.length / 2; gap > 0; gap /= 2){//將數據分為arr.length/gap組，逐個對其所在的組進行插入排序//按照分組一直進行下面的每組直接插入，直到整個元素集合分為一組for (int i = gap; i < arr.length; i++) {//遍歷各組中的所有元素，步長為gapint j = i;//每一組的元素個數定義為jint temp = arr[j]; //記錄待插入的值while (j - gap >= 0 && temp < arr[j-gap]){//移動arr[j] = arr[j-gap];j -= gap;}//找到位置，進行插入arr[j] = temp;}System.out.println(Arrays.toString(arr));}}

? ? ? ? 代碼二（較易理解）：

    public void straightInsertion(int[] array,int gap) {int len = array.length;for(int i = gap; i < len ; i++) {int count = array[i];int j = i - gap;for( ; j >= 0; j-=gap) {if(count < array[j]) {array[j + gap] = array[j];} else {break;}}array[j + gap] = count;}}public void shellSort(int[] arrary) {int gap = arrary.length;while(gap  > 0) {gap = gap /2;straightInsertion(arrary,gap);}}

??????????測試代碼及結果如下：

 public static void main(String[] args) {int[] arr = {8, 9, 1, 7, 2, 3, 5, 6, 4, 0};System.out.println("排序前: " + Arrays.toString(arr));shellSort(arr);System.out.println("排序后: " + Arrays.toString(arr));}

?????????

2.2.2 分析與總結

1. 希爾排序是對直接插入排序的優化。
2. 當 gap > 1 時都是預排序，目的是讓數組更接近于有序。當 gap == 1 時，數組已經接近有序的了，這樣就會很快。這樣整體而言，可以達到優化的效果。我們實現后可以進行性能測試的對比。
3. 希爾排序的時間復雜度不好計算，因為 gap 的取值方法很多，導致很難去計算，因此在好些書中給出的希爾排序的時間復雜度都不固定。（時間復雜度不固定）
4. 穩定性：不穩定

3 選擇排序

????????基本思想：第一次從待排序的數據元素中選出最小（或最大）的一個元素，存放在序列的起始位置，然后再從剩余的未排序元素中尋找到最小（大）元素，然后放到已排序的序列的末尾。以此類推，直到全部待排序的數據元素的個數為零。選擇排序是不穩定的排序方法。

3.1 直接選擇排序

? ? ? ? 動態圖解如下圖所示：

3.1.1?詳細思路與圖解分析

第一次：從arr[0]~arr[n-1]中選取最小值，與arr[0]進行交換；
第二次：從arr[1]~arr[n-1]中選取最小值，與arr[1]進行交換；
第三次：從arr[2]~arr[n-1]中選取最小值，與arr[2]進行交換；
…
第 i 次：從arr[i]~arr[i-1]中選取最小值，與arr[i]進行交換；
總共通過n-1次，可以得到從小到大的有序序列。

以序列：{8, 3, 2, 1, 7, 4, 6, 5} 為例！分步驟圖解如下：? ? ? ? ? ? ??

綜上所述：

在每趟排序時，都默認當前位置的元素為最小值，如果在遍歷過程中發現有比當前位置元素還小的值，則替換最小值。（先將最小值記錄，此趟遍歷完成再替換）
選擇排序一共有arr.length-1次趟排序。

? ? ? ? 代碼一如下實現：

  public static void selectSort(int[] arr){//選擇排序過程for (int i = 0; i < arr.length - 1; i++) {int minIndex = i; //假定最小索引，最小值為第一個元素int min = arr[minIndex];for (int j = i + 1; j < arr.length; j++) {if (min > arr[j]){//更新最小值min = arr[j];minIndex = j;}}//將最小值放進arr[i]if (i != minIndex){arr[minIndex] = arr[i];arr[i] = min;}//輸出每輪排序后的結果System.out.println("第" + (i+1) + "趟: " + Arrays.toString(arr));}}

? ? ? ? 代碼二（更易理解）：

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

? ? ? ? 測試代碼及結果：

public static void main(String[] args) {int[] array = {8, 3, 2, 1, 7, 4, 6, 5};System.out.println("排序前: " + Arrays.toString(array));selectSort(array);System.out.println("排序后: " + Arrays.toString(array));}

? ? ? ?

3.1.2 直接選擇排序的特性總結

直接選擇排序思考非常好理解，但是效率不是很好。實際中很少使用

時間復雜度：O(N^2)

空間復雜度：O(1)

穩定性：不穩定

3.2 堆排序

????????堆排序（Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆積是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。堆排序可以說是一種利用堆的概念來排序的選擇排序。（關于堆的相關詳細知識見于前面相應章節）分為兩種方法：????????

????????大頂堆：每個節點的值都大于或等于其子節點的值，在堆排序算法中用于升序排列；

????????小頂堆：每個節點的值都小于或等于其子節點的值，在堆排序算法中用于降序排列；

3.2.1?詳細思路與圖解分析

????????圖解如下圖所示：?

由上圖所示，該方法思路如下所示：

創建一個堆 H[0……n-1]；

把堆首（最大值）和堆尾互換；

把堆的尺寸縮小 1，并調用相應方法，目的是把新的數組頂端數據調整到相應位置；

重復步驟 2，直到堆的尺寸為 1

代碼實現如下：

    private  void swap(int[] array,int i,int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;}public  void heapSort(int[] array) {createBigHeap(array);int end = array.length-1;while (end > 0) {swap(array,0,end);shiftDown(array,0,end);end--;}}private  void createBigHeap(int[] array) {for (int parent = (array.length-1-1)/2; parent >= 0 ; parent--) {shiftDown(array,parent,array.length);}}private  void shiftDown(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;}}}