您现在的位置是:首页 >技术教程 >这个 快速排序详解过程 我能吹一辈子!网站首页技术教程

这个 快速排序详解过程 我能吹一辈子!

Yumpie_ 2024-06-17 11:25:17
简介这个 快速排序详解过程 我能吹一辈子!

快速排序概念

快速排序是公认的排序之王,快速排序是Hoare于1962年提出的一种二叉树结构的交换排序算法,其基本思想为:
 任取待排序元素序列中的某元素作为基准值,按照该基准值将待排序列分为两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后左右序列重复该过程,直到所有元素都排列在相应位置上为止。

对于如何按照基准值将待排序列分为两子序列,常见的方式有:
 1、Hoare版本
 2、挖坑法
 3、前后指针法

快速排序递归实现

Hoare版本

单趟的动图演示:
在这里插入图片描述
Hoare版本的单趟排序的基本步骤如下:
1、选出一个key,一般是最左边或是最右边的。
2、定义一个L和一个R,L从左向右走,R从右向左走。(需要注意的是:若选择最左边的数据作为key,则需要R先走;若选择最右边的数据作为key,则需要L先走)。
3、在走的过程中,若R遇到小于key的数,则停下,L开始走,直到L遇到一个大于key的数时,将L和R的内容交换,R再次开始走,如此进行下去,直到L和R最终相遇,此时将相遇点的内容与key交换即可。(选取最左边的值作为key)

经过一次单趟排序,最终使得key左边的数据全部都小于key,key右边的数据全部都大于key。

然后我们在将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作,因为这种序列可以认为是有序的。

代码示例:

//快速排序(Hoare版本)
void QuickSort1(int* a, int begin, int end)
{
	if (begin >= end)//当只有一个数据或是序列不存在时,不需要进行操作
		return;
		
	int left = begin;//L
	int right = end;//R
	int keyi = left;//key的下标
	while (left < right)
	{
		//right先走,找小
		while (left < right&&a[right] >= a[keyi])
		{
			right--;
		}
		//left后走,找大
		while (left < right&&a[left] <= a[keyi])
		{
			left++;
		}
		if (left < right)//交换left和right的值
		{
			Swap(&a[left], &a[right]);
		}
	}
	int meeti = left;//L和R的相遇点
	Swap(&a[keyi], &a[meeti]);//交换key和相遇点的值

	QuickSort1(a, begin, meeti - 1);//key的左序列进行此操作
	QuickSort1(a, meeti + 1, end);//key的右序列进行此操作
}

时间复杂度:O(N*logN)

挖坑法

单趟的动图演示:
在这里插入图片描述
挖坑法的单趟排序的基本步骤如下:
 1、选出一个数据(一般是最左边或是最右边的)存放在key变量中,在该数据位置形成一个坑。
 2、还是定义一个L和一个R,L从左向右走,R从右向左走。(若在最左边挖坑,则需要R先走;若在最右边挖坑,则需要L先走)。
 3、在走的过程中,若R遇到小于key的数,则将该数抛入坑位,并在此处形成一个坑位,这时L再向后走,若遇到大于key的数,则将其抛入坑位,又形成一个坑位,如此循环下去,直到最终L和R相遇,这时将key抛入坑位即可。(选取最左边的作为坑位)

经过一次单趟排序,最终也使得key左边的数据全部都小于key,key右边的数据全部都大于key。

然后也是将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作。

代码示例:

//快速排序(挖坑法)
void QuickSort2(int* a, int begin, int end)
{
	if (begin >= end)//当只有一个数据或是序列不存在时,不需要进行操作
		return;

	int left = begin;//L
	int right = end;//R
	int key = a[left];//在最左边形成一个坑位
	while (left < right)
	{
		//right向左,找小
		while (left < right&&a[right] >= key)
		{
			right--;
		}
		//填坑
		a[left] = a[right];
		//left向右,找大
		while (left < right&&a[left] <= key)
		{
			left++;
		}
		//填坑
		a[right] = a[left];
	}
	int meeti = left;//L和R的相遇点
	a[meeti] = key;//将key抛入坑位

	QuickSort2(a, begin, meeti - 1);//key的左序列进行此操作
	QuickSort2(a, meeti + 1, end);//key的右序列进行此操作
}

时间复杂度:O(N*logN)

前后指针法

