【原】基本算法-快速排序

翟天保的图书馆 2022-07-06 发布于上海

展开全文

作者：翟天保Steven
版权声明：著作权归作者所有，商业转载请联系作者获得授权，非商业转载请注明出处

前言

本文介绍一种排序算法——快速排序，是常用的排序算法之一。以下是本篇文章正文内容，包括算法简介、算法特点、算法实现和C++示例。

一、快速排序简介

快速排序法又称分割交换排序法，是目前公认的较优排序法之一，采用了分而治之的思想。先从数据中找到一个参照值，将其放置在数据中间，把数据集分为两部分，比参照值小的在左边，大的在右边；再以同样的方式分别处理左右侧的数据，直到排序完毕。

快速排序法的实现思路有很多，本文介绍其中一种（我觉得最好理解且最方便实现的）——占坑法。

假设第一个数据是参照值，该值备份下来。
从后开始找比它小的数值a，并将其放置在第一个数据处，然后再从前开始找比它大的数值b，将其放置在a原先的位置，以此类推，以占坑的方法让数据集动态排序。
在此过程中，数据集一直有两个值是一样的。
直到前下标和后下标重合时，将备份的参考值替换当前下标的数值，这样就完成了第一轮的分区。
同操作分别处理左侧数据集合右侧数据集，可用递归进行。递归完成，排序完毕。

二、算法特点

1）最好情况和平均情况下，时间复杂度为O(nlog2n)；最坏情况下，每次挑中的参照值都是最值，这样时间复杂度为O(n2)。

2）不稳定，假设两个一样的值a=b，a在前b在后，a被选为基准，排完一遍后，a很大可能就跑到b的后面去了。

3）占坑法的空间复杂度是O(1)，别的实现方法可能会增加空间复杂度。

4）快速排序法是目前使用较多的排序算法，也是平均运行速度较快的算法。

三、代码实现

代码实现逻辑：

以最左侧数据为基准，并备份为b。
占坑法对比数据并替换。
当i==j时，将备份的基准值b赋值到data[i]，完成一次分区。
对左侧数据和右侧数据分别排序。
递归完成，排序结束。

// 快速排序
void QuickSort(vector<int> &data, int left, int right)
{
	// 若左标与右标重合，中断
	if (left >= right)
		return;

	// i为左标，j为右标，b为基准
	int i = left;
	int j = right;
	int b = data[i];
	// 占坑式替换
	while (i < j)
	{
		while (data[j] >= b && i < j)
			j--;
		data[i] = data[j];
		while (data[i] <= b && i < j)
			i++;
		data[j] = data[i];
	}
	data[i] = b;

	QuickSort(data, left, i - 1);
	QuickSort(data, i + 1, right);
}

四、C++示例

#include <iostream>
#include <iomanip>
#include <vector>
#include <string>

using namespace std;

// 展示当前顺序
void Show(vector<int> data)
{
	size_t size = data.size();
	for (size_t i = 0; i < size; ++i)
		cout << setw(4) << data[i];
	cout << endl;
}

// 快速排序
int Count = 1;
void QuickSort(vector<int> &data, int left, int right)
{
	// 若左标与右标重合，中断
	if (left >= right)
		return;

	// i为左标，j为右标，b为基准
	int i = left;
	int j = right;
	int b = data[i];
	// 占坑式替换
	while (i < j)
	{
		while (data[j] >= b && i < j)
			j--;
		data[i] = data[j];
		while (data[i] <= b && i < j)
			i++;
		data[j] = data[i];
	}
	data[i] = b;
	cout << "第" << Count << "次排序结果：\n";
	Show(data);
	Count++;
	QuickSort(data, left, i - 1);
	QuickSort(data, i + 1, right);
}

// 主函数
int main()
{
	vector<int> data = { 9,11,567,0,-2,4,2 };

	// 快速排序
	cout << "快速排序：\n原始数据：\n";
	Show(data);
	QuickSort(data, 0, data.size() - 1);
	cout << "排序后结果：\n";
	Show(data);

	system("pause");
	return 0;
}

效果图：