排序算法之选择排序（简单选择排序、堆排序）

选择排序

选择排序的基本思想是：每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列。

简单选择排序 概念

假设排序表为L[1…N]，，第i趟排序即从L[1…N]中选择关键字最小的元素与L（i）交换，每一趟排序可以确定一个元素的最终位置，这样经过n-1趟排序就可以使得整个排序表有序。

算法实现

void select_sort(ElemType A[],int n) { int i, j,min; for (i = 0; i < n-1; i++) { min = i; //	记录最小元素位置 for (j = i + 1; j < n; j++) //在A【i...n-1】中选取最小的元素 if (A[j] < A[min]) min = j; //更新最小元素位置 if (min != i) swap(A[i],A[min]); } } 

堆排序 概念

1. 堆排序要结合顺序存储的完全二叉树的特性进行学习。 对于完全二叉树而言：

• 结点 i 的左孩子是 2i
• 结点 i 的右孩子是 2i+1
• 结点 i 的父节点是 i/2
• 编号 <= n/2的结点都是分支结点

1. n个关键字序列L[1…N]称为堆。 当且仅当 L(i) >=L(2i) 且 L(i)>=L(2i+1) 可以将该一维数组视为一棵完全二叉树，满足此条件的堆称之为大根堆。大根堆的最大元素存放在根节点，且其任一非根节点的值小于等于其双亲结点值。 小根堆反之。
2. 堆排序的思路很简单：首先将存放在L[1…N]中的N个元素建成初始堆，由于堆本身的特点（以大根堆为例），堆顶元素就是最大值。输出堆顶元素后，通常将堆底元素送入堆顶，此时根节点已不满足大顶堆的性质，对被破坏，将堆顶元素向下调整使其继续保持大顶堆的性质，再输出堆顶元素。如此重复，直到堆中仅剩一个元素为止。
3. 构建初始堆的方法：先对完全二叉树的最右下边的子树调整，使其成为堆（如果此节点的孩子有比他大的，则将最大的孩子和父节点调换），之后向前依次对各节点（[N/2]-1~1）为根的子树进行筛选，看该节点是否大于其左右孩子的值，若不大于则交换，交换后可能会破坏下一级的堆，于是采用上述方法继续构建下一级的堆，直到以该节点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根节点。

算法实现

void Build_Max_Heap(ElemType A[],int len) { //构建大根堆 int i; for (int i = len / 2; i > 0; i--) //从i=[n/2]~1,反复调整堆 HeadAdjust(A,i,len); } void HeadAdjust(ElemType A[],int k,int len) {//将元素k为根的子树进行调整 int i; A[0] = A[k]; //A[0]暂存子树的根节点 for (i = 2 * k; i <= len; i*=2) //沿key较大的子节点向下筛选 { if (i < len && A[i] < A[i + 1]) { i++; //取较大的子节点的下标 } if (A[0] >= A[i]) break; //筛选结束 else { A[k] = A[i];//将A[i]调整到双亲结点上 k = i;//修改k值，以便继续向下筛选 } } A[k] = A[0]; //被筛选结点的值放入最终位置 } void Heap_Sort(ElemType A[],int len) {//堆排序 int i; Build_Max_Heap(A,len);//初始建堆 for (i = len; i > 1; i++) //n-1趟的交换和建堆过程 { swap(A[i],A[1]); //输出堆顶元素（和堆底元素互换） HeadAdjust(A,1,i-1);//调整，把剩余的i-1个元素整理成堆 } } 

后续

如果想了解更多物联网、智能家居项目知识，可以关注我的程序设计专栏。 订阅专栏后，可以在微信公众号上私聊我，直接发给你源码。 或者关注公众号。

编写不易，感谢支持。