单趟的动图演示:
在这里插入图片描述
前后指针法的单趟排序的基本步骤如下:
 1、选出一个key,一般是最左边或是最右边的。
 2、起始时,prev指针指向序列开头,cur指针指向prev+1。
 3、若cur指向的内容小于key,则prev先向后移动一位,然后交换prev和cur指针指向的内容,然后cur指针++;若cur指向的内容大于key,则cur指针直接++。如此进行下去,直到cur指针越界,此时将key和prev指针指向的内容交换即可。

经过一次单趟排序,最终也能使得key左边的数据全部都小于key,key右边的数据全部都大于key。

然后也还是将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作。

代码示例:

//快速排序(前后指针法)
void QuickSort3(int* a, int begin, int end)
{
	if (begin >= end)//当只有一个数据或是序列不存在时,不需要进行操作
		return;

	//三数取中
	int midIndex = GetMidIndex(a, begin, end);
	Swap(&a[begin], &a[midIndex]);

	int prev = begin;
	int cur = begin + 1;
	int keyi = begin;
	while (cur <= end)//当cur未越界时继续
	{
		if (a[cur] < a[keyi] && ++prev != cur)//cur指向的内容小于key
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	int meeti = prev;//cur越界时,prev的位置
	Swap(&a[keyi], &a[meeti]);//交换key和prev指针指向的内容

	QuickSort3(a, begin, meeti - 1);//key的左序列进行此操作
	QuickSort3(a, meeti + 1, end);//key的右序列进行此操作
}

时间复杂度:O(N*logN)

快速排序非递归实现

当我们需要将一个用递归实现的算法改为非递归时,一般需要借用一个数据结构,那就是栈。将Hoare版本、挖坑法以及前后指针法的快速排序改为非递归版本,其实主体思想一致,只是调用的单趟排序的算法不同而已。
 于是我们可以先将Hoare版本、挖坑法和前后指针法的单趟排序单独封装起来。然后写一个非递归的快速排序,在函数内部调用单趟排序的函数即可。

Hoare版本

Hoare版本的单趟排序代码:

//Hoare版本(单趟排序)
int PartSort1(int* a, int left, int right)
{
	int keyi = left;//key的下标
	while (left < right)
	{
		//right走,找小
		while (left < right&&a[right] >= a[keyi])
		{
			right--;
		}
		//left先走,找大
		while (left < right&&a[left] <= a[keyi])
		{
			left++;
		}
		if (left < right)
		{
			Swap(&a[left], &a[right]);//交换left和right的值
		}
	}
	int meeti = left;//L和R的相遇点
	Swap(&a[keyi], &a[meeti]);//交换key和相遇点的值
	return meeti;//返回相遇点,即key的当前位置
}

挖坑法

挖坑法的单趟排序代码:

//挖坑法(单趟排序)
int PartSort2(int* a, int left, int right)
{
	int key = a[left];//在最左边形成一个坑位
	while (left < right)
	{
		//right向左,找小
		while (left < right&&a[right] >= key)
		{
			right--;
		}
		//填坑
		a[left] = a[right];
		//left向右,找大
		while (left < right&&a[left] <= key)
		{
			left++;
		}
		//填坑
		a[right] = a[left];
	}
	int meeti = left;//L和R的相遇点
	a[meeti] = key;//将key抛入坑位
	return meeti;//返回key的当前位置
}

前后指针法

前后指针法的单趟排序代码:

//前后指针法(单趟排序)
int PartSort3(int* a, int left, int right)
{
	int prev = left;
	int cur = left + 1;
	int keyi = left;
	while (cur <= right)//当cur未越界时继续
	{
		if (a[cur] < a[keyi] && ++prev != cur)//cur指向的内容小于key
		{
			Swap(&a[prev], &a[cur]);
		}
		cur++;
	}
	int meeti = prev;//cur越界时,prev的位置
	Swap(&a[keyi], &a[meeti]);//交换key和prev指针指向的内容
	return meeti;//返回key的当前位置
}

快速排序的非递归算法基本思路
 1、先将待排序列的第一个元素的下标和最后一个元素的下标入栈。
 2、当栈不为空时,读取栈中的信息(一次读取两个:一个是L,另一个是R),然后调用某一版本的单趟排序,排完后获得了key的下标,然后判断key的左序列和右序列是否还需要排序,若还需要排序,就将相应序列的L和R入栈;若不需排序了(序列只有一个元素或是不存在),就不需要将该序列的信息入栈。
 3、反复执行步骤2,直到栈为空为止。

代码示例:

//快速排序(非递归实现)
void QuickSortNonR(int* a, int begin, int end)
{
	Stack st;//创建栈
	StackInit(&st);//初始化栈
	StackPush(&st, begin);//待排序列的L
	StackPush(&st, end);//待排序列的R
	while (!StackEmpty(&st))
	{
		int right = StackTop(&st);//读取R
		StackPop(&st);//出栈
		int left = StackTop(&st);//读取L
		StackPop(&st);//出栈
		//该处调用的是Hoare版本的单趟排序
		int keyi = PartSort1(a, left, right);
		if (left < keyi - 1)//该序列的左序列还需要排序
		{
			StackPush(&st, left);//左序列的L入栈
			StackPush(&st, keyi - 1);//左序列的R入栈
		}
		if (keyi + 1 < right)// 该序列的右序列还需要排序
		{
			StackPush(&st, keyi + 1);//右序列的L入栈
			StackPush(&st, right);//右序列的R入栈
		}
	}
	StackDestroy(&st);//销毁栈
}

时间复杂度:O(N*logN)

快速排序的俩个优化

三数取中

快速排序的时间复杂度是O(NlogN),是我们在理想情况下计算的结果。在理想情况下,我们每次进行完单趟排序后,key的左序列与右序列的长度都相同:
在这里插入图片描述
若每趟排序所选的key都正好是该序列的中间值,即单趟排序结束后key位于序列正中间,那么快速排序的时间复杂度就是O(NlogN)。

可是谁能保证你每次选取的key都是正中间的那个数呢?当待排序列本就是一个有序的序列时,我们若是依然每次都选取最左边或是最右边的数作为key,那么快速排序的效率将达到最低:
在这里插入图片描述
可以看到,这种情况下,快速排序的时间复杂度退化为O(N2)。其实,对快速排序效率影响最大的就是选取的key,若选取的key越接近中间位置,则则效率越高。

为了避免这种极端情况的发生,于是出现了三数取中:
 三数取中,当中的三数指的是:最左边的数、最右边的数以及中间位置的数。三数取中就是取这三个数当中,值的大小居中的那个数作为该趟排序的key。这就确保了我们所选取的数不会是序列中的最大或是最小值了。

代码示例:

//三数取中
int GetMidIndex(int* a, int left, int right)
{
	int mid = left + (right - left) / 2;
	if (a[mid] > a[left])
	{
		if (a[mid] < a[right])
			return mid;
		else if (a[left]>a[right])
			return left;
		else
			return right;
	}
	else
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[left] > a[right])
			return right;
		else
			return left;
	}
}

