数据结构初阶：选择排序堆排序

vlambda
2022-02-09

数据结构初阶：选择排序堆排序

@八大排序

3 选择排序

3.1 直接选择排序
3.2 堆排序

3 选择排序

3.1 直接选择排序

选择排序是所有排序中最简单的排序之一。

基本思想

遍历一遍数组，选出规定范围内的最大值和最小值，
将最大值和最后一个位置的元素交换，将最小值和最前一个位置交换。
将最前最后的位置“排除”出数组，进一步缩小范围，

再重复上述步骤直到选完为止，当然遍历数组选最值时虽可只选一个但为降低时间消耗最好选两个。

代码实现

简单版：一次找一个极值。

void SelectSort(int* a, int n) {
	assert(a);
	while (n) {
		int maxi = 0;
		for (int i = 0; i < n; i++) {
			if (a[i] > a[maxi]) {
				maxi = i;
			}
		}
		Swap(&a[maxi], &a[n - 1]);
		n--;
	}
}

提升版：一次找两个极值。

//1. 
void SelectSort(int* a, int n) {
	assert(a);
	int begin = 0, end = n - 1;
	while (begin < end) {
		int mini = begin, maxi = begin;
		//找最值
		for (int i = begin; i <= end; i++) {
			if (a[i] < a[mini]) {
				mini = i;
			}
			if (a[i] > a[maxi]) {
				maxi = i;
			}
		}	
		//交换
		Swap(&a[mini], &a[begin]);
		//修正
		if (maxi == begin) {
			maxi = mini;
		}
		Swap(&a[maxi], &a[end]);
		++begin;
		--end;
	}
}
//2. 
void SelectSort2(int* a, int n) {
	assert(a);
	int sz = n;
	while (sz > n / 2) {
		int maxi = mini = n - sz;
		for (int i = n - sz; i < sz; i++) {
			if (a[i] < a[mini]) 
				mini = i;
			if (a[i] > a[maxi]) 
				maxi = i;
		}
		Swap(&a[maxi], &a[sz - 1]);
		if (mini == sz - 1) {
			mini = maxi;
		Swap(&a[mini], &a[n - sz]);
		sz--;
	}
}

第一种方案，定义了头尾两个指针来标识排序的范围，第二种是定义变量sz标识范围大小，但要注意控制排序趟数正好是元素个数的一半，相比来说第一种更加直观。

同时找两个最值的方法在交换的时候会出现一个问题：

既然最小值与首元素交换，最大值与尾元素交换，可能在最大值与尾元素交换的时候，尾元素正好是最小值，或者最小值与首元素交换时，首元素正好是最大值。

本来maxi,mini已经标识好了最值的下标，上述情况下交换会将元素移走，但maxi,mini不会变，这就导致了下一次交换的并不是最值。要想解决这个问题，就必须在交换后检查并修正这两个下标，及时地更改下标的位置使其依旧和元素保持对应。

两次交换中只需要在第一次交换后检查修正就行，第二次交换出现问题但并不影响结果因为下一趟排序会重新遍历找最值。

复杂度分析

每次找一个最值和每次找两个的方式的复杂度具体算式分别为和，但时间复杂度都是。所以每次找一个和两个的优化仅仅是量的提升，并没有质的提升。

上述是最坏情况，而最好情况仍然是一样的遍历步骤，所以最好情况的时间复杂度仍是。无论什么情况直接选排的复杂度都是，所以直接选择排序的效果比较差。

3.2 堆排序

基本思想

堆排序要先把数组建成堆再进行堆排序，建堆用向下调整算法，时间复杂度为。建堆最好选择排升序建大堆，排降序建小堆。

数组从逻辑结构上看是完全二叉树，但并不一定是堆。所以我们需要先将数组建成堆，然后才能再进行堆排序。若将数组建成小堆，取堆顶就是最小的数，选出次小的数就要删除首元素从第二个元素位置开始破坏堆的结构重新建堆。

向下调整算法要求结点的左右子树都是堆，故从下往上走，从第一个非叶子结点开始向下调整建堆。
建堆完成后，数组首尾元素互换选出最大的数，再向下调整选出次大的数，循环直至调整完数组。

将数组首尾元素互换，堆顶最大数就被放在了数组末尾，尾指针减1，再向下调整把次大的数调整到堆顶，再首尾互换，次大的数就放在了后面。依次类推一直循环，直到尾指针指向数组首元素，就排完了整个数组。

代码实现

void AdjustDown(int* a, int n, int parent) {
	assert(a);
	int child = parent * 2 + 1;
	while (child < n) {
        if (child + 1 < n && a[child + 1] > a[child]) {
			child++;
		}
		if (a[child] > a[parent]) {
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		else {
			break;
		}
	}
}
void HeapSort(int* a, int n) {
	assert(a);
	//建堆
	for (int i = (n - 1 - 1) / 2; i >= 0; i--) {
		AdjustDown(a, n, i);
	}
	//堆排序
	int end = n - 1;
	while (end) {
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

复杂度分析

直接选择排序的复杂度太高，虽然堆排序也是选择排序，但堆排序利用了堆的性质大幅缩减了比较的次数，达到了，建堆用向下调整算法，时间复杂度为。二者综合起来就是，可见堆排和希尔排序属于同一级别的排序。

vlambda博客
学习文章列表