选择排序(包含堆排序)

发表于

思路

每一趟都从n-i+1（i=1,2,3….n-1）个记录中选择出最小的关键字，作为有序序列的第i个元素。

常用的选择排序

  • 简单选择排序
  • 堆排序

简单选择排序

思路 （参考：选择排序）

数组A，长度为：n，临时变量：i,初始化为1

  • 从A[i]~A[n]这n-i+1个元素中，找出最小的关键字，并且记录其下标
  • 如果该关键字不是A[i]~A[n]这个序列的第一个元素，则将该两个位置的元素替换
  • 将i从1~n-1，递增循环执行上述两个步骤

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
using namespace std;
typedef int Datatype;    //编译期多态的一种：转换

void print(Datatype * data, int i, int length) {
	int j = 0;
	cout << "第" << i + 1 << "趟排序：";
	for (j = 0; j < length; ++j) {
		cout << data[j] << " ";
	}
	cout << endl;
}
void EasySelectSort(Datatype * data, const int length) {
	int i = 0;
	int j = 0;
	Datatype min;
	int temp = 0;
	for (i = 0; i < length-1; ++i) {    //只需要确认前length-1个元素的顺序，则最后一个位置的元素的位置也就确定了
		temp = i;                       //记录temp
		for (j=i; j < length; ++j) {    //找出最小的那个关键字的位置。 
			if (data[j] < data[temp]) {
				temp = j;
			}
		}
		if (temp != i) {   //判断是否需要交换两个位置上的元素
			min = data[temp];
			data[temp] = data[i];
			data[i] = min;
		}
		print(data, i, length);
	}
}



void main() {
	int data[] = { 7,4,-2,19,13,6 };
	EasySelectSort(data, sizeof(data) / sizeof(int));
	system("pause");
}

结果：
image

时间复杂度分析

我们通过分析可以知道，我们程序无论是什么情况，都要比较：n*(n-1)/2次。所以程序的时间复杂度为：O(n^2)。

是否稳定

稳定的定义就是：两个相同的数，在排完序后前后的相对顺序没有改变。对于简单选择排序，它是不稳定的，我可以简单的举个例子：{7,7,2}，当我们进行简单选择排序后，第一个7会和2调换位置，从出现不稳定的情况

堆排序

简单的选择排序为了得出有序的序列，对于任意序列都要比较：n*(n-1)/2次。那么我们要优化这个算法的话，那么就要减少我们的比较的次数。所以从比较这里出发：我们为得出n个关键字中的最小的值，需要比较n-1次，而下一次要得出n-1个关键字中最小的值时，同样又要比较n-2次，如果我们可以利用之前的n-1次的比较结果，那么我们就可能在下一次寻找中，减少比较次数，从而就可以提高程序的效率了。堆就可以记录这些信息，所以我们就提出了另外一种优化的选择排序：堆排序

思路

用一个完全二叉树来表示堆，堆有两种：最大堆和最小堆。

  • 最大堆：所有结点都比它们的左右孩子大。调整过程出现两个孩子结点，都大于父结点，选择大的那个替换。
  • 最小堆：所有结点都比它们的左右孩子小。调整过程出现两个孩子结点，都小于父结点，选择小的那个替换。

堆排序的大体思路是（以最小堆为例）：

  • 首先建立初始堆
  • 输出根结点，用最后一个结点替换根结点，删除最后一个结点，并且对堆进行调整，使其还是满足最小堆的性质。
  • 重复，第二个过程，直到堆为空为止

实现过程

我们从思路分析，可以知道我们需要解决两个问题：

  • 建立初始堆
  • 输出后，对堆的调整

程序实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void HeapAdjust(Datatype * data, int length, int s) {
	//最小堆
	int j = 0;
	Datatype temp = data[s];
	j = 2 * s + 1;
	for (; j <= length; j = 2 * j + 1) {
		/*
		最大堆需要修改：下面两个if语句，
		*/
		//如果左子树小于右子树，则让右子树去和根结点比较
		if (j < length && data[j] > data[j + 1]) {
			++j;
		}
		//此时已经满足最小堆了条件了，可以停止寻找了
		if (temp <= data[j]) {
			break;
		}
		//交换根结点和孩子结点的值
		data[s] = data[j];
		s = j;
	}
	//最后，确定了我们那个关键需要存放的地方
	data[s] = temp;
}
void HeapSort(Datatype * data, int length) {
	for (int i = (length / 2)-1; i >= 0; --i) {
		HeapAdjust(data, length-1, i);
	}
	int n = length - 1;
	//这里我们只需要比较前length-1个数，最后一个数的值也就确定了
	while (n >= 1) {
		Datatype temp;
		temp = data[0];
		data[0] = data[n];
		data[n] = temp;
		cout << temp << " ";
		--n;
		HeapAdjust(data, n, 0);
	}
	cout << data[n];
	cout << endl;
}

在主函数中，调用上述的HeapSort函数，就可以进行堆排序了。

时间复杂度分析

这里的时间主要是花费在调用heapAdjust函数中，HeapAdjust函数最多做：⌈log2n⌉次调整，总共需要调用：(n/2）+(n-1)次HeapAdjust函数，所以该时间复杂度为：O（nlog2n）

是否稳定

堆排序是不稳定的排序算法，比如有无序的序列：{3,27,36,27}，所以在输出3后，最后的那个27替换到了根节点，从这里就可以看出该算法是不稳定的。

总结

堆排序的时间复杂也是为：O（nlog2n），而且是最多就是：O（nlog2n）。对于时间复杂同样是：O（nlog2n）的排序算法：快速排序和归并排序来说，它只是在最坏情况下是占优势的。具体可以参考：
堆和快排、归并的比较