C++实现排序 - 02 归并排序、快速排序和堆排序

数据结构与算法专栏 —— C++实现

写在前面：
今天我们继续来整理平均时间复杂度为 O(nlogn) 的三个排序算法，即归并排序、堆排序和快速排序。

归并排序采用了分治法的思想，不断将两个有序的序列进行合并从而最终得到整个有序的序列，算法步骤如下：

1. 把当前长度为 n 的序列分为两个长度为 n / 2 的子序列，对子序列进行操作。
2. 同样对两个子序列进行划分，再分别对其子序列进行划分操作，直至子序列中只有一个元素为止就不再进行划分，而是进行回溯。
3. 通过回溯的子序列进行排序操作，我们额外创建一个数组出来，将回溯的两个子序列进行合并操作。
4. 一直往上回溯，这样每次得到的两个回溯的子序列都是有序的，可以方便我们进行合并操作，合并的序列也会是有序的。

直接上图：

我们先对序列进行划分操作：

然后对各个子序列进行回溯：

通过合并操作，得到最终的子序列。

#include 
using namespace std;

int n, q[100010], temp[100010];

void merge_sort(int q[], int l, int r) {
	//如果当前序列只有一个元素，则不用排序直接返回
	if (l >= r)
		return;

	//对序列进行划分，然后对其子序列进行递归操作
	int mid = l + r >> 1;
	merge_sort(q, l, mid), merge_sort(q, mid + 1, r);

	//合并操作
	int k = 0, i = l, j = mid + 1;
	while (i <= mid && j <= r) {
		//遍历两个子序列，将更小的元素取出放入临时数组temp
		if (q[i] <= q[j])
			temp[k++] = q[i++];
		else
			temp[k++] = q[j++];
	}

	//如果还有元素没有取出，将剩余元素放入临时数组temp
	while (i <= mid)
		temp[k++] = q[i++];
	while (j <= r)
		temp[k++] = q[j++];

	//将原数组进行更新，更新上面合并的区间
	for (int i = l, j = 0; i <= r; i++, j++)
		q[i] = temp[j];
}

int main() {
	
	scanf("%d", &n);
	for (int i = 0; i < n; i++) {
		scanf("%d", &q[i]);
	}
	merge_sort(q, 0, n - 1);
	for (int i = 0; i < n; i++) {
		printf("%d ", q[i]);
	}
}

快速排序也是利用了递归思想，算法步骤如下：

1. 选取第一个的数作为基准数。
2. 将小于基准数的元素换到前面，将大于基准数的元素换到后面。
3. 重复上述操作，直到区间只有一个数为止。

直接上图：

第一步：选取第一个数作为基准数。

第二步：从后往前找一个比基准数小的数放到前面。

第三步：从前往后找到一个比基准数大的树放到后面。

第四步：继续从后往前查找，发现 first 和 last 重合，本次遍历结束，并将基准数放到指针所指地方。

第五步：将该序列分成两半，左半部分是该序列左边界至 first -1 ，右半部分是 first +1 至右边界。

第六步：对左半部分即下标为 0 ~ 1 区间进行递归排序，由于已经是有序我们就直接跳过这里。

第七步：对右半部分即下标为 3 ~ 6 区间进行递归排序。

第八步：从后往前找到一个比基准数小的数放到前面。

第九步：从前往后找一个比基准数大的数放到后面，但是发现指针最终重合，故此次遍历结束，将基准数放到指针所指位置。

第十步：与上面相同，对该序列进行左右区间划分，再分别遍历。由于右半部分已经没有元素了，我们直接对左半部分即下标为 3 ~ 5 区间进行递归排序。

由于该序列已经有序，后续递归操作我们就不再展示了，直接来看代码。

#include 
using namespace std;

int q[1000010];

void quick_sort(int q[], int l, int r) {
	if (l >= r)
		return;
	int first = l, last = r, key = q[first];
	while (first < last) {
		//将比第一个小的移到前面
		while (first < last && q[last] >= key)
			last--;
		if (first < last)
			q[first++] = q[last];

		//将比第一个大的数移到后面
		while (first < last && q[first] <= key)
			first++;
		if (first < last)
			q[last--] = q[first];
	}
	q[first] = key;
	quick_sort(q, l, first - 1), quick_sort(q, first + 1, r);
}

int main() {
	
	int size = 0;
	scanf("%d", &size);
	for (int i = 0; i < size; i++) {
		scanf("%d", &q[i]);
	}
	quick_sort(q, 0, size - 1);
	for (int i = 0; i < size; i++) {
		printf("%d ", q[i]);
	}
	return 0;
}

在了解堆排序之前，我们先来看看什么是堆。

