排序算法之不同版本的快速排序-Toy模板网

这篇具有很好参考价值的文章主要介绍了排序算法之不同版本的快速排序。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

快速排序思想：选取一个关键字，通过一趟排序将这些待排序的数据分隔为两个部分，一部分数据全小于关键字，一部分数据全大于关键字，通过一趟排序就可以将一个关键字排好序，然后再可以对这两部分执行相同类似的操作，每次走一趟选出一个关键字，这个关键字的左边小于它，右边大于它。每一趟排序都有两个区间，也可以看作是二叉树，之后再对剩下的数据进行排序它的区间范围不在极端情况下几乎都会缩小一半，直到待排序区间为1时就不用再排序了，此时都排好了，返回，总的可以为logⁿ在最后范围到一时不用再排序，而此时在近乎好的情况下时间复杂度为o(nlogⁿ),且都是类似的子问题，这样它也可以递归解决。

一、关键字如何选择？

一般选取第一个或者最后一个或者中间那个
定义区间第一个下标为left,区间最后一个下标为right,关键字下标为keyi,数组为a[ ],
当选取a[left]为关键字时,令keyi = left，a[keyi] = a[left],这时就要先从区间最右边开始与key比较，当a[right] >= a[keyi]，那么right–，此时right往前走再与关键字比较，当a[right] < a[keyi]时，right停下，此时从左边开始找比关键字大的，当a[left]<=a[keyi]，left++,当前left对应值小于key时，left++,当a[left] > a[keyi]，left停下，此时将a[left]和a[right]交换，之后再从右边走找小，从左边走找大，直到left遇到right**,但是它们相遇有两种情况，从右边开始找不到a[right] < key,那么a[left]就是key对应的值，从右边第一个就是小于key,从左边开始走之后一直到right之间找不到a[left] .>key，此时left = right,** ,此时它们相遇位置对应的值要小于key,然后再将a[left]与啊[keyi]交换(left下标对应的值一定会小于或者等于key)，至此一趟排序完成

选右边a[right]作为关键字,keyi = right,a[keyi]
=a[right],这时先从左边走与其关键字进行比较，a[left] <= a[keyi] ;left++,直到走到a[left] > a[keyi] left不动，此时从右边开始走，当a[right] >= a[keyi]时，right–,直到走到a[right] <
a[keyi]时，right停止，此时将a[left]
a[right]交换，再执行同样操作，最后直到left与right相遇,将a[left]与a[keyi]交换，至此一趟完成
当选取中间那个时，先将它与第一个或者最后一个交换，就可以了，然后上面原理

为什么从左边开始时要先从右边先走比较？

如果先从左边走，那么走到右边界都没有数大于关键字，但是在右边界left~right-1之间的值小于或者等于关键字的，那么此时不交换，最后left走到right，这时再从右边走，但是left与right都相遇了此时a[left] = a[right]，也就不用再进行与关键字比较但是如果此时[right]>=a[keyi]，就将a[left]与a[right]交换,那么此时比关键字大的就到left前面去了，最后将a[left]与a[keyi]两个交换，也不能保证a[keyi]左边小于它，

同样选取右边做关键字先从左边走也是同理

二、快速排序（1）

交换接口

void Swap(int* e1, int* e2)
{
	int tmp = *e1;
	*e1 = *e2;
	*e2 = tmp;
}

普通版本

void QuickSort1(int* a, int left, int right)
{
    //当左边区间比右边区间大时或者区间大小为1时不必再排了直接返回
	if (left >= right)
		return;
	//保存上每一趟的左右边界，然后以待递归排序左右区间时使用
	int begin = left;
	int end = right;

	//选取第一个数为key
	int keyi = left;

	while (left < right)
	{
	    //两个没有相遇时，且从右边走它的值的大于或者等于关键字时
		while (left<right &&a[right] >= a[keyi])
			right--;
		//两个没有相遇时，且从左边走它的值小于或者等于关键字时
		while (left<right&&a[left] <= a[keyi])
			left++;
         //最后两者停下时，将其对应值交换
		Swap(&a[right], &a[left]);
	}
     //最后left下标对应的值小于或者等于关键字，将两者交换，keyi左边的值小于a[keyi]，keyi右边的值大于a[keyi]
	Swap(&a[keyi], &a[left]);
	//递归关键字所在它的左区间
	QuickSort1(a, begin, left - 1);
	//递归关键字所在位置它的右区间
	QuickSort1(a, left + 1, end);
}

但是这个普通版本对应数据本已经有序且数据量很大时的情况处理不行了，时间复杂度达到了O(n^2)。当数据有序时，再取最左边或者最右边作为关键字这个方法就不可取了。排序算法之不同版本的快速排序

而此时也有了对快排的优化
随机选数和三数取中那么在有序的情况下选取中间值作为关键字就就最为恰当，此时也就有了三数取中法，但是并不是每一次都是有序的，此时也有了随机选数法

随机选数：选择在区间范围内的随便一个下标对应的值作为关键字，然后这个值再与第一个的值或者最后一个值进行交换，其余操作不变，再让就可以再执行上面排序操作了


