C语言实现快速排序

图解：这样我们的的单次排序就好了，然后就和挖坑法一样分成左右区间，再递归排序就好了。

文章共7,101字 · 阅读需要大约24分钟

一键AI生成摘要，助你高效阅读

问答

LQB木杉

5387人浏览 · 2023-04-12 22:32:38

LQB木杉 · 2023-04-12 22:32:38 发布

快速排序

一、递归实现快速排序
二、非递归实现快速排序
三、快速排序的优化
- 优化1：三数取中
- 优化2：小区间排序
四、快速排序的时间复杂度及稳定性

快速排序：快速排序是冒泡排序的改进，它的基本思想是定义一个基准数（一般取第一或最后一个数），每次快排把比这个基准数小的放一边，比它大的放另一边，再把基准数插入，这样基准数的位置就排好了，然后再对两边进行快排，最后就达到了有序。

一、递归实现快速排序

1、挖坑法

挖坑法就是定义一个基准数（key）,把key取出，形成一个坑
在这里插入图片描述
然后从右向左找一个比key小的数，把它挖出放到前面那个坑，这样就又形成了一个新的坑

再从左向右找一个比key大的数，把它挖出放到后面那个坑，然后形成一个新坑

然后又从右向左找一个比key小的数，再挖坑填坑
在这里插入图片描述
再从左向右找一个比key大的数，挖坑填坑

在这里插入图片描述

最后begin>=end挖坑就结束了，这时候把key放入最后一个坑，快排的单次排序就结束了，此时key（6）的一边比它小一边比它大，6的位置就排好了。
代码如下：

int PartSort1(int*a,int left,int right)
{
	int begin = left;
	int end = right;
	/*int midindex = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midindex]);*/
	int key = a[left];
	int pivot = left;
	while (begin < end)
	{
		//找小
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		a[pivot] = a[end];
		pivot = end;
		//找大
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[pivot] = a[begin];
		pivot = begin;
	}
	pivot = begin;
	a[pivot] = key;

	return pivot;
}

当我们实现了单次排序后就可以采用分而治之的思路，把6的两边分成两个区间进行递归排序。
代码如下：



void QuickSort(int* a, int left,int right)
{
	if (left >= right)
	{
		return;
	}
	int keyindex = PartSort1(a, left, right);
	QuickSort(a, left, keyindex - 1);//对key的左边进行递归排序
	QuickSort(a, keyindex + 1, right);//对key的右边进行递归排序
}

2、左右指针法

左右指针法的思想是定义两个指针左指针和右指针，每次右指针向左移动找一个比key（key和上面的挖坑法一样）小的数，左指针向右移找一个比key大的数，然后把这个两个数交换，然后再移动交换，最后左指针和右指针相遇的时候把key和左指针交换序列就排好了。
图解：
在这里插入图片描述

这样我们的的单次排序就好了，然后就和挖坑法一样分成左右区间，再递归排序就好了

int PartSort2(int* a, int left, int right)
{
	int begin = left;
	int end = right;
	int midindex = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midindex]);
	int key = a[left];
	while (begin < end)
	{
		//找小
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		//找大
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[left]);
	return begin;
}
void QuickSort(int* a, int left,int right)
{
	if (left >= right)
	{
		return;
	}
	//int keyindex = PartSort1(a, left, right);
	int keyindex = PartSort2(a, left, right);
	//int keyindex = PartSort3(a, left, right);
	QuickSort(a, left, keyindex - 1);
	QuickSort(a, keyindex + 1, right);
}

3、前后指针法

前后指针法和左右指针法类似，都是定义两个指针，通过指针找比key大的数，然后交换，最后交换key和prev指针，单次排序就好了，然后进行递归排序，序列就有序了。
图解：
在这里插入图片描述

经过上面的步骤单次排序就好了。
代码如下：

int PartSort3(int* a, int left, int right)
{
	int midindex = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midindex]);
	int prev = left, cur = left + 1;
	int key = a[left];
	while (cur <= right)
	{
		if (a[cur] < key && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[left], &a[prev]);
	return prev;
}
void QuickSort(int* a, int left,int right)
{
	if (left >= right)
	{
		return;
	}
	//int keyindex = PartSort1(a, left, right);
	int keyindex = PartSort2(a, left, right);
	//int keyindex = PartSort3(a, left, right);
	QuickSort(a, left, keyindex - 1);
	QuickSort(a, keyindex + 1, right);
}

完整代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include <stdlib.h>

void PrintArray(int* a, int n)//把数组中的元素打印出来
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void Swap(int* p1, int* p2)//交换两个值
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//挖坑法
int PartSort1(int*a,int left,int right)
{
	int begin = left;
	int end = right;
	int key = a[left];
	int pivot = left;
	while (begin < end)
	{
		//找小
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		a[pivot] = a[end];
		pivot = end;
		//找大
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[pivot] = a[begin];
		pivot = begin;
	}
	pivot = begin;
	a[pivot] = key;

	return pivot;
}
//左右指针法
int PartSort2(int* a, int left, int right)
{
	int begin = left;
	int end = right;
	int key = a[left];
	while (begin < end)
	{
		//找小
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		//找大
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		Swap(&a[begin], &a[end]);
	}
	Swap(&a[begin], &a[left]);
	return begin;
}
//前后指针法
int PartSort3(int* a, int left, int right)
{
	int prev = left, cur = left + 1;
	int key = a[left];
	while (cur <= right)
	{
		if (a[cur] < key && ++prev != cur)
		{
			Swap(&a[cur], &a[prev]);
		}
		cur++;
	}
	Swap(&a[left], &a[prev]);
	return prev;
}
void QuickSort(int* a, int left,int right)
{
	if (left >= right)
	{
		return;
	}
	int keyindex = PartSort1(a, left, right);//挖坑法
	//int keyindex = PartSort2(a, left, right);//左右指针法
	//int keyindex = PartSort3(a, left, right);//前后指针法
	QuickSort(a, left, keyindex - 1);
	QuickSort(a, keyindex + 1, right);
}
void TestQuickSort()
{
	int a[] = { 6,1,2,7,9,3,4,5,10,8 };
	QuickSort(a, 0,sizeof(a) / sizeof(int)-1);
	PrintArray(a, sizeof(a) / sizeof(int));
}
int main()
{
	TestQuickSort();
	return 0;
}

