快速排序(递归)——C语言实现

快速排序(递归)——C语言实现,第1张

爆肝一万字,全网最详细的快速排序,你想到的,你想不到的这里都有。



🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥🔥

文章目录

  • 一、快速排序

  • 🏀

    二、快速排序之“挖坑法”

    • 🥪2.1 挖坑法思路
    • 🍟2.2 挖坑法图解
    • 🥯2.3 挖坑法动图展示
    • 🧀2.4 单趟排序的代码
    • 🌭2.5 挖坑法总体代码实现
    • 🍖2.6 递归展开图(用于理解)
  • 🏐

    三、时间复杂度分析

    • ✈️3.1 计算时间复杂度
    • 🚀3.2 优化最坏时间复杂度(三数取中)

  • 四、递归调用的内存消耗

    • 🐧4.1 内存消耗
    • 🐤4.2 优化内存消耗(小区间优化)
  • 🏀

    五、加上三数取中和小区间优化后的完整代码


  • 六、快速排序之“左右指针法”

    • 🎺6.1 左右指针法思路
    • 🎸6.2 左右指针法图解
    • 🎻6.3 动图演示
    • 🎷6.4 左右指针法代码
    • 🥁6.5 问题分析
  • 🎱

    七、快速排序之“前后指针法”

    • 🚗7.1 前后指针法思路
    • 🚙7.2 图解
    • 🚕7.3 动图演示
    • 🚛7.4 前后指针法代码
    • 🚜7.5 问题分析


一、快速排序

💉 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。


其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。


🏀

二、快速排序之“挖坑法” 🥪2.1 挖坑法思路

⛳ 单趟排序:单趟排序的目的就是使当前的key值放到它最终的位置,左边全是比它小的数,右边全是比它大的数。


我们一般选取第一个值或者最后一个值做key,pivot初始值为初始的key值的位置,这里也就是第一个位置。


当pivot在begin的位置时,end从右往左开始找比key小的值,找到后将它放到pivot的地方,也就是填坑,填完之后自己形成新的坑位;pivot在end的位置时,begin从左往右开始找比key大的数,找到之后进行填坑,直到begin和end相遇时,最后将key放至相遇点即可。


🍟2.2 挖坑法图解

第一步:定义begin,end,key,pivot这四个变量。


这里选第一个值最为key,那么第一个值自然就是pivot。




第二步:将key值拿走,第一个值成为pivot。



第三步:这时候pivot在begin位置,那么end就开始从右至左找比key小的值,找到后放入pivot。


所以将2放到pivot的位置,end成为新的pivot。



第四步:这时候pivot在end位置,那么begin开始从左至右找比key大的值,找到后放入pivot。


所以将8放到pivot的位置,begin成为新的pivot。



第五步:end继续找小,找到4放到pivot,end成为新的pivot。



第六步:begin继续找大,这里与end汇合了,停止循环,把key放到相遇位置即可。



🥯2.3 挖坑法动图展示

🧀2.4 单趟排序的代码
void QuickSort(int* arr, int n)
{
	int begin = 0;
	int end = n-1;
	int key = arr[begin];
	int pivot = begin;

	while (begin < end)
	{
		//pivot在begin那边,则end这边找比key小
		while (begin < end&&arr[end] >= key)
		{
			end--;
		}
		//循环结束则为找到该小值,将之赋值给arr[pivot]
		arr[pivot] = arr[end];
		//自己形成新的坑位
		pivot = end;

		//piovt在end那边,则begin这边找比key大
		while (begin < end&&arr[begin] <= key)
		{
			begin++;
		}
		//循环结束则为找到该大值,将之赋值给arr[pivot]
		arr[pivot] = arr[begin];
		//自己形成新的坑位
		pivot = begin;
	}
	//循环结束代表begin和end相遇,并且相遇在坑(pivot)
	pivot = begin;//这里给begin和end都可以
	//将key放到pivot
	arr[pivot] = key;
}
🌭2.5 挖坑法总体代码实现

