本篇文章將帶你詳細了解八大基本排序中的選擇排序

---

目錄

（一）選擇排序的時間復雜度和空間復雜度及穩定性分析

（二）代碼實現

(三)輸出結果

---

選擇排序的基本原理是：每次從待排序的數組中找出最大值和最小值。具體流程是：每次找出最大值和最小值之后，把最大值和數組的右邊界互換，把最小值和數組的左邊界互換。這樣，第一次找出的最大值和最小值就被放好了。然后由于數組的左右邊界已經在正確的位置了，所以我們把左邊界加1，右邊界-1.這樣新的數組仍然是待排序的數組，然后由此類推，直到左邊界大于右邊界為止。這里附上GIF動圖。

（一）選擇排序的時間復雜度和空間復雜度及穩定性分析

我們以每次選出最大值或最小值的簡單選擇排序來分析。

• 當數組有序時，選擇排序仍要遍歷整個數組，然后從中選出最值放在邊界。這里的時間復雜度是O（N）。重復上述過程，整個排序的時間復雜度就是O（N方）了。
• 同理，當數組無序時，也同樣是當數組有序時的處理，所以時間復雜度也是O（N方）

至于空間復雜度

• 整個排序沒有多余的空間產生，所以空間復雜度是O(1)

穩定性分析

• 每次選出的最大值和最小值，并不能保持在相同大小的相對位置。所以選擇排序是不穩定的排序

（二）代碼實現

//選擇排序的實現。我們每次選出最大值或最小值，分別與數組的兩個邊界互換。void Select(int* arr, int n)
{//形參列表的arr是待排序數組，n是數組的大小//開始的邊界就是數組的左右邊界int begin = 0;int end = n - 1;//n-1是數組最后一個元素的下標while (begin < end){//進入循環//找到最大值和最小值int maxi = begin;int mini = begin;for (int i = begin + 1; i <= end; i++){if (arr[i] > arr[maxi]){maxi = i;  }if (arr[i] < arr[mini]){mini = i;}}//找到最大值和最小值后，與數組邊界交換//這里注意的是當待排序數組只有兩個時，并且最大值是下標是前一個，最小值的下標是后一個時//交換了2次就等同于沒有變。//所以我們得防止這樣的情況if (maxi == begin){maxi = mini;}//我們寫一個下標交換函數    Swap(&arr[begin]. &arr[mini]);Swap(&arr[end], &arr[maxi]);begin++;end--;}   
}int main()
{//產生無序數組int arr[10] = {10, 9, 8, 7, 6, 5, 4, 3, 2, 1};int n = sizeof(arr) / sizeof(arr[0]);//n是數組的大小Select(arr, n);}

(三)輸出結果

?