二、非递归实现快速排序

递归实现快速排序虽然代码更简洁清晰，可读性更好；但其时间和空间消耗比较大、很多计算都是重复的、调用栈可能会溢出。因此，我们还需要掌握非递归实现快速排序。
非递归实现快速排序我们是用栈来实现的，每次单次排序前我们把要排的区间放入栈，再从栈中取出进行单次排序，再把key的左右区间放入栈，再对其单次排序，再取出……直到栈为空，我们就排好了。
图解：
在这里插入图片描述
把keyindex的两边入栈

然后再入栈，再取出排序

……（中间省略）

在最后我们可以看到，栈已经被取空了，排序就结束了
代码如下：

void PrintArray(int* a, int n)//把数组中的元素打印出来
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}
void Swap(int* p1, int* p2)//交换两个值
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
void QuickSortNonR(int *a,int n)
{
	ST st;
	StackInit(&st);
	StackPush(&st, n - 1);
	StackPush(&st, 0);
	while (!StackEmpty(&st))
	{
		//把区间从栈中取出排序
		int left = StackTop(&st);
		StackPop(&st);
		int right = StackTop(&st);
		StackPop(&st);
		int keyindex = PartSort3(a, left, right);//此处也可以挖坑或前后指针
		//把左右区间入栈
		if (keyindex+1 < right)
		{
			StackPush(&st, right);
			StackPush(&st, keyindex + 1);
		}
		if (keyindex-1 > left)
		{
			StackPush(&st, keyindex - 1);
			StackPush(&st, left);
		}
	}
}
void TestQuickSortNonR()
{
	int a[] = { 6,1,2,7,9,3,4,5,10,8 };
	QuickSortNonR(a, sizeof(a) / sizeof(int));
	PrintArray(a, sizeof(a) / sizeof(int));
}

三、快速排序的优化

优化1：三数取中

我们知道快速排序是根据key的值采用分而治之的思路实现的，但是，如果key的值太小或太大就会出现一边倒的情况，那么快速排序的效率就会降低很多，如图：
在这里插入图片描述
对此，科学家们引入了三数取中
代码如下：

int GetMidIndex(int* a, int left, int right)
{
	int mid = (left + right) / 2;
	if (mid > left)
	{
		if (mid < right)
			return mid;
		else
			return right;
	}
	else
	{
		return left;
	}
}
int PartSort1(int*a,int left,int right)
{
	int begin = left;
	int end = right;
	//三数取中
	int midindex = GetMidIndex(a, left, right);
	Swap(&a[left], &a[midindex]);
	
	int key = a[left];
	int pivot = left;
	while (begin < end)
	{
		//找小
		while (begin < end && a[end] >= key)
		{
			end--;
		}
		a[pivot] = a[end];
		pivot = end;
		//找大
		while (begin < end && a[begin] <= key)
		{
			begin++;
		}
		a[pivot] = a[begin];
		pivot = begin;
	}
	pivot = begin;
	a[pivot] = key;

	return pivot;
}

即让key取left、right和（left+right）之中的中间值

优化2：小区间排序

在均分下，对一个序列我们要递归logN次，而随着递归层数的增加我们递归调用的空间就越来越多，如图：
在这里插入图片描述
从上图我们可以看出，当需要排列的数足够多时，最后几层递归调用的空间是非常大的，所以在最后的几层小区间（具体大小可以自己定，但一般是十几）排序是我们不采用递归排序，而是直接用插入排序来代替，这样递归调用的空间就会大大减少，效率就提高了。
代码如下：

void QuickSort(int* a, int left,int right)
{
	if (left >= right)
	{
		return;
	}
	int keyindex = PartSort1(a, left, right);
	//int keyindex = PartSort2(a, left, right);
	//int keyindex = PartSort3(a, left, right);
	//小区间优化
	if (keyindex - left-1 > 10)
	{
		QuickSort(a, left, keyindex - 1);
	}
	else
	{
		InsertSort(a + left, keyindex - left);
	}
	if (right - keyindex-1 >10)
	{
		QuickSort(a, keyindex + 1, right);
	}
	else
	{
		InsertSort(a + keyindex + 1, right - keyindex);
	}
}

四、快速排序的时间复杂度及稳定性

快速排序在最坏的情况下时间复杂度为O(N^2)，最好情况下时间复杂度为O(N*logN)，但在引入三数取中后快速排序基本不会出现最坏情况。
快速排序在最好的情况下空间复杂度为O(logN)，最坏为O(N）。
快速排序可能会改变两个相同元素的位置，因此快排不稳定。

GitCode 开源社区

旨在为数千万中国开发者提供一个无缝且高效的云端环境，以支持学习、使用和贡献开源项目。

更多推荐

【目标检测】目标检测的一些常用神经网络模型及方法

我的阶段性总结????文章目录1.概述1.2 目标检测的任务1.3 目标检测的分类2.R-CNN系列2.1 [R-CNN（Region with CNN features）](https://arxiv.org/pdf/1311.2524.pdf)2.2 [Fast R-CNN](https://www.cv-foundation.org/openaccess/content_iccv_2015/