选择排序的基本思想是每次从待排序的数据元素集合中选取最小或最大的数据元素放到数据元素集合的最前面或最后面，数据元素集合不断缩小，当数据元素集合为空时，选择排序结束。常用的选择排序有直接选择排序和堆排序两种。
1、直接选择排序
直接选择排序是从待排序的数据元素集合中选取最小的数据元素并将它与原始数据元素集合中的第一个数据元素交换位置；然后从不包括第一个位置上的数据元素的集合中选取最小的数据元素，并将它与原始数据元素集合中的第二个数据元素交换位置；如此重复，直到数据元素集合中只剩下一个数据元素为止。
例如对无序表{56，12，80，91，20}采用简单选择排序算法进行排序，具体过程为：
- 第一次遍历时，从下标为 1 的位置即 56 开始，找出关键字值最小的记录 12，同下标为 0 的关键字 56 交换位置：
- 第二次遍历时，从下标为 2 的位置即 56 开始，找出最小值 20，同下标为 2 的关键字 56 互换位置：
- 第三次遍历时，从下标为 3 的位置即 80 开始，找出最小值 56，同下标为 3 的关键字 80 互换位置：
- 第四次遍历时，从下标为 4 的位置即 91 开始，找出最小是 80，同下标为 4 的关键字 91 互换位置：
1.1、 直接选择排序的代码实现
void SelectSort() {
int arr[] = {56, 12, 80, 91, 20};
int len = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < len; ++i) {
int small = I;
for (int j = i + 1; j < len; ++j) {
if (arr[j] < arr[small])
small = j;//记住最小元素的下标
}
if (small != i) {//当前最小元素的下标不等于i时，交换两者的值
int temp = arr[i];
arr[i] = arr[small];
arr[small] = temp;
}
}
}
1.2、直接选择排序的效率分析
在直接选择排序中，第1次排序要进行n-1(n表示数据元素的个数)次比较，第二次排序要进行n-2次比较，如此类推第n-1次排序需要比较1次，所以比较的从此次数为：
因此直接选择排序算法的时间复杂度为。直接选择排序算法的空间复杂度为
。
2、堆排序
在直接选择排序中，待排序的数据元素集合构成一个线性结构，要从有n个数据元素的线性结构中选出一个最小的数据元素比较n-1次。如果能把待排序的数据元素集合构成一个完全二叉树结构，则每次选择出一个最小或最大的数据元素只需要比较完全二叉树的深度值次，即次，则排序算法的时间复杂度为
。这就是堆排序的基本思想。
2.1 堆的定义
堆分为最大堆(也称大顶堆或大根堆)和最小堆(也称小顶堆或小根堆)两种。
最大堆是指在数组a中存放n个数据元素，数组下标从0开始，如果当数组下标2i+1<n时有a[i]a[2i+1]，当数组下标2i+2<n时有a[i]
a[2i+2]，则这样的数据结构称为最大堆。如果把有n个数据元素的数组a中的元素看做一个完全二叉树的n和结点，则a[0]对应这完全二叉树的树根，a[1]对应着树根的左孩子结点，a[2]对应着树根的右孩子结点，a[3]对应着a[1]的左孩子结点，a[4]对应着a[1]的右孩子结点，如此等等。在此基础上，只需要再调整所有非叶结点的数组元素，使之满足条件：a[i]
a[2i+1]和a[i]
a[2i+2]，这这样的完全二叉树就是一个最大堆。
如下图所示是同一个数据序列的完全二叉树和最大堆的表示图例。
最小堆是指在数组a中存放的n和数据元素，数组的下标从0开始，如果数组小标2i+1<n时有a[i]a[2i+1]，当数组下标2i+2<n时有a[i]
a[2i+2]，这样的数据结构称为最小堆。
根据前面对于堆的定义可以推知堆有如下两个性质。
- 最大堆的根结点是堆中值最大的数据元素，最小堆的根结点是堆中最小的数据元素，
- 对于最大堆，从根结点到每个叶结点的路径上，数据元素组成的序列都是递减有序的；对于最小堆，从根结点到每个叶结点的路径上，数据元素组成的序列都是递增有序的。
2.2 创建堆
要进行堆排序，首先要创建堆。按非递减序列排序时，要创建最大堆。设数组a中存放了n个数据元素，若把数组a中这n个数据元素看做是一个完全二叉树的n个结点，则这棵有n个结点的完全二叉树采用了顺序存储结构。但是完全二叉树还不一定满足最大堆的定义。要让一棵完全二叉树满足最大堆的定义，需要从完全二叉树的叶结点端开始逐个结点进行调整，使它们满足最大堆的定义。
在一棵顺序存储结构存储的完全二叉树中，所有叶结点都满足最大堆的定义。对于第1个非叶结点ai，由于其左孩子结点a[2i+1]和右孩子结点a[2i+2]都已经是最大堆，所以只需要首先找出a[2i+1]结点和a[2i+2]结点的较大者，然后比较这个较大者结点和a[i]结点。如果a[i]结点大于或等于这个较大的结点，则以a[i]结点为根结点的完全二叉树已经满足最大堆的定义；否则对换a[i]结点和这个较大的结点，对换后，以a[i]结点为根结点的完全二叉树满足最大堆的定义。按照这样的方法，再调整第2棵非叶结点a[i-1]，第3棵非叶结点a[i-2]，直到最后调整根结点a[0]。当根结点调整完成后，这课二叉树就是一个最大堆。
对于一个数组序列{10,50,32,5,76,9,40,88}对应的完全二叉树如下所示。
-
首先调整第1个非叶结点(即下标为i=(n-1)/2=3的数组元素)，交换88和5的位置。
-
调整第2个非叶结点(即下标为i=2的数组元素)，交换40和32的位置。
-
调整第3个非叶结点(即下标为i=1的数组元素)，交换88和50的位置。
-
跳帧下标为0的数据元素即根结点。在调整根结点时，将引起数据元素88和数据元素76的上移，数据元素10最终下移存放在数据元素76的位置。
当完全二叉树中某一个非叶结点ai的左孩子结点a[2i+1]和右孩子结点a[2i+2]都已经是最大堆后，调整非也结点a[i]使之满足最大堆的函数代码实现如下：
//调整非叶结点a[i]使之满足最大堆
void CreateHeap(int a[],int len, int i) {
int h = i;//要创建堆的二叉树根结点下标
int j = 2 * h + 1;//根结点的左孩子结点下标
int temp = a[h];
int flag = 0;
while (j < len && flag != 1) {
//寻找左右孩子结点中的较大者，j为其下标
if (j < len - 1 && a[j] < a[j + 1]) {
j++;
}
//左右孩子结点的较大者和a[h]结点比较
if (temp > a[j]) {
flag = 1;
} else {
a[h] = a[j];
h = j;
j = 2 * h + 1;
}
a[h] = temp;
}
};
//初始化创建最大堆：从第一个非叶结点a[i](i=(len-2)/2)开始到根结点a[0]位置循环调用CreateHeap函数。
void InitCreateHeap(int a[],int len){
for (int k = (len-2)/2; k > 0; k--) {
CreateHeap(a,len,k);
}
};
2.3 堆排序的实现
堆排序的过程：首先把有n个元素的数组a初始化创建为最大堆，然后循环执行如下过程直到数组为空为止。① 把堆顶a[0]元素（为最大元素）和当前最大堆的最后一个元素交换；② 最大堆元素个数减1；③由于第①步后根结点不再满足最大堆的定义，所以调整根结点使之满足最大堆的定义。
堆排序算法代码如下：
void HeapSort(){
int arr[] = {56, 12, 80, 91, 20};
int len = sizeof(arr) / sizeof(arr[0]);
InitCreateHeap(arr,len);
for (int i = len-1; i >0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
CreateHeap(arr,i,0);
}
for (int k = 0; k < len; ++k) {
printf("%d ", arr[k]);
}
}
如下图所示是数组序列{10,50,32,5,76,9,40,88}的堆排序的排序过程图。
- 堆排序算法是基于完全二叉树的排序。把一个完全二叉树调整为堆，以及每次堆顶元素交换后进行调整的时间复杂度为
,所以堆排序算法的时间复杂度为
- 堆排序算法的空间复杂度为
。
- 堆排序算法是一种不稳定的排序方法。
网友评论