选择排序

 · 2022-8-20 · 次阅读

根据王道书上的代码，结合自己的理解，编写的简单选择排序和堆排序（基于大根堆）的示例代码。

简单选择排序

简单选择排序的思想是，每次从未处理的数据里面选择一个最小的（或者最大的），将这个最小值（或者最大值）放在已排序数组的末尾，从而实现排序。

image.png

简单选择排序的时间复杂度不受初始排列的影响，始终为O(n^2)

简单选择排序的空间复杂度为常数级O(1)

简单选择排序是一种不稳定的排序算法，可能会改变相同元素的先后顺序。

示例代码：

// 简单选择排序
void SelectSort(int * data, int len)
{
	int i = 0, j = 0;
	for (i=0; i<len; i++) {
		int min = i;						// 最小值下标初始化为i
		for (j=i+1; j<len; j++) {			// 从i+1开始
			if (data[j] < data[min]) {
				min = j;					// 确定后面最小的元素的下标
			}
		}
		if (min != i) {
			swap(data[min], data[i]);		// 把后面最小的元素与第一位的元素交换
		}
	}
	return;
}

堆排序

堆排序通过首先建立一个堆，每次从堆里面选择一个最大（或者最小）的元素，从而实现排序。

大根堆：二叉树的根节点大于所有子孙节点的二叉树。

小根堆：二叉树的根节点小于所有子孙节点的二叉树。

实现堆排序，首先要对数组进行原始处理，使得数组满足大根堆顺序存储的要求。

具体做法是，从数组的一半开始，倒着往前处理（因为数组后一半都是叶子节点，无需调整，而从后往前保证了每上一层的调整都基于下面已经满足大根堆要求的前提）

// 将一个数组调整为大根堆
void CreateHeap(int * data, int len)
{
	int i = 0;
	for (i=len/2; i>0; i--) {
		AdjustHeap(data, i, len);					// 明确为什么从后往前，因为按照二叉树的逻辑，应该是从下往上的
													// 保证上面每一个节点的处理都是在下面节点合法的情况下
	}
	return;
}

这里面的核心操作是AdjustHeap函数。这个函数传入一个指定的节点，然后把这个节点下沉到属于它的位置：

// 调整一个节点使其大于下面的所有节点，这个操作是堆排序的核心
void AdjustHeap(int * data, int k, int len)
{
	int i = 0;
	data[0] = data[k];								// 0号位置保存待安放的根节点
	for (i=k*2; i<=len; i*=2) {
		if (i != len && data[i] < data[i+1]) {		// 判断根的两个孩子谁比较大，并将i指向更大的孩子
			i++;
		}
		if (data[0] >= data[i]) {					// 如果根的值大于最大的孩子，就不需要调整了
			break;
		}
		data[k] = data[i];							// 将孩子的值上浮，但是没法确定根就放在这个孩子的位置
													// 因为这个孩子的孩子还可能比原来的根大
		k = i;										// 将根节点转化为这个更大的孩子，在这个孩子的下面继续寻找
	}
	data[k] = data[0];
	return;
}

一旦将一个树调整成大根堆，之后只需要懂哪个元素调整哪个元素即可，不足要再全部调整。

void HeapSort(int * data, int len)
{
	int i = 0;
	CreateHeap(data, len);							// 初始化堆，时间复杂度O(n)
	for (i=len; i>1; i--) {							// 共进行n轮操作
		swap(data[1], data[i]);						// 交换堆根节点元素和最后一个节点的元素
		AdjustHeap(data, 1, i-1);					// 对剩余的部分进行堆调整，注意数组的长度是i-1，时间复杂度是O(log2n)
	}
	return;
}

上面代码的第六行需要特别注意。这个循环里面所做的事情有：

  1. 将当前的堆顶与最后一个元素交换
  2. 调整刚刚被换成堆顶的元素，使得堆顶仍然保持最大

这里需要注意循环内AdjustHeap函数的参数。

  1. 第二个参数，由于始终是对第一个元素进行调整，所以置1
  2. 第三个参数，只填未处理的元素的个数。在上一步交换之后，未处理的元素只剩下i-1个，所以这里填写i-1

image.png

这里的数组0号位不放元素，主要是基于数的顺序存储，从1号位开始存放元素，计算孩子节点更加方便。

赏