1.选择排序
1.1选择排序的基本思想
基本思想：
遍历一遍待排数据，将最大值与最小值的下标记录，然后把最小值与数组最前面的数据交换，将最大值与数组最后一个数据交换，这样遍历一遍，就将最大值和最小值放到了正确的位置；
将除了上面已经在正确位置的数据，将剩下的数据看成待排数组，然后重复上述操作，这样，遍历2/n次，就可以将所有数据排好序；
图解：
1.2代码实现
void SelectSort(int* a, int n) { for (int j = 0; j < n/2; j++) { //假设数组中最大最小值的下标是j int maxi = j; int mini = j; for (int i = j; i < n -j; i++) { //有比max大的，就改变下标 if (a[i] > a[maxi]) { maxi = i; } //有比min小的，就改变下标 if (a[i] < a[mini]) { mini = i; } } //将找到的最小值放到待排数组最前面 Swap(&a[mini], &a[j]); //如果最大值在待排数组最前面，在把最小值换到前面的时候，会将最大值的下标改变 //所以这里需要更新最大值的下标，如上图第三步中8的交换 if (maxi == j) { maxi = mini; } //将最大值放到待排数组的后面 Swap(&a[maxi], &a[n - 1-j]); } }
1.3性能分析
最坏情况：逆序
时间复杂度：O(N^2)
空间复杂度：O(1)
2.堆排序
要了解堆排序要先了解堆，堆的相关知识http://t.csdnimg.cn/GoxJO
2.1堆排序的基本思想
利用大堆的特点，父亲都大于孩子，所以堆的根结点是整个二叉树中的最大数；
先将根结点与树中最后一个节点交换（对应在数组中，就是将数组中第一个数据与最后一个数字交换），这样，最大的数就在数组最后，在正确的位置上了，交换过后，（树的左右子树都是大堆）这样再利用向下调整建堆，将剩下的数据变成大堆，这样最大的数据又在根结点了，重复上面操作就可以将所有数据变成有序；
图解：
2.2代码实现
void Adjustdown(int* a, int parent, int n) { assert(a); int child = parent * 2 + 1; while (child < n) { //假设左孩子大 if (child + 1 < n && a[child] < a[child + 1]) { //假设不成立，调整 child = child + 1; } if (a[child] > a[parent]) { Swap(&a[parent], &a[child]); parent = child; child = child * 2 + 1; } else { break; } } } void HeapSort(int* a, int n) { assert(a); //从最后一个非叶子节点向下调整 //n-1是最后一个结点，（n-1-1）/2是它父亲 for (int i = (n-1-1) / 2; i >= 0; i--) { Adjustdown(a, i, n); } int end = n-1; while (end > 0) { Swap(&a[0],&a[end]); Adjustdown(a,0, end); end--; } }
2.3性能分析
数据个数为N，则高度为：logN
N个数据，每个数据向下调整，时间复杂度需要logN
时间复杂度：O(N*logN)
空间复杂度为：O(N)
