【排序算法】快速排序

前言：

    本章节将详细讲解排序算法中的快速排序，这里写的是C语言版本   

    快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列在相应位置上为止。

一、递归版本

1.1 hoare版本

算法思路 ：

    1.创建左右指针，确定基准值

    2.从右向左找出⽐基准值⼩的数据，从左向右找出⽐基准值⼤的数据，左右指针数据交换，进⼊下次循环

 

void swap(int* x, int* y)
{
	int tmp = *x;
	*x = *y;
	*y = tmp;
}


void QuickSort1(int* a,int left,int right)
{
	//若只有一个元素，或者没有元素，直接返回
	if (left >= right)
		return;

	int keyi = left;

	int begin = left;
	int end = right;
	while (begin < end)
	{
		while (begin < end && a[end] >= a[keyi])
		{
			end--;
		}

		while (begin < end && a[begin] <= a[keyi])
		{
			begin++;
		}

		swap(&a[begin], &a[end]);
	}

	swap(&a[begin], &a[keyi]);
	keyi = begin;
    
	//[left , keyi-1] [keyi+1 , right]
	//递归子区间
	QuickSort1(a, left, keyi - 1);
	QuickSort1(a, keyi+1, right);


}

问题1：为什么left 和 right指定的数据和key值相等时不能交换？

 

问题2：为什么跳出循环后right位置的值⼀定不⼤于key？

    我先说规律：左边作为基准值，右边先走，相遇位置一定比key的值小，反之也成立！

 

    具体的图我就不画了，你们按这个去推导，无非就这两种情况

    

    OK，第一个版本的递归就写完了，其实还能优化，但是我想先把3个版本都写完在写快排的优化吧！

1.2 挖坑法

算法思路：

    创建左右指针。⾸先从右向左找出⽐基准⼩的数据，找到后⽴即放⼊左边坑中，当前位置变为新的"坑"，然后从左向右找出⽐基准⼤的数据，找到后⽴即放⼊右边坑中，当前位置变为新的"坑"，结束循环后将最开始存储的分界值放⼊当前的"坑"中，返回当前"坑"下标（即分界值下标）

 

void QuickSort2(int* a, int left, int right )
{
	if (left >= right)
		return;

	int hole = left;
	int key = a[left];


	int begin = left;
	int end = right;

	while (begin < end)
	{
		//右边找小
		while (begin < end && a[end] >= key)
			end--;

		a[hole] = a[end];
		hole = end;

		//左边找大
		while (begin < end && a[begin] <=key)
			begin++;
		a[hole] = a[begin];
		hole = begin;


	}

	a[hole] =key;
	 
	//[left,hole-1] [hole+1, right]
	QuickSort2(a,left,hole-1);
	QuickSort2(a, hole+1,right);


}

1.3 lomuto前后指针版本

    创建前后指针，从左往右找⽐基准值⼩的进⾏交换，使得⼩的都排在基准值的左边。

 

void QuickSort3(int*a,int left ,int right)
{
	if (left >= right)
		return;

	int cur = left + 1;
	int prev = left;

	int keyi = left;

	while (cur <= right)
	{
		if (a[cur] < a[keyi])
		{
			++prev;
			swap(&a[cur], &a[prev]);
			++cur;
		}

		if (a[cur] >= a[keyi])
		{
			++cur;
		}
	}

	swap(&a[keyi], &a[prev]);

	keyi = prev;

	QuickSort3(a, left, keyi - 1);
	QuickSort3(a, keyi + 1, right);
}

 二、快排优化

2.1 时间复杂度的计算

    2.1.1 理想状态

    理想状态中的快排是个满二叉树,树的高度是log以2为底的N（这是二叉树的结论，我就直接用来用了），然后第一行的个数是n，第二行是n-1,第n行时n-key的个数，但是由于树的高度是log以2为底的N,所以最后一行是N-（首项为1，公比为2 ，项数为log以2为底N的对数的等比数列的和），由于log这个为低阶项，所以近似认为每行为N个元素，所以理想状态的时间复杂度为N*logN

2.1.2 有序状态

    这种情况下是等差数列，时间复杂度是N^2

2.1.3 大量重复数据

