排序算法（三）——选择排序【C/C++】_选择排序c++

---

前言

这里保存个人对常见选择排序算法的理解和实现思路过程。
供大家学习和参考。

---

一、几点注意

对于耗时时间，随机数选取，单调性的问题详见排序算法（一）。

二、选择类排序

2.1 选择类排序的分类

常见的选择类排序分为简单选择排序和堆排序等等，这里着重实现这两种插入排序。

2.2 简单选择排序

2.2.1 简单选择排序的思路

第一趟简单选择排序时，从第一个记录开始，通过n-1次关键字比较，从n个记录中选择出关键字最小的记录，并和第一个记录进行比较。
依次进行第二趟通过n-2次比较，从n-1个中选出最小的。
依次类推。
经过n-1趟简单选择排序，把n-1个记录排到位，剩下的一个自然也就排好了。

2.2.2 具体代码

void SelectSort(int* arr, int n) {
	int i, j;
	int min;
	for (i = 0; i <= n - 1; i++) {
		min = i;
		for (j = i + 1; j <= n - 1; j++) {
			if (arr[j] < arr[min]) {
				min = j;
			}
		}
		Swap(&arr[min], &arr[i]);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

2.2.3 测试代码

2.2.4 稳定性分析

举个例子，数组 6、7、6、2、8，在对其进行第一遍循环的时候，会将第一个位置的6与后面的2进行交换。此时，就已经将两个6的相对前后位置改变了。因此选择排序不是稳定性排序算法。

2.3 堆排序

2.3.1 堆排序的思路

把待排序的数字看成一颗完全二叉树的顺序表示，每个结点表示一个记录，第一个记录作为二叉树的根，对剩下的记录依次逐层从左到右顺序排序，（i从0开始）任意节点r[i]的左孩子是r[2r+1]，右孩子是r[2i+2]，双亲是r[(i+1)/2-1]。对这颗完全二叉树进行调整。
大根堆： r[i]>r[2i+1]且r[i]>r[2i+2]，也就是父节点大于孩子节点的完全二叉树称为大根堆。
每次建立建立大根堆后将堆顶元素与未排的最后一个孩子进行交换再进行调整，因此，如果要输出一个递增序列，那么就应该建立一个大根堆。

2.3.2 具体代码

void HeapAdject(int* arr, int root, int capacity) {
	int max = root;
	int lchild = root * 2 + 1;
	int rchild = root * 2 + 2;
	if (lchild<capacity && arr[lchild]>arr[max]) {
		max = lchild;
	}
	if (rchild<capacity && arr[rchild]>arr[max]) {
		max = rchild;
	}
	if (max != root) {
		Swap(&arr[max], &arr[root]);
		HeapAdject(arr, max, capacity);
	}
}
void HeapSort(int* arr, int n) {
	for (int parent = ((n-1)+1) / 2 - 1; parent >= 0; parent--) {
		HeapAdject(arr, parent, n);
	}
	for (int i = n - 1; i >= 0; i--) {
		Swap(&arr[i], &arr[0]);
		HeapAdject(arr, 0, i);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

2.3.3 具体思路实现讲解

首先说一下void HeapSort(int* arr, int n)，首先建立堆是从后往前调整的！
比如一个数组长度为3，内容为{3,6,8}，对于最后一个元素来说，即arr[2]来说，其父节点是3，也就是arr[0]—>（3/2-1=0）。
对于一个数组长度为4，内容为{3,6,8,9}，对于最后一个元素来说，即arr[3]来说，其父节点是6，也就是arr[1]—>(4/2-1=0）。
对于有n个元素的数组来说，最后一个元素arr[n-1]，他的父节点是arr[((n-1)+1)/2-1]。（这个也适用于任意节点）。
即对于任意i>0的元素来说元素arr[i]，其父节点为arr[(i+1)/2-1]

for (int parent = ((n-1)+1) / 2 - 1; parent >= 0; parent--) {
	HeapAdject(arr, parent, n);
}
1
2
3

对所有的父节点为根节点的子树从下往上依次调整。

for (int i = n - 1; i >= 0; i--) {
	Swap(&arr[i], &arr[0]);
	HeapAdject(arr, 0, i);
}
1
2
3
4

调整完毕后，将待排子树的最后一个节点和顶元素交换，即输出。
但是当交换完后，这个大根堆就不是个大根堆了，因此还要对剩下的元素进行重新调整。

接下来就是重头戏void HeapAdject(int* arr, int root, int capacity)
对于以root为父节点的子树来说，左子树就是root2+1，右子树就是root2+2，我们要调整这三个节点成为一个大根堆，就要找这三个人里谁最大，要是根节点最大，那这三个节点就是大根堆，如果根节点不是这三个里最大的，那么我就得找一哈这三个人里面谁最大。

int max = root;
int lchild = root * 2 + 1;
int rchild = root * 2 + 2;
if (lchild<capacity && arr[lchild]>arr[max]) {
	max = lchild;
}
if (rchild<capacity && arr[rchild]>arr[max]) {
	max = rchild;
}
1
2
3
4
5
6
7
8
9

那为什么要求lchild和rchild要小于capacity呢?那当然是害怕这俩节点不存在。
找肯定是要找存在着的孩子里谁最大，谁最大谁就和父节点交换，交换完成后，以刚刚交换的孩子为父节点的子树满足大根堆了。但是有可能以刚刚交换出去的孩子为节点的子树不满足大根堆了，因为现在子树的根节点变成了比较换出去的孩子节点小的父节点了，所以应该对换过来的节点的子树再递归调整。
害怕听不懂我在说啥，我花了个图来解释一下

首先先调整对是从前往后的，{80,60,75}符合大根堆，往上一层{60,45,55}符合大根堆，下一组{70,80,50,60,75}这里不符合大根堆，找70的孩子{80,50}里的大的80，记为max，然后70和80换，现在的arr[root]=80，而arr[max]=70，以max为父节点的子树{70,60,75}不符合大根堆，所以要接着递归进行对max为根的子树进行调整。

if (max != root) {
	Swap(&arr[max], &arr[root]);
	HeapAdject(arr, max, capacity);
}
1
2
3
4

想必大家已经听懂了，这下我们就测试一下。

2.3.4 测试代码

先测试10个元素。

想必是没有问题滴。

2.3.5稳定性分析

随便举个例子{8,(8),6}，6和第一个8换位置，变成{6,(8),8}，两个8的位置已经发生变换了。第二个8排在一个8前面了。所以堆排序是不稳定的。

2.4 两种选择排序算法比较

简单选择排序

时间复杂度：平均情况下为O(N²)。
      最好情况下为O(N²)
      最坏情况下为O(N²)。
空间复杂度：因为每回只移动一个所以空间复杂度为O(1)。
稳定性：不稳定。

堆排序

时间复杂度：平均情况下为O(Nlog₂^N)。
      最好情况下为O(Nlog₂^N)。
      最坏情况下O(Nlog₂^N)。
空间复杂度：O(1)。每回只交换第一个元素和待排的最后一个元素。
稳定性：不稳定。

三、和较快算法比较

对于100000以内的随机数的100000个元素的数组进行比较。

对于1000000以内的随机数的1000000个元素的数组进行比较。

可见对于不同算法的选取，效率差距还是蛮大的。

---

总结

对于选择类排序的总结就到这里，有问题欢迎大家指正。