快速排序

介绍

快速排序是分治思想的一种体现，通过递归不断将原数列划分为一大一小两部分， 从而实现对数列的排序。

算法时间复杂度为O(nlogn)。特点是数据越混乱，效率越高；数据越有序，效率越低。

值得注意的是快速排序是不稳定的，即相同大小的数据在排序前后的相对位置可能会发生变动。

代码实现

void quick_sort(int a[],int l,int r)//快速排序，从小到大
{
	if (l == r)
		return;//若数列中只有一个数，则必定有序，返回
	int x = a[(l + r) / 2], i = l - 1, j = r + 1;
    //取中项值为标准值x，采用do while，故i，j起始位置在l，r两端
	while(i<j)//当指针相遇且越过，则说明数列已遍历完
    {
		do i++; while (a[i] < x);
		do j--; while (a[j] > x);
        //i，j从两端分别向中间遍历，使i左边值小于x，j右边值大于x，遇到不满足则停止
		if (i < j) swap(a[i], a[j]);
        //当i，j分别移动到不满足项时，交换二者位置，则二者都满足，i，j继续向中间遍历
	}
    //指针相遇，遍历结束，此时j及其左侧值都小于x，j+1及其右侧值都大于x
	quick_sort(a, l, j);
	quick_sort(a, j + 1, r);
    //分别对左右两部分递归处理，知道整个数列都有序
}

思路解析

void quick_sort(int a[],int l,int r)//快速排序，从小到大
{
	if (l == r)
		return;
    //......
}

函数的传入值包括数组和左右端点下标。

显而易见，当l==r时，数列中只有1个数据，必定有序，所以我们直接返回。

int x = a[(l + r) / 2], i = l - 1, j = r + 1;

此时，我们需要将该数列分为一大一小两部分，保证右边的所有数都能大于左边。

所以，我们需要设定一个标准值，来判断某一个数应该放在左边还是右边。

这个标准值可以选择数组中的任何一个数据，可以取第一个值a[l]，也可以取中项a[(l+r)/2]，甚至可以随机。

但我们这里选择取中项值作为标准值，假如取首项为标准值，当所有数据大小都一样时，算法的时间复杂度会从O(nlogn)退化到O(n²)。

同时，我们设立两个指针i和j，分别置于数列两端，用于遍历下标，至于为什么要多偏移一位，我们下面解释。

while(i<j)//当指针相遇且越过，则说明数列已遍历完
    {
		do i++; while (a[i] < x);
		do j--; while (a[j] > x);
        //i，j从两端分别向中间遍历，使i左边值小于x，j右边值大于x，遇到不满足则停止
		if (i < j) swap(a[i], a[j]);
        //当i，j分别移动到不满足项时，交换二者位置，则二者都满足，i，j继续向中间遍历
	}

指针位于数列的两端，同时往中间移动，我们采用do{} while{};语句，每次先移动指针再进行判断，所以我们的起始位置应该置于l和r的外侧一位。

指针向中间移动后，比较当前位置的数据值和标准值x的大小。

以i指针举例，若a[i]<x，则无事发生，指针i继续遍历，将该数据留在i的左边，直到遇到一个不满足的数，停下。

指针j同理。

当两个指针都已停止后，说明a[i]处有一个大于x的值，a[j]处有一个小于x的值，此时只需要将二者调换位置即可有效地调整数列顺序，当然，需要先对i，j是否越过进行判断。

若两个指针相遇且越过，就说明数列已经遍历完了，每个下标都已经经过。

此时，我们就已经将数组划分为左右一大一小两个部分。

quick_sort(a, l, j);
quick_sort(a, j + 1, r);

最后，我们将划分出的两个数组递归处理，再次划分为一大一小，直到划分到只有1个数据，然后开始回溯。

最终，就会返回一个有序数列。

值得注意的是，递归的起始位置也可以用i表示，但需要改为

quick_sort(a, l, i - 1);
quick_sort(a, i, r);

并且x的取值也需要从x = a[(l + r) / 2]改为x = a[(l + r) / 2 + 1]，即额外加1。

否则会出现边界问题，导致无限递归。

以上便是对快速排序的介绍，本文由凉茶coltea撰写，思路来自AcWing大佬yxc的课