目錄

前言??????

一.選擇排序

1.思想

2.實現

3.特點

二.堆排序

1.思想

2.實現

3.特點

---

前言??????

?????????排序算法是計算機科學中的基礎工具之一，對于數據處理和算法設計有著深遠的影響。了解不同排序算法的特性和適用場景，能夠幫助程序員在特定情況下選擇最合適的算法，從而提高程序的效率和性能。本節我們講述選擇排序和堆排序。

一.選擇排序

1.思想

基本思想是在未排序的部分中選擇最小和最大的元素，然后將其與未排序部分的第一個元素和最后一個交換位置。重復這個過程，直到整個序列有序。

選擇排序的步驟如下：

1. 初始狀態： 將整個序列分為已排序部分和未排序部分，初始時已排序部分為空，未排序部分包含所有元素。

2. 選擇最小元素： 在未排序部分中找到最小和最大的元素，并記錄其位置。

3. 交換位置： 將找到的最小元素與未排序部分的第一個元素交換位置。最大元素與最后一個元素交換。

4. 更新已排序部分和未排序部分： 將交換后的元素視為已排序，將原未排序部分減少二個元素，繼續從未排序部分重復步驟2和步驟3。

5. 重復直至完成： 重復上述過程，直到整個序列有序。

2.實現

void SelectSort(int* a, int n)
{int gap = 0;int end = n - 1;while (gap < end){int maxi = gap, mini = gap;for (int i = gap+1; i <= end; i++){if (a[mini] > a[i]){mini = i;}if (a[maxi] < a[i]){maxi = i;}}Swap(&a[gap], &a[mini]);if (gap == maxi){maxi = mini;}Swap(&a[end], &a[maxi]);gap++;end--;}
}

????????注意:為了避免最大值為第一個時,被最小值交換時換走,我們修正一下,如果第一個值就是最大值,那么當第一個值與最小值交換后,修正最大值的位置

時間復雜度:O(n^2)

空間復雜度O(1)

穩定性:不穩定

3.特點

1.優勢:

1. 交換操作相對較少： 選擇排序的交換操作次數相對較少，每次只進行一次交換。這使得它在某些場景下可能比冒泡排序更有效。

2. 適用于小規模數據集： 在數據規模較小的情況下，選擇排序的性能可能相對較好，因為其簡單性和交換操作的相對少。

2.缺點

1. 時間復雜度高： 選擇排序的時間復雜度為O(n^2)，其中n是待排序序列的長度。這意味著對于大規模數據集，選擇排序的性能可能相對較差，尤其是與一些O(nlog n)時間復雜度的算法相比。

2. 不穩定： 選擇排序是一種不穩定的排序算法。當存在相等元素時，它可能會改變它們的相對順序，使得選擇排序在某些應用場景中不適用。

3. 對逆序數據的不足： 在對逆序數據（完全逆序排列的情況）進行排序時，選擇排序的性能較差。每次選擇最小元素時，都需要在未排序的部分中進行線性搜索，導致交換操作次數較多。

二.堆排序

1.思想

堆排序是一種基于二叉堆（Binary Heap）數據結構的排序算法。堆是一個特殊的樹狀數據結構，其中每個節點的值都不大于或不小于其子節點的值。堆可以分為最大堆和最小堆。(可以看這個堆的實現與操作-CSDN博客)

堆排序的基本思想如下：

1. 建堆： 將待排序序列構建成一個二叉堆。對于最大堆，父節點的值大于或等于其子節點的值；對于最小堆，父節點的值小于或等于其子節點的值。

2. 排序： 不斷將堆頂元素與堆的最后一個元素交換，然后對除最后一個元素外的部分重新調整成堆。這樣，每次交換后，最大或最小元素就被放置在了正確的位置。重復這個過程，直到整個序列有序。

2.實現

void AdjustDown(int* a,int parent,int size)//向下調整建堆
{int child = parent *2 + 1;while (child < size){if (child+1<size&&a[child] < a[child + 1])child++;if (a[parent] < a[child]){Swap(&a[parent], &a[child]);parent = child;child = parent*2 + 1;}else{break;}}
}
void HeapSort(int* a, int n)//堆排序
{for (int i = (n - 1) / 2; i >= 0; i--){AdjustDown(a, i, n);}int end = n-1 ;while (end){Swap(&a[0], &a[end]);AdjustDown(a, 0, end );end--;}
}

????????這里我們采用向下調整建堆,從第一個非葉子節點開始,建大堆后,每次將堆頂元素調整到數組后面,再調整堆

時間復雜度:O(nlogn)

空間復雜度O(1)

穩定性:不穩定

3.特點

1.優勢:

1. 時間復雜度穩定： 堆排序的時間復雜度為O(n log n)，其中n是待排序序列的長度。這使得堆排序在大規模數據集上具有相對較好的性能。

2. 適用于大規模數據： 由于其O(n log n)的時間復雜度，堆排序對于大規模數據集的排序任務是一個較好的選擇，特別是相對于一些O(n^2)復雜度的排序算法。

2.缺點:

1. 不穩定性： 堆排序是一種不穩定的排序算法。在交換的過程中，可能會改變相同元素的相對順序。對于需要保持相等元素相對位置關系的應用場景，不穩定性可能是一個不可接受的缺點。

2. 對于小規模數據： 盡管堆排序在大規模數據集上表現良好，但在小規模數據集上，它的性能可能不如一些簡單且更容易實現的排序算法，如快速排序或插入排序。