标题：[数据结构] 基于选择的排序 选择排序&&堆排序
@水墨不写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 child int 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; }
完~
未经作者同意禁止转载