基准值选取与划分问题

    快速排序通过选定基准值，将数组划分为两部分。理想状况下，每次划分能让两部分规模大致相等，递归树近似满二叉树，高度为O(logn) ，时间复杂度为O(nlogn) 。但大量重复数据时，基准值若恰好是重复值，或重复数据分布不均，易使划分极度不平衡 。比如大部分元素都等于基准值，都被划分到同一侧，导致一侧子数组规模很大，另一侧很小，递归树退化为链表状，递归深度从O(logn) 变为O(n) 。

冗余操作

    传统快速排序对于重复元素，依旧会不断比较和交换 。例如，已有很多相等元素，还反复判断它们与基准值的大小关系并交换位置，这些操作对排序结果无实质帮助，却耗费大量时间，使得操作次数大幅增加。当数据规模为n 时，随着上述无意义操作增多，整体操作次数接近N^2 量级，时间复杂度近似为O(n2) 。

    总结：

            两边划分的越均匀，效率越优！！！

   2.2 优化

    2.2.1 随机选key 

	//随机选key
	int randi = left + (rand() % (right - left));

    //%(right-left)让随机数始终在这正确区间内，加上left是因为每个区间的开始是left
	swap(&a[left], &a[randi]);

	int keyi = left;

    2.2.2 三数取中

int GetMidNumi(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[left] < a[mid])
	{
		if (a[mid] < a[right])
		{
			return mid;
		}
		else if (a[left] > a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
	else // a[left] > a[mid]
	{
		if (a[mid] > a[right])
		{
			return mid;
		}
		else if (a[left] < a[right])
		{
			return left;
		}
		else
		{
			return right;
		}
	}
}

    以上两种优化都是为了解决有序的情况！！！

2.2.3 三路划分

    专门为了解决大量重复元素的算法:

    (先不写，后续会进行补充)

三、非递归版本

//非递归辅助接口
int PartSort(int* a ,int left,int right)
{
	int cur = left + 1;
	int prev = left;

	//三数取中
	int mid = GetMidNumi(a, left, right);
	swap(&a[left], &a[mid]);

	//随机选key
	//int randi = left + (rand() % (right - left));//%(right-left)让随机数始终在这正确区间内，加上left是因为每个区间的开始是left
	//swap(&a[left], &a[randi]);

	int keyi = left;
	while (cur <= right)
	{
		if (a[cur] < a[keyi])
		{
			++prev;
			swap(&a[cur], &a[prev]);
			++cur;
		}

		if (a[cur] >= a[keyi])
		{
			++cur;
		}
	}

	swap(&a[keyi], &a[prev]);

	keyi = prev;

	return keyi;

}

//快排非递归
void QuickSortNonR(int* a, int left, int right)
{
	stack st;
	STInit(&st);//栈的初始化
	STPush(&st, right);//入栈
	STPush(&st, left);

	while (!STEmpty(&st))
	{
		int begin = STTop(&st);取栈顶元素
		STPop(&st);
		int end = STTop(&st);
		STPop(&st);

		int keyi = PartSort(a, begin, end);
		// [begin,keyi-1] keyi [keyi+1, end]
		if (keyi + 1 < end)
		{
			STPush(&st, end);
			STPush(&st, keyi + 1);
		}

		if (begin < keyi - 1)
		{
			STPush(&st, keyi - 1);
			STPush(&st, begin);
		}
	}

	STDestroy(&st);//栈的销毁
}

    用栈进行辅助，上面我是直接用写好的栈的接口的，你们可以自己写个栈，基本思路就是：

3.1  划分操作

    与递归版快排一样，先实现数组的划分函数。通过选定一个基准元素（可以用三数取中、随机选取等策略优化），将数组分为两部分，使得左边部分元素小于等于基准，右边部分元素大于等于基准，并返回基准元素的最终位置。

    

3.2  利用栈模拟递归

    初始化栈：创建一个栈结构（可以是顺序栈或链式栈），用于存储待排序子数组的左右边界。

    入栈操作：将原始待排序数组的左右边界下标压入栈中，代表整个数组作为第一个待处理的子问题。

    循环处理：当栈不为空时，不断从栈中弹出左右边界，获取当前要处理的子数组范围。对该子数组进行划分操作，得到基准元素的位置。然后将基准元素左右两侧非空的子数组边界（如果存在）压入栈中。这一步相当于递归版中对基准元素左右子数组分别进行递归调用，只不过这里用栈来管理待处理的子数组，而非递归调用。

    结束条件：当栈为空时，意味着所有子数组都已处理完毕，排序完成。