注意:当大小居中的数不在序列的最左或是最右端时,我们不是就以居中数的位置作为key的位置,而是将key的值与最左端的值进行交换,这样key就还是位于最左端了,所写代码就无需改变,而只需在单趟排序代码开头加上以下两句代码即可:

	int midIndex = GetMidIndex(a, begin, end);//获取大小居中的数的下标
	Swap(&a[begin], &a[midIndex]);//将该数与序列最左端的数据交换
	//以下代码保持不变...

小区间优化

我们可以看到,就算是上面理想状态下的快速排序,也不能避免随着递归的深入,每一层的递归次数会以2倍的形式快速增长。
 为了减少递归树的最后几层递归,我们可以设置一个判断语句,当序列的长度小于某个数的时候就不再进行快速排序,转而使用其他种类的排序。小区间优化若是使用得当的话,会在一定程度上加快快速排序的效率,而且待排序列的长度越长,该效果越明显。

代码示例:

//优化后的快速排序
void QuickSort0(int* a, int begin, int end)
{
	if (begin >= end)//当只有一个数据或是序列不存在时,不需要进行操作
		return;

	if (end - begin + 1 > 20)//可自行调整
	{
		//可调用快速排序的单趟排序三种中的任意一种
		//int keyi = PartSort1(a, begin, end);
		//int keyi = PartSort2(a, begin, end);
		int keyi = PartSort3(a, begin, end);
		QuickSort(a, begin, keyi - 1);//key的左序列进行此操作
		QuickSort(a, keyi + 1, end);//key的右序列进行此操作
	}
	else
	{
		//HeapSort(a, end - begin + 1);
		ShellSort(a, end - begin + 1);//当序列长度小于等于20时,使用希尔排序
	}
}

风语者!平时喜欢研究各种技术,目前在从事后端开发工作,热爱生活、热爱工作。