选择排序

选择排序的基本思想： 每⼀次从待排序的数据元素中选出最⼩（或最⼤）的⼀个元素，存放在序列的起始位置，直到全部待 排序的数据元素排完。

直接选择排序

1. 在元素集合 array[i]--array[n-1] 中选择关键码最⼤(⼩)的数据元素

2. 若它不是这组元素中的最后⼀个(第⼀个)元素，则将它与这组元素中的最后⼀个（第⼀个）元素 交换

3. 在剩余的 array[i]--array[n-2] （ array[i+1]--array[n-1] ） 集合中，重复上述步骤，直到集合剩余1个元素

例：

标记好第一个元素和最后一个元素的位置begin,end,然后设置最大值位置maxi和最小值位置mini,令其初始化。从begin开始到end结束，依次遍历找到最大值位置和最小值位置

最后交换begin与mini,end与maxi,begin++,end--

重复上述步骤，直至begin>end,排序完成

特殊情况：begin==maxi,end==mimi

交换begin与mini,end与maxi,begin++,end--

7,2位置不变，排序错误。

原因：7，2交换两次，等同没有交换

处理：令maxi==end or mini==begin,使其只交换一次

代码如下

void DirectSelectSort(int* arr, int n)
{int begin = 0, end = n - 1;while (begin < end){int maxi = begin, mini = begin;for (int i = begin;i <= end; i++){if (arr[i] > arr[maxi])maxi = i;if (arr[i] < arr[mini])mini = i;}if (maxi == begin && mini == end)    //特殊情况，特殊处理maxi = end;Swap(&arr[begin], &arr[mini]);Swap(&arr[end], &arr[maxi]);begin++, end--;}
}

堆排序

堆排序(Heapsort)是指利⽤堆积树（堆）这种数据结构所设计的⼀种排序算法，它是选择排序的⼀ 种。它是通过堆来进⾏选择数据。需要注意的是排升序要建⼤堆，排降序建⼩堆。

向下调整算法

堆的删除： 删除堆是删除堆顶的数据，将堆顶的数据根最后⼀个数据⼀换，然后删除数组最后⼀个数据，再进⾏ 向下调整算法

向下调整算法有⼀个前提：左右⼦树必须是⼀个堆，才能调整。

向下调整算法建堆时间复杂度为： O(n)

堆排序

数组建堆，⾸尾交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整选出次⼤的数据

堆排序时间复杂度为： O(nlogn)

//向下调整算法
void AdjustDown(int* arr, int parent, int n)    //n是堆中元素个数
{int child = parent * 2 + 1;while (child < n){// 假设法，选出左右孩⼦中大的那个孩⼦if ((child + 1) < n && arr[child+1] > arr[child])child++;//> 建大堆//< 建小堆if (arr[child] > arr[parent]){Swap(&arr[parent], &arr[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}
//堆排序
void HeapSort(int* arr, int n)
{//child n-1   parent (child-1)/2// a数组直接建堆    O(N)for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, n);}int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}
}