选择排序的思想很简单，就是在数组找到一个最大的然后放到最后面（升序）、最前面（降序），或者找一个最小的放到最前面（升序）最后面（降序）。此外还有优化方案就是从两边开始，同时找最大的和最小的，找的后放到正确的位置
void SelectSort1(vector<int>& v) { if (v.empty()) { return; } int i = 0; int j = 0; for (i = 0; i<v.size() - 1; i++)//控制交换的次数 { int min = i; for (j = i; j<=v.size() - 1; j++)//在该区间找到最小的 { if (v[j]<v[min]) { min = j; } } if (min != i) { swap(v[i], v[min]);//把最小的放到当开始的位置，下一交换就是下一个位置，同时在这个位置后面寻找最小的 } } } void SelectSort2(vector<int>& v) { if (v.empty()) { return; } int left = 0; int right = v.size() - 1; while (left < right) { int min = left; int max = right; int i = left; for (i = left; i <= right; i++)//从两边开始同时寻找最大的和最小的 { if (v[i]>v[max]) { max = i; } if (v[i] < v[min]) { min = i; } } swap(v[left], v[min]); if (max == left)//这里的判断是为了避免最大的在left这个位置，而一交换，最大的数位置就会改变。 { max = min; } swap(v[right], v[max]); left++; right--; } } 选择排序是一种不稳定的排序（4，4，3第一个4就会移到第二个4后面），时间复杂度为O(n^2)堆 大堆：每个父子节点都大于孩子节点 小堆：每个父子节点都小于孩子节点
堆排序也是选择排序的一种。如果升序就建大堆，每次取堆顶的数往最后放（swap(heap[0],heap[end])）,交换往后该堆就不是一个大堆了（除最后一个放好的数），从开始位置进行一次向下调整，又将其调整为一个大堆，把堆顶与最后次位置进行交换，依次这样进行排序。如果降序建小堆
class Solution { public: /** * @param A an integer array * @return void */ /*void AdjustDown(vector<int>& a,int n,int root) { int parent=root; int child=parent*2+1; while(child<n) { if(child<n-1&&a[child+1]>a[child]) { child++; } if(a[parent]<a[child]) { swap(a[parent],a[child]); parent=child; child=parent*2+1; } else { break; } } } void sortIntegers2(vector<int>& A) { // Write your code here int i=0; for(i=(A.size()-2)/2;i>=0;i--) { AdjustDown(A,A.size(),i); } int end=A.size()-1; while(end>0) { swap(A[end],A[0]); AdjustDown(A,end,0); end--; } }*/ };此外我们也可以这样实现堆排序 void sortIntegers2(vector& v) {
make_heap(v.begin(),v.end()); sort_heap(v.begin(),v.end()); }