单趟排完后,已经有一个值被放到了正确的位置,以该值做分割,此时区间被分为左右两个子区间,然后对左右两个子区间进行递归即可。


#include

void Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}

void QuickSort(int* arr, int left,int right)
{
	//当区间被分到只有1个元素时,则返回
	//=代表只有一个元素,>代表没有右区间,为什么会出现大于可以看下面递归图
	if (left >= right)
	{
		return;
	}

	int begin = left;
	int end = right;
	int key = arr[begin];
	int pivot = begin;

	while (begin < end)
	{
		//pivot在begin那边,则end这边找比key小
		while (begin < end&&arr[end] >= key)
		{
			end--;
		}
		//循环结束则为找到该小值,将之赋值给arr[pivot]
		arr[pivot] = arr[end];
		//自己形成新的坑位
		pivot = end;

		//piovt在end那边,则begin这边找比key大
		while (begin < end&&arr[begin] <= key)
		{
			begin++;
		}
		//循环结束则为找到该大值,将之赋值给arr[pivot]
		arr[pivot] = arr[begin];
		//自己形成新的坑位
		pivot = begin;
	}
	//循环结束代表begin和end相遇,并且相遇在坑(pivot)
	pivot = begin;//这里给begin和end都可以
	//将key放到pivot
	arr[pivot] = key;

	//将区间分为[left,pivot-1] pivot [pivot+1,right]
	//采用分治递归,左边有序了,右边有序了,则整体有序
	QuickSort(arr, left, pivot - 1);
	QuickSort(arr, pivot + 1, right);
}

void test01()
{
	int arr1[] = { 5,8,1,4,9,6,2 };
	int n = sizeof(arr1) / sizeof(arr1[0]);
	QuickSort(arr1, 0, n - 1);
	Print(arr1, n);
}

int main()
{
	test01();
	return 0;
}
🍖2.6 递归展开图(用于理解)

🏐

三、时间复杂度分析 ✈️3.1 计算时间复杂度

我们先计算单趟排序的时间复杂度,很简单,单趟排序就是begin和end两个指针往中间一起走知道汇合,将数组遍历了一遍,所以单趟排序的时间复杂度为O(N)



递归的时间复杂度,我们假设每次取到的数都是中间数,也就是接近二分,看下图:
把它看出一颗完全二叉树,每一层都是N个数,总共有logN层,所以总体的时间复杂度为O(N*logN)


但是这是理想情况,那么最坏情况又是什么时候呢?没错,就是序列有序时最坏。


看下图:

每次只排好一个上数,那么我们递归的深度就是N,每趟时间复杂度O(N),那么N趟下来就是O(N^2)。


🚀3.2 优化最坏时间复杂度(三数取中)

由上面的时间复杂度分析可知,当序列有序时,时间复杂度为O(N^2)。


这是因为我们选的key值总是最大或者最小,所以我们只要保证所选的值不是最大或者最小就能达到优化的效果。


这里我们采取三数取中。


🏕三数取中基本思想:取序列中的左右中三个数选出中间值最为key值进行排序。


三数取中的代码为:

int GetMinIndex(int* arr,int left,int right)
{
	int mid = (left + right) >> 1;
	if (arr[left] < arr[mid])
	{
		if (arr[mid] < arr[right])
		{
			return mid;
		}
		if (arr[left] < arr[right] && arr[right] < arr[mid])
		{
			return right;
		}
		return left;
	}
	else//arr[left] >= arr[mid]
	{
		if (arr[left] < arr[right])
		{
			return left;
		}
		if (arr[mid]<arr[right] && arr[right] < arr[left])
		{
			return right;
		}
		return mid;
	}
}

将之运用到快速排序代码:

void Swap(int* p1, int*p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void QuickSort(int* arr, int left,int right)
{
	//当区间被分到只有1个元素时,则返回
	if (left >= right)
	{
		return;
	}

	int index = GetMinIndex(arr, left, right);
	//因为我们下面的逻辑都是把第一个数作为key,
	//为了避免改动代码,这里我们直接交换就可以
	Swap(&arr[left], &arr[index]);

	int begin = left;
	int end = right;
	int key = arr[begin];
	int pivot = begin;

	while (begin < end)
	{
		//pivot在begin那边,则end这边找比key小
		while (begin < end&&arr[end] >= key)
		{
			end--;
		}
		//循环结束则为找到该小值,将之赋值给arr[pivot]
		arr[pivot] = arr[end];
		//自己形成新的坑位
		pivot = end;

		//piovt在end那边,则begin这边找比key大
		while (begin < end&&arr[begin] <= key)
		{
			begin++;
		}
		//循环结束则为找到该大值,将之赋值给arr[pivot]
		arr[pivot] = arr[begin];
		//自己形成新的坑位
		pivot = begin;
	}
	//循环结束代表begin和end相遇,并且相遇在坑(pivot)
	pivot = begin;//这里给begin和end都可以
	//将key放到pivot
	arr[pivot] = key;

	//将区间分为[left,pivot-1] pivot [pivot+1,right]
	//采用分治递归,左边有序了,右边有序了,则整体有序
	QuickSort(arr, left, pivot - 1);
	QuickSort(arr, pivot + 1, right);
}

采取三数取中后,快排不会出现最快情况,时间复杂度就是O(N*logN)。



四、递归调用的内存消耗 🐧4.1 内存消耗

这里我们先解释一下什么是函数栈帧。


🌴函数栈帧:C语言中,每个栈帧对应着一个未运行完的函数,栈帧中保存着该函数的函数地址和局部变量。


由此可见,每一次递归调用时,都会在内存的栈区上存一个函数栈帧,当递归的深度过深时,就可能导致栈溢出


🐤4.2 优化内存消耗(小区间优化)

为了减少递归调用的内存消耗,这里我们做一个小小的优化——小区间优化。


看下图:
我我们假设有100万个数需要排序,那我们就得调用100万次,栈上就需要存储100万个函数栈帧,显然这不是我们想要看到的结果。


我们需要将之优化一下。


最后由上图可以看到,最后三层的调用就占了87.5万次,所以我们只需要将最后三层的调用消除,就可以达到优化的效果。


如何优化:倒数第三层时,子区间差不多被分到了不到10个数,数据量极小,所以我们只需要采用直接插入排序就可以了。


我们需要改动的代码就只有最后递归时候,需要加上判断条件。


//将区间分为[left,pivot-1] pivot [pivot+1,right]
if(pivot-1-left>13)
{
	QuickSort(arr, left, pivot - 1);
}
else
{
	InsertSort(arr+left, pivot-1-left+1);
}
if(right-(pivot+1)>13)
{
	QuickSort(arr,pivot+1,right);
}
else
{
	InsertSort(arr+pivot+1, right-(pivot+1)+1);
}

InsertSort为插入排序,这里的代码就不再赘述了,直接使用。



详情可点击——>>插入排序详解

🏀

五、加上三数取中和小区间优化后的完整代码

#include

//打印函数
void Print(int* arr, int n)
{
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
}


//交换函数
void Swap(int* p1, int*p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//直接插入排序
void InsertSort(int* arr, int sz)
{
	for (int i = 0; i < sz - 1; i++)//注意这里i相当于就等end,i必须是小于sz-1
	{
		//此for循环是要排序的趟数
		int end = i;
		int tmp = arr[end + 1];
		//此while循环是一趟下来要比较的次数
		while (end >= 0)//只要end没出界就继续比较
		{
			if (tmp < arr[end])
			{
				//在比较的过程中只要tmp值比arr[end]小,就向后移动arr[end]
				arr[end + 1] = arr[end--];
				//end--;
			}
			else
			{
				//一旦出现相等或者比arr[end]大,就将tmp插入到arr[end+1]处
				//这里break掉是因为,如果循环结束,说明要插入的值比所以的值都要小,
				//要插入到头部,所有到while后面一并处理
				break;
			}
		}
		arr[end + 1] = tmp;
	}
}

//三数取中
int GetMinIndex(int* arr, int left, int right)
{
	int mid = (left + right) >> 1;
	if (arr[left] < arr[mid])
	{
		if (arr[mid] < arr[right])
		{
			return mid;
		}
		if (arr[left] < arr[right] && arr[right] < arr[mid])
		{
			return right;
		}
		return left;
	}
	else//arr[left] >= arr[mid]
	{
		if (arr[left] < arr[right])
		{
			return left;
		}
		if (arr[mid] < arr[right] && arr[right] < arr[left])
		{
			return right;
		}
		return mid;
	}
}

//快速排序挖坑法
void QuickSort(int* arr, int left,int right)
{
	//当区间被分到只有1个元素时,则返回
	if (left >= right)
	{
		return;
	}

	int index = GetMinIndex(arr, left, right);
	//因为我们下面的逻辑都是把第一个数作为key,
	//为了避免改动代码,这里我们直接交换就可以
	Swap(&arr[left], &arr[index]);

	int begin = left;
	int end = right;
	int key = arr[begin];
	int pivot = begin;

	while (begin < end)
	{
		//pivot在begin那边,则end这边找比key小
		while (begin < end&&arr[end] >= key)
		{
			end--;
		}
		//循环结束则为找到该小值,将之赋值给arr[pivot]
		arr[pivot] = arr[end];
		//自己形成新的坑位
		pivot = end;

		//piovt在end那边,则begin这边找比key大
		while (begin < end&&arr[begin] <= key)
		{
			begin++;
		}
		//循环结束则为找到该大值,将之赋值给arr[pivot]
		arr[pivot] = arr[begin];
		//自己形成新的坑位
		pivot = begin;
	}
	//循环结束代表begin和end相遇,并且相遇在坑(pivot)
	pivot = begin;//这里给begin和end都可以
	//将key放到pivot
	arr[pivot] = key;

	//将区间分为[left,pivot-1] pivot [pivot+1,right]
	//采用分治递归,左边有序了,右边有序了,则整体有序
	//小区间优化
	if (pivot - 1 - left > 10)
	{
		QuickSort(arr, left, pivot - 1);
	}
	else
	{
		InsertSort(arr + left, pivot - 1 - left + 1);
	}
	if (right - (pivot + 1) > 10)
	{
		QuickSort(arr, pivot + 1, right);
	}
	else
	{
		InsertSort(arr + pivot + 1, right - (pivot + 1) + 1);
	}
}

void test01()
{
	int arr1[] = { 5,8,1,4,9,6,2 };
	int n = sizeof(arr1) / sizeof(arr1[0]);
	QuickSort(arr1, 0, n - 1);
	Print(arr1, n);
}

int main()
{
	test01();
	return 0;
}

六、快速排序之“左右指针法”

理解了前面的挖坑法,左右指针法将不难理解。


🎺6.1 左右指针法思路

🌲定义begin和end两个指针,end从右向左找比key值小的,找到停下;begin从左向右找比key值大的,找到停下;然后交换这两个值,一直循环下去,直到相遇。


🎸6.2 左右指针法图解

还是拿arr=[5,8,1,4,9,2,6]为例
第一步:定义号begin,end,和key,我们取第一个值为key。



第二步:end从右向左找比key值小的,找到8停下;begin从左向右找比key值大的,找到2停下。


特别注意:选左边作为key,要保证右边的end先动。



第三步:交换8和2;

第四步:end继续从右向左找比key值小的,找到4停下;begin从左向右找比key值大的,没找到,但是在4的位置于end相遇了,停下。



第五步:相遇位置的值一定小于key,交换key和相遇位置的值,也就是5和4。


单趟排序完毕。



🎻6.3 动图演示

🎷6.4 左右指针法代码
//快速排序左右指针法
void QuickSort(int *arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	//三数取中
	int index = GetMinIndex(arr, left, right);
	Swap(&arr[left], &arr[index]);

	int begin = left;
	int end = right;
	int key = arr[begin];

	while (begin < end)
	{
		//end找小
		while (begin < end && arr[end] >= key)
		{
			end--;
		}

		//begin找大
		while (begin < end && arr[begin] <= key)
		{
			begin++;
		}
		Swap(&arr[begin], &arr[end]);
	}
	Swap(&arr[begin], &key);

	//将区间分为[left,begin-1] begin [begin+1,right]
	//小区间优化
	if (begin - 1 - left > 10)
	{
		QuickSort1(arr, left, begin - 1);
	}
	else
	{
		InsertSort(arr + left, begin - 1 - left + 1);
	}
	if (right - (begin + 1) > 10)
	{
		QuickSort1(arr, begin + 1, right);
	}
	else
	{
		InsertSort(arr + begin + 1, right - (begin + 1) + 1);
	}
}
🥁6.5 问题分析
//end找小
		while (begin < end && arr[end] >= key)
		{
			end--;
		}

对于上面这段代码,有些人会有个疑问,为什么要在判断条件上加上begin


如果这个地方不加这个条件,那么在极端条件下,也就是顺序的情况下,end永远不会小于key,while循环不会在正常范围内停下来,就会一直减减直到数组越界。


当然加了三数取中后,是不会出现这种情况的,但不是每个时候都有三数取中。



那如果将arr[end]>=key改成arr[end]>key能解决问题吗?看似解决了,实则衍生出了新的问题。


看下图,可能会造成死循环。



🎱

七、快速排序之“前后指针法” 🚗7.1 前后指针法思路

🎋定义一前一后两个指针,prev和cur,以及一个key值,key值取第一个值。


prev指向第一个值,cur指向第二个值。


cur从左向右找比key小的值,找到停下,然后prev++,然后交换arr[cur]和arr[prev],循环下去直到cur将数组遍历完。


🚙7.2 图解

第一步:将第一个值作为key值,定义prev和cur。




第二步:cur向右找小,找到1停下,prev++到8的位置,交换1和8。




第三步:cur继续向右找小,找到4停下,prev++到8的位置,交换8和4。




第四步:cur继续向右找小,找到2停下,prev++到8的位置,交换8和2。




第五步:cur继续向右找小,越界停止,交换key和prev位置的值,也就是5和2。



🚕7.3 动图演示

🚛7.4 前后指针法代码
//前后指针法
void QuickSort3(int *arr, int left, int right)
{
	if (left >= right)
	{
		return;
	}

	//三数取中
	int index = GetMinIndex(arr, left, right);
	Swap(&arr[left], &arr[index]);

	int prev = left;
	int cur = left + 1;
	int key = arr[left];

	while (cur <= right)
	{
		//cur找小
		while (arr[cur] < key && ++prev != cur)
		{
			Swap(&arr[prev], &arr[cur]);
		}
		cur++;
	}
	Swap(&arr[prev], &key);

	//将区间分为[left,prev-1] prev [prev+1,right]
	//小区间优化
	if (prev - 1 - left > 10)
	{
		QuickSort1(arr, left, prev - 1);
	}
	else
	{
		InsertSort(arr + left, prev - 1 - left + 1);
	}
	if (right - (prev + 1) > 10)
	{
		QuickSort1(arr, prev + 1, right);
	}
	else
	{
		InsertSort(arr + prev + 1, right - (prev + 1) + 1);
	}
}
🚜7.5 问题分析
//cur找小
		while (arr[cur] < key && ++prev != cur)
		{
			Swap(&arr[prev], &arr[cur]);
		}

在上面的代码中,为什么要加上++prev != cur?

这是为了避免prev和cur走到一个位置上,交换同样的数,没有必要。


欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/langs/577603.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-04-11
下一篇 2022-04-11

发表评论

登录后才能评论

评论列表(0条)

保存