堆就是一个类似于完全二叉树的结构，同时它分为大顶堆和小顶堆，它们的性质分别是每个结点的值都大于（或小于）它的孩子结点。

下面就是一个大顶堆：

下面就是一个小顶堆：

那么我们如何利用堆的性质进行排序呢，算法步骤如下（这里讲解升序操作）：

1. 先将初始化的数组序列构建成大顶堆。
2. 将堆顶元素和最后一个元素进行交换，此时最后一个元素的位置就是该序列的最大值了。然后再对其前面的所有元素进行堆更新，即从堆顶元素往下进行堆操作，但是这里已经排好序的最后一个元素不参与对操作。
3. 重复上述步骤，每次都从堆顶取剩余元素的最大值放到堆即剩余元素的最后一个，然后从堆顶往下进行对操作，直至所有元素都已经操作完。

可能会有小伙伴比较有疑惑，我们该如何确定已经排好序和没有排好序的元素呢。这就需要用到完全二叉树的性质：

在下标从 0 开始存储元素的顺序存储的数组当中，结点的左孩子下标等于该结点下标乘以 2 加 1 ，结点的右孩子下标等于该结点下标乘以 2 加 2 。

这样我们可以通过数组下标进行操作，先对前 n 个元素构建大顶堆。然后交换堆顶和最后一个元素，确定数组中第 n 个元素的序列，再对前 n - 1 个元素进行堆操作。

直接上图：

先来看看如何构建出大顶堆，我们要从第一个非叶子结点开始往上构建。因为如果从第一个结点开始往下构建的话，可能无法将最大的元素放到堆顶。

假设我们初始的序列为 { 21 , 343 , 122 , 84 , 5 , 117 , 4 } ，从第一个非叶子结点开始往上构建。

第一步：第一个非叶子结点为 122 ，每次都去找到该结点与其孩子结点中的最大值并进行交换，发现自身印记是最大值了，故找到上一个非叶子结点。

第二步：非叶子结点 122 已经是其和其孩子结点中的最大值，故不用交换。

第三步：非叶子结点 21 与其孩子结点进行比较，发现其孩子结点 343 更大，故进行交换。

第四步：交换后的结点不是叶子结点，故继续向下找到最大值。

至此，大顶堆已经构建完成，现在进行排序操作。

第一步：交换堆顶和最后一个元素。

第二步：对堆顶元素向下进行对操作，注意已经排好序的 343 不再参与到对操作之中。

第三步：交换堆顶和最后一个元素，并对堆顶元素向下进行堆操作。

第四步：交换堆顶和最后一个元素，并对堆顶元素向下进行堆操作。

第五步：交换堆顶和最后一个元素，并对堆顶元素向下进行堆操作。

第六步：交换堆顶和最后一个元素，并对堆顶元素向下进行堆操作。

第七步：交换堆顶和最后一个元素，并对堆顶元素向下进行堆操作。

第八步：交换堆顶和最后一个元素，并对堆顶元素向下进行堆操作。

至此，所有元素都排好序了，直接输出即可。

#include 
using namespace std;

//用递归方式来调整为大顶堆
void adjust(int a[], int len, int index) {
	int right = index * 2 + 1;	//index的右结点
	int left = index * 2 + 2;	//index的左结点

	//找到三个结点中最大的一个，使其在index位置上
	int maxIdx = index;
	if (right < len && a[right] > a[maxIdx])
		maxIdx = right;
	if (left < len && a[left] > a[maxIdx])
		maxIdx = left;

	if (maxIdx != index) {
		swap(a[maxIdx], a[index]);
		adjust(a, len, maxIdx);	//变换结点后如果还有子结点，则继续进行排序
	}
}

//堆排序
void heapSort(int a[], int size) {
	//从最后一个非叶子结点开始构建大顶推
	for (int i = size / 2 - 1; i >= 0; i--) {
		adjust(a, size, i);
	}

	for (int i = size - 1; i > 0; i--) {
		swap(a[i], a[0]);	//将大顶堆的根结点与最后一个结点交换，就得到了最大值
		adjust(a, i, 0);	//交换完后，继续对除交换到最后的元素之外的前面所有元素进行堆排序
	}
}

int main() {
	int a[10] = { 21, 343, 122, 84, 5, 117, 4, 35, 90, 666 };
	int size = 10;
	heapSort(a, size);
	for (int i = 0; i < size; i++) {
		cout << a[i] << " ";
	}
	return 0;
}

如果大家有什么问题的话，欢迎在下方评论区进行讨论哦~

【上一讲】C++实现排序 - 01 归并排序、快速排序和堆排序

【下一讲】C++实现排序 - 03 计数排序、桶排序和基数排序