void QuickSort1(int* a, int left, int right)
{
	if (left >= right)
		return;
	
	int begin = left;
	int end = right;

	
	//随机选数，主要针对已经有序的情况，提高性能
	int randi = left + (rand() % (right - left));
	if (randi != left)
	{
		Swap(&a[randi], &a[left]);
	}
	
	int keyi = left;

	while (left < right)
	{
		while (left<right &&a[right] >= a[keyi])
			right--;
		
		while (left<right&&a[left] <= a[keyi])
			left++;

		Swap(&a[right], &a[left]);
	}

	Swap(&a[keyi], &a[left]);
	
	QuickSort1(a, begin, left - 1);
	
	QuickSort1(a, left + 1, end);

}

三数取中选关键字：每趟将a[left],a[right],mid = (left+right)/2,
a[mid]中不大不小的那个值作为关键字,这个值再与a[left]或者a[right]交换，然后此时又是其余操作不变，将这些数据排序

//三数取中法
//选中间的值
int GetMid(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (a[mid] > a[left])
	{
		if (a[left] > a[right])
		{
			return left;
		}
		else if (a[right] > a[mid])
		{
			return mid;
		}
		else
		{
			return right;
		}
	}

	else//(a[mid] < a[left])
	{
		if (a[right] > a[left])
		{
			return left;
		}
		else if(a[right] < a[mid])
		{
			return mid;
		}
		else
		{
			return right;
		}
	}
}

void QuickSort1(int* a, int left, int right)
{
	if (left >= right)
		return;
	
	int begin = left;
	int end = right;

	//三数取中，在有序的情况下，中间值是最为恰当的关键字
	int midi = GetMid(a, left, right);
	if (midi != left)
	{
		Swap(&a[left], &a[midi]);
	}
	
	int keyi = left;

	while (left < right)
	{
		while (left<right &&a[right] >= a[keyi])
			right--;
		
		while (left<right&&a[left] <= a[keyi])
			left++;

		Swap(&a[right], &a[left]);
	}

	Swap(&a[keyi], &a[left]);
	
	QuickSort1(a, begin, left - 1);
	
	QuickSort1(a, left + 1, end);
}

三、快速排序（挖坑法）

挖坑法：坑位下标用**hole**表示，先将其关键字保存keyi = left，然后这个关键字所在的位置形成了一个坑位 hole =
left，从右边开始走，a[right]>=a[keyi],right--, 走到比关键字小的,a[right] < a[keyi]，那么将这个值赋给这个坑a[hole] = a[right]，然后这时这个值下标就成为了新的坑位hole = right，
这时从左边开始走a[left] <=a[keyi],left++，走到比关键字大的a[left]>a[keyi]，
将这个值赋给坑位a[hole] =a[left]，然后这个值下标成为新的坑hole = left，以此循环，直到left与right相遇

排序算法之不同版本的快速排序
挖坑法选取关键字时，同样也可用三数取中和随机选数

//挖坑法：坑在左边动右边，坑在右边动左边，最开始以第一个为坑，然后从右边开始与关键字比较，
//大则继续往左边走，小则将这个数赋给坑位，然后这个数对应的下标成为新的坑，
//这时从左边开始走，遇见比关键字小的往右边走，遇见大的则停下，
//将这个数赋给坑，这时这个数下标成为新的坑，以此走下去，
//直到left和right相交，这时的坑位是为空的，需要将关键字放入这个坑位，
//然后这个关键字它的左边数要比他小，右边要比它大

void QuickSort2(int* a, int left, int right)
{
	if (left >= right)return;
	int begin = left;
	int end = right;
	//三数取中
	/*int midi = GetMid(a, left, right);
	if (midi != left)
	{
		Swap(&a[left], &a[midi]);
	}*/

   
	//随机选数
	/*int randi = left + (rand() % (right - left));
	if (randi != left)
	{
		Swap(&a[randi], &a[left]);
	}*/
	int hole = left;
	int key = a[left];
	while (left < right)
	{
		while (left<right&&key < a[right])
		{
			right--;
		}
		a[hole] = a[right];
		hole = right;

		while (left<right&&a[left] < key)
		{
			left++;
		}
		a[hole] = a[left];
		hole = left;
	}
	
	a[hole] = key;
	//递归排关键字所在位置的左区间
	QuickSort2(a, begin, hole - 1);
	//递归排关键字所在位置的右区间
	QuickSort2(a, hole + 1, end);
}

四、快速排序（前后指针法）

前后指针：两个指针，prev,cur,prev代表从关键字开始走，然后cur代表从关键字下一个位置开始走，
cur走，找比关键字小的然后将cur对应的值与prev对应的值交换，之后prev++,cur++,最后cur走到右边界
这一趟已经结束，而此时应该将关键字与prev对应的值交换

//前后指针法
void QuickSort3(int* a, int left, int right)
{
	if (left >= right)
		return;
	int begin = left;
	int end = right;
	//三数取中选数
	/*int midi = GetMid(a, left, right);
	if (midi != left)
	{
		Swap(&a[left], &a[midi]);
	}*/

	//随机选数
	/*int randi = left + (rand() % (right - left));
	if (randi != left)
	{
		Swap(&a[randi], &a[left]);
	}*/
	int key = left;
	int cur = left + 1;
	int prev = left;

	while (cur <= right)
	{
		if (a[cur] < a[key] && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}

	Swap(&a[key], &a[prev]);
	//递归排关键字所在位置的左区间
	QuickSort3(a, begin, prev - 1);
	//递归排关键字所在位置的右区间
	QuickSort3(a, prev + 1, end);
}