数据结构：选择类型排序的总结（考研）
选择排序包括：选择排序，双选择排序以及堆排序。 选择排序的核心是每一趟排序中查找最小值或者最大值的索引，然后与边界的位置进行交换。例如当前待排序的元素值为a[i]，设置最小值所对应的索引为minIndex，初始值就为i。这样一次循环后，minIndex的值可能会变，也可能不变，只有当变化的时候我们交换一下即可。下面看一下常见的选择类型的排序。
(1)选择排序
void selectSort(int *a, int n) {
for(int i=0; i<n; ++i) {
int minIndex = i;//记录最小值所对应的索引 初始值为i
//查找最小值所对应的索引
for(int j=i+1; j<n; ++j) {
if(a[j] < a[minIndex]) minIndex = j;
}
//最小值索引发生了改变 我们就交换他俩
if(i != minIndex) swap(a[i], a[minIndex]);
}
}(2)双选择排序
双选择排序本质上还是选择排序，可以说只是对直接选择排序做了优化。双选择排序每趟循环中同时找到最大值和最小值的索引，最大值和最小值初始的索引为待排序数组的两个边界，当一趟查找结束后，如果有索引发生了变化，就进行交换。
void biSelectSort(int *a, int n) {
int left=0, right=n-1;//待排序数组的两个边界
//只有当数组中还有两个元素时才需要进行排序 只有一个时数组已经有序
while(left < right) {
int minIndex=left, maxIndex=right;
//保证最小值一定小于最大值
if(a[minIndex] < a[maxIndex]) swap(a[minIndex], a[maxIndex]);
//在[left+1, right-1]闭区间中 查找最大值和最小值的索引
for(int i=left+1; i<right; ++i) {
if(a[i] < a[minIndex) minIndex = i;
else if(a[i] > a[maxIndex]) maxIndex = i;
}
swap(a[left], a[minIndex]);
swap(a[right], a[maxIndex]);
left ++, right --;//缩小范围
}
}(3)堆排序
堆排序在底层中使用了堆这样的数据结构，堆维护的性质是，若为大根堆，则任意根节点的值大于其左右孩子节点的值。堆同时是一完全二叉树的的逻辑结构，堆很方便的可以使用数组来实现，因此是一种线性的存储结构，方便编程，主要利用到是完全二叉树的性质：
1.若任意节点的索引为j,若其左右孩子都存在，则它们的索引分别是2 * j和2*j+1。
2.任意节点的父亲节点的索引为j/2，满足这样关系的前提条件是数组下标从1开始，否则若根节点的下标从0开始判断比较麻烦，需要讨论奇偶性。所以在实现的时候我们需要多开辟一个存储空间，因为鼠标下标为0的位置不使用。
下面来看堆排序的简单实现：
void heapSort(int *a, int n) {
Heap<int> heap(n);
for(int i=0; i<n; ++i) heap.insert(a[i]);
for(int i=0; i<n; ++i) a[i] = extractMin();
}时间复杂度的分析：在heapSort的实现过程中，insert方法中会涉及shitfUp操作，shiftUp操作的时间复杂度为O(logn)，外层循环的时间复杂度为O(n)，因此第一层总的时间复杂度为O(n * logn), 同样第二层循环，外层循环的时间复杂度为O(n)， 内层extractMin()函数会涉及到shiftDown操作， shiftDown操作的时间复杂度为O(logn), 因此总的时间复杂度也为O(n * logn), 所以最终总的时间复杂度任为O(n * logn)。 下面来看小根堆的简单实现：
#include <iostream>
#Include <cassert>
using namespace std;
template <typename T>
class Heap{
private:
int cnt;//当前堆中的节点个数
int capacity;//堆的容量
T *data;//存放数据的线性结构
void shiftDown(int k) {
while(2 * k <= cnt) {
int j = 2 * k;//j此时为左孩子节点的索引
//有孩子节点存在 并且有孩子节点比左孩子节点还小 j++
if(j + 1 <= cnt && data[j+1] < data[j]) j ++;
if(data[k] <= data[j]) break;//如果根节点比min(data[j], data[j+1])更小，break掉
swap(a[k], a[j]);
k = j;
}
}
void shiftUp(int k) {
while(k>1 && data[k/2] > data[k]) {
swap(data[k/2], data[k]);
jk /= 2;
}
}
public:
Heap(int capacity) {
this->cnt = 0;//初始堆中没有节点，初始化为0
this->capacity = capacity;
//注意这里很重要， data中下标为0位置并不使用，因此需要多开辟一个存储空间
data = new T[capacity + 1];
}
~Heap() {delete [] data;}
void insert(int x) {
assert(cnt + 1 <= capacity);
data[cnt + 1] = x;
shiftUp(cnt + 1);
cnt ++;
}
T extractMin() {
assert(cnt > 0);
T res = data[1];
swap(data[1], data[cnt]);
cnt --;
shiftDown(1);
return res;
}
};