標題：[數據結構] 基于選擇的排序 選擇排序&&堆排序

@水墨不寫bug

---

（圖片來源于網絡）

---

目錄

（一）選擇排序

實現：(默認從小到大排序)

優化后實現方法：

（二）堆排序

實現： （從小到大排序）

---

?

正文開始：

（一）選擇排序

????????時間復雜度：O（N^2）

????????空間復雜度：O (1)

????????穩定性：不穩定

基本思想：

? ? ? ? 每次從待排序的數據元素中選出一個最大（或最小）的一個元素，存放在序列的起始位置，直到數據有序。

實現：(默認從小到大排序)

void SelectSort(vector<int>& nums)
{int n = nums.size();int begin = 0, end = n - 1;for (int j = 0; j < n-1; ++j){int maxi = 0;for (int i = 0; i < n-j; ++i){if (nums[maxi] < nums[i]){maxi = i;}}swap(nums[end--], nums[maxi]);}
}

選擇排序仍然有一種優化方法：

? ? ? ? 每次選擇的時候，可以同時選擇兩個數，這樣就可以減少遍歷的次數，提高效率。

優化后實現方法：

void SelectSort(vector<int>& nums)
{int n = nums.size();int begin = 0, end = n - 1;while(begin < end){int maxi = begin, mini = begin;for (int i = begin; i <= end; ++i){if (nums[maxi] < nums[i]){maxi = i;}if (nums[mini] > nums[i]){mini = i;}}swap(nums[mini], nums[begin]);if (maxi == begin){maxi = mini;}swap(nums[maxi], nums[end]);begin++;end--;}
}

?但是這種實現方法會導致一個問題：

? ? ? ? 由于每次選兩個值，當最大值下標就是區間左端點時，由于需要將最小值放在左端點，這樣會使最大值下標失效，于是就需要修正最大值下標：

? ? ? ? 當最小值下標與區間左端點begin交換后，判斷最大值下標是否指向區間左端點，如果是，則將其修正為交換后的最小值下標的位置。

下標交換只有四種情況：

其實這個問題的本質是：

? ? ? ? 將最小值交換到最前面的操作是先進行的，先進行的過程會對后進行的過程產生干擾。

? ? ? ? 最小值下標與區間左端點交換導致的最大值下標失效的問題，需要修正最大值下標。

（二）堆排序

?堆排序實現過程：默認排升序

????????時間復雜度：O（N*logN）

????????空間復雜度：O（1）

????????穩定性：不穩定

? ? ? ? 特點：小堆排降序，大堆拍升序。

? ? ? ? 小堆可以得到最小的數，然后將最小的數排除，在剩余的數中再次找到最小的數，依次類推；大堆類似。

實現原理：

? ? ? ? 用到了向下調整法建堆的過程：以大堆排升序為例

? ? ? ? 一般堆是由連續的數組模擬實現的邏輯結構，每次將堆頂最大的數移動到數組末尾后，需要向下調整來保持堆的特性。在向下調整之后，最大值就到了數組的末尾，堆也保持了其特性，接下來繼續重復即可。

實現： （從小到大排序）

void AdgustDown(vector<int>& nums,int pos,int size)
//排序的過程size是變化的，動態的，每完成一個數據，size要動態減小
{int n = size;int parent = pos;//find max childint child = pos * 2 + 1;while (child < n){//假設左孩子大if (child + 1 < n && nums[child] < nums[child + 1]){child++;}if (nums[parent] < nums[child]){swap(nums[parent], nums[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//大堆排升序
void HeapSort(vector<int>& nums)
{int n = nums.size();//建堆過程for(int i = (n-1-1)/2;i >= 0;--i){ AdgustDown(nums, i,n);}Print(nums);//排序過程for(int j = 0; j < n;++j){int size = n - 1 - j;swap(nums[0], nums[size]);AdgustDown(nums, 0, size);}
}
int main()
{vector<int> nums = { 99,0,7,5,44,3,78,653,90,81 };Print(nums);HeapSort(nums);Print(nums);return 0;
}

---

完~

未經作者同意禁止轉載?