选择类排序 （简单选择排序，堆排序）— c语言实现
选择类排序包括：
(1) 简单选择排序
（2）树形选择排序
（3）堆排序
简单选择排序：
【算法思想】：在第 i 趟简单选择排序中，从第 i 个记录开始，通过 n - i 次关键字比较，从 n - i + 1 个记录中选出关键字最小的记录，并和第 i 个记录进行交换
时间复杂度：O(n^2)
1 //此函数中a[0]不用，即对 a[1] ~ a[length-1] 排序；
//如果对a[0]~a[length-1]排序，将 for 循环中的 i = 1 改为 i = 0 即可，注意输出
2 void select(int a[],int length){//length为数组的长度
3 int i,j;
4 int min;//记录最小值的位置
5
6 for(i = 1;i < length - 1;i++){
7 min = i;
8 //选择最小的值
9 for(j = i + 1;j < length;j++){
10 if(a[j] < a[min]) //更新最小值的坐标
11 min = j;
12 }
13 if(min != i){
14 int temp;
15 temp = a[min];
16 a[min] = a[i];
17 a[i] = temp;
18 }
19 }
20 }
堆排序:
堆排序是威洛母斯在1964年提出的对树形选择排序的改进算法，其只需要一个记录大小的辅助空间，采用向量数组方式存储，采用完全二叉树的顺序结构的特征进行分析，而非采用树的存储结构。
从小到大排序采用大根（顶）堆：r[i].key >= r[2i].key && r[i].key >= r[2i+1].key (结点值大于等于其左子与右子）
从大到小排序采用小根（顶）堆：r[i].key <= r[2i].key && r[i].key<= r[2i+1].key (结点值小于等于其左子与右子）
【算法思想】把待排序的记录的关键字存放在数组 r[1...n] 中，将 r 看成一棵完全二叉树的顺序表示，每个结点表示一个记录，第一个记录 r[1] 作为二叉树的根，以下各记录 r[2] ~ r[n] 依次逐层从左到右顺序排列，任意结点 r[i] 的左孩子是 r[2i] ,右孩子是 r[2i+1]，双亲是 r[i/2]。对这棵二叉树进行调整建堆。
时间复杂度：O（nlog2n)
说明：在c语言中，i/2 的含义是整除，不同于数学中的定义，即 3/2 = 1，有一个向下取整的意思
堆排序可分为2步（从小到大排序）：
<1> 建初堆：建立一个大根堆
<2>重建堆：进行 n - 1 趟的交换（r[1] 与 堆尾进行交换）和建堆的过程
1 /*堆排序*/
2 /*建初堆：大根堆*/
3 void AdjustDown(int a[],int k,int len);
4 void BuildMaxHeap(int a[],int len){
5 int i;
6 for(i = len/2;i > 0;i--){
7 AdjustDown(a,i,len);
8 }
9 }
10 //调整堆
11 void AdjustDown(int a[],int k,int len){
12 a[0] = a[k];//将第一个记录移出
13 int i;
14 for(i = 2*k;i <= len;i = 2*i){
15 if(i < len && a[i] < a[i+1])//不能忘记i < len,否则会超出范围
16 i++;//取左右子中的最大值
17 if(a[0] >= a[i])
18 break;
19 else{
20 a[k] = a[i]; //将a[i]调整到其双亲结点上
21 k = i; //修改k值，以便继续向下筛选
22 }
23 }
24 a[k] = a[0];
25 }
26
27 void HeapSort(int a[],int len){
28 BuildMaxHeap(a,len);
29 int i;
30 int temp;
31 for(i = len;i > 1;i--){
32 //第一个和堆尾进行交换
33 temp = a[1];
34 a[1] = a[i];
35 a[i] = temp;
36 //调整堆
37 AdjustDown(a,1,i-1);
38 }
39 }
图可参照：https://blog.csdn.net/u013384984/article/details/79496052
测试：
1 int main(){
2 int a[11] = {-1,2,3,1,4,7,3,5,1,6,0};
3 int b[11] = {-1,2,3,1,4,7,3,5,1,6,0};
4 int i,j;
5 select(a,11); //没有用a[0],对后面的元素进行排序
6 HeapSort(b,10);//数组的最后一个下标，a[0]为辅助单元
7 for ( i = 1;i < 11;i++){
8 printf("%d \t",a[i]);
9 }
10 printf("\n");
11
12 for ( i = 1;i < 11;i++){
13 printf("%d \t",b[i]);
14 }
15 printf("\n");
16 }