一、選擇排序

1.算法思想

選擇排序（Selection Sort）是一種簡單直觀的排序算法，其基本思想是：每次都從待排序部分中選出最小的一個數據和待排序的第一個數據交換。

將待排序序列分為已排序和未排序兩部分，初始時已排序部分為空，未排序部分包含整個待排序序列。在每一輪迭代中，從未排序部分中選擇最小（或最大）的元素，將其與未排序部分的第一個元素交換位置，從而將該元素添加到已排序部分的末尾。重復這個過程，直到整個序列都被排序。
選擇排序的具體步驟：
從整個序列中選擇最小的元素，將其與第一個位置的元素交換。此時，第一個位置的元素就是整個序列中最小的元素，已排序部分包含這一個元素，未排序部分包含剩余的元素。
在剩余的未排序元素中選擇最小的元素，將其與未排序部分的第一個位置（即第二個位置）的元素交換。此時，前兩個位置的元素是有序的，已排序部分包含兩個元素，未排序部分包含剩余的元素。
重復上述步驟，每次都從未排序部分中選擇最小的元素，并將其與未排序部分的第一個位置的元素交換，直到未排序部分只剩下一個元素。此時，整個序列已經完全有序。

2.代碼實現?

//選擇排序
void SelectSort(int* arr, int len)
{int tmp;int minIndex;//最小值的下標for (int i = 0; i < len - 1; i++){minIndex = i;for (int j = i + 1; j < len; j++){if (arr[minIndex] > arr[j]){minIndex = j;}}if (minIndex != i)//最小值和待排序的第一個為同一個，則不交換，提高效率{tmp = arr[minIndex];arr[minIndex] = arr[i];arr[i] = tmp;}}
}

?3.復雜度分析

1.選擇排序的時間復雜度為O(n2)，其中n是待排序序列的長度。這是因為對于一個長度為n的序列，需要進行n?1輪選擇和交換操作，每輪操作需要遍歷未排序部分的元素，平均需要比較n/2次。

2.選擇排序的空間復雜度為O(1)，因為它只需要使用常數級別的額外空間來進行元素的交換。

3. 不穩定：在選擇排序里，當把最小元素和未排序序列的首個元素交換時，可能會改變相等元素的相對順序。

二、堆排序

堆是一種特殊的完全二叉樹，分為大根堆和小根堆。

大根堆的每個節點的值都大于或等于其左右子節點的值，小根堆則相反，每個節點的值都小于或等于其左右子節點的值。（大根堆小根堆只看父子關系）

堆排序的基本思想是將待排序的序列構建成一個堆，然后依次取出堆頂元素并調整堆，直到整個序列有序。

1.算法思想

• 建堆：將給定的數組構建成一個大根堆（或小根堆）。從最后一個非葉子節點開始，依次向上調整每個節點，使其滿足堆的性質。
• 交換元素：將堆頂元素與堆的最后一個元素交換位置，此時堆頂元素是當前堆中的最大（或最小）值，將其取出，放到已排序序列的末尾。
• 調整堆：交換元素后，堆的性質可能被破壞，需要對剩余的元素重新調整堆，使其再次滿足堆的性質。重復步驟 2 和 3，直到堆中只剩下一個元素，此時整個數組已經有序。

?1->調整成大根堆

(1)從最后一棵子樹開始，從后往前調整

(2)每次調整，從上往下

(3)整體調整成大根堆

具體調整：

定義一個臨時變量tmp，把根放到tmp里，找左右孩子的最大值，和tmp比較，如果比tmp大，則放到根的位置，繼續遞歸比較新的左右孩子的最大值

調整順序：

調整子樹：

?調整完成：

?2->根和待排序的最后一個交換

根是最大的，交換后則視作有序

3->再次調整成大根堆

2.代碼實現

//堆排序void HeapAdjust(int* arr, int start, int end)
{int tmp = arr[start];for (int i = 2 * start + 1; i <= end;i=2*i+1)//從上往下{if (i < end && arr[i] < arr[i + 1])//如果有右孩子，且左孩子的值小于右孩子{i++;}//i一定是左右孩子的最大值if (arr[i] > tmp){arr[start] = arr[i];start = i;}else{break;}}arr[start] = tmp;
}void HeapSort(int* arr, int len)
{//第一次建立大根堆（從后往前，多次調整）//根分別為4 3 2 1的子樹for (int i = (len-1-1)/2; i >= 0; i--)//i的初值與結點總數有關，i=總結點數len-根-{HeapAdjust(arr, i, len - 1);}//每次將根和待排序的最后一個交換，然后再次調整（注意是待排序部分）int tmp;//用于交換for (int i = 0; i < len - 1; i++){tmp = arr[0];arr[0] = arr[len - 1 - i];arr[len - 1 - i] = tmp;//再次調整HeapAdjust(arr, 0, len - 1 - i - 1);}return;
}

