软考程序员考试考点：选择排序

选择排序的基本思想是每步从待排序的记录中选出排序码最小的记录，顺序存放在已排序的记录序列后面，直到全部排完。选择排序中主要使用直接选择排序和堆排序。

1、直接选择排序

直接选择排序的过程是，首先在所有记录中选出排序码最小的记录，把它与第一个记录交换，然后在其余的记录内选出排序码最小的记录，与第二个记录交换……，依次类推，直到所有记录排完为止。直接选择排序的平均时间复杂度为，是不稳定排序。

直接选择排序用C语言实现如下：

2、堆排序

堆排序是一种树形选择排序，是对直接选择排序的有效改进。n个关键字序列K1.K2.……,Kn称为堆，当且仅当该序列满足(Ki≤K2i且Ki≤K2i+1)，(1≤i≤n)。Ki相当于二叉树中的非叶节点，K2i,K2i+1相当于Ki的左右儿子。根结点(堆顶)的关键字是堆里所有结点关键字中最小者，称为小根堆;根结点的关键字是堆里所有结点最大者，称为大根堆。

堆排序的最坏时间负责度为O(nlog2n),堆排序的平均性能接近于最坏性能。由于建初始堆的比较次数较多，所以堆排序不适合记录较少的文件。堆排序就是就地排序，辅助空间为O(1)，它是不稳定排序。

堆排序的关键步骤有两个，一是如何建立初始堆;二是当堆的根结点与堆的最后一个结点交换后，如何对少了一个结点后的结点序列做调整，使之重新称为堆。