3.復雜度分析?

建立大根堆的時間復雜度：O(n)

每次調整大根堆時間復雜度：O(logn)，調整次數n-1次，總時間復雜度O(nlogn)

綜合建堆和排序兩個階段，堆排序的時間復雜度為O(n+nlogn)，通常簡化為O(nlogn)。這是堆排序的平均時間復雜度；

空間復雜度O(1)；

不穩定

三、歸并排序

1.算法思想

歸并排序的基本思想是將一個數組分成兩個子數組，對每個子數組進行排序，然后將排序好的子數組合并成一個排序好的數組。這個過程是遞歸進行的，直到子數組的長度為 1，此時子數組已經是有序的。

1.分解：將待排序的數組不斷地分成兩半，直到每個子數組只有一個元素。可以使用遞歸實現這一步驟。
2.合并：將兩個已經排序好的子數組合并成一個排序好的數組。在合并過程中，比較兩個子數組的元素，將較小的元素依次放入一個臨時數組中，直到其中一個子數組的元素全部被放入臨時數組。然后將另一個子數組中剩余的元素全部放入臨時數組。最后將臨時數組中的元素復制回原數組。

注意邊界越界。?

2.代碼實現

//歸并排序
//一次歸并
//gap：歸并段的長度
static void Merge(int* arr, int len, int gap)
{int low1 = 0;//第一個歸并段的起始下標int high1 = low1 + gap - 1;//第一個歸并段的結束下標int low2 = high1 + 1;//第二個歸并段的起始下標int high2 = low2 + gap - 1 < len - 1 ? low2 + gap - 1 : len - 1;//第二個歸并段的結束下標//防止越界//存放歸并好的數據int* brr = (int*)malloc(len * sizeof(int));assert(brr != NULL);int i = 0;//brr的下標//有兩個歸并段while (low2 < len)//表面至少存在兩個歸并段{//兩個歸并段都有數據，需要比較low1和low2while (low1<=high1&&low2<=high2){if (arr[low1] <= arr[low2]){brr[i++] = arr[low1++];}else{brr[i++] = arr[low2++];}//誰小存誰}//一個歸并段的數據已經完成了，另一個還有數據while (low1 <= high1)//第一個歸并段還有數據{brr[i++] = arr[low1++];}while (low2 <= high2)//第二個歸并段還有數據{brr[i++] = arr[low2++];}//下兩個歸并段low1 = high2 + 1;high1 = low1 + gap - 1;low2 = high1 + 1;high2 = low2 + gap < len ? low2 + gap - 1 : len - 1;}//只有一個歸并段while (low1<len){brr[i++] = arr[low1++];}//將歸并好的數據拷貝到arr中for (i = 0; i < len; i++){arr[i] = brr[i];}free(brr);
}void MergeSort(int* arr, int len)
{for (int i = 1; i < len; i *= 2){Merge(arr, len, i);//一次歸并}
}

3.復雜度分析

歸并排序是一種基于分治思想的排序算法：

時間復雜度：
最好情況：當待排序序列已經是有序的時候，歸并排序依然需要進行logn層的歸并操作，每層歸并操作需要比較和移動n次元素，所以時間復雜度為O(nlogn)。
最壞情況：當待排序序列是逆序的時候，同樣需要logn層歸并操作，每層歸并操作也需要比較和移動n次元素，時間復雜度也是O(nlogn)。平均情況：歸并排序將序列分成兩部分，然后對兩部分分別排序，再將排好序的兩部分合并。

在平均情況下，每次劃分都能將序列分成大致相等的兩部分，所以時間復雜度為O(nlogn)。

空間復雜度：歸并排序在合并過程中需要借助額外的存儲空間來存放臨時數據，最壞情況下需要
O(n)的輔助空間來完成排序。

穩定性：歸并排序是穩定的排序算法。在歸并過程中，當左右兩個子序列中出現相等元素時，先將左邊子序列中的元素放入臨時數組，然后再將右邊子序列中的元素放入臨時數組，這樣相等元素的相對順序在排序前后不會發生改變。
綜上所述，歸并排序的時間復雜度為O(nlogn)，空間復雜度為O(n)，并且是穩定的排序算法。

以上是排序算法第三部分關于選擇排序、堆排序以及歸并排序的知識，如果有幫助可以點贊收藏一下，會持續更新輸出有用的內容，感興趣可以關注我！