快速排序——各种方法图文详解，从入门到精通

时间复杂度：O(N*logN)空间复杂度：O(logN)(因为需要不断的开栈，二分划分区间不断向下开空间)稳定性：不稳定.t=P9T8t=P9T8栈的相关知识https://blog.csdn.net/2401_88240248/article/details/151156635?堆的相关知识https://blog.csdn.net/2401_88240248/article/details/1

努力的小张.

1302人浏览 · 2025-11-19 21:32:06

努力的小张. · 2025-11-19 21:32:06 发布

快速排序介绍：

快速排序是一种非常常用的排序方法，它在1962由C. A. R. Hoare（霍尔）提的一种二叉树结构的交换排序方法，故因此它又被称为霍尔划分，它基于分治的思想，所以整体思路是递归进行的。

基本思想：

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

基本思路：

先在待排的数中找到一个key值，一般key值在数组第一个数（后续优化过程中，会将待排数的第一个数，中间的数，以及最后一个数进行比较，取中间大的数做key值）.
确定key后，经过操作将key放在其合适位置，即其左边的数都比key小，右边数都比key大，但左边或右边的数并不一定有序，随后在由递归思想将其，key左边以及右边部分分别进行递归处理，最后直到待排区间不存在或只有一个元素时返回.

递归版本

一.hoare版本

为什么先走right，而不是先走left?

这是因为当先走left时，最后在两者相遇前交换了一次数据，此时right指向的值大于key，left往后走与right相遇，key与right交换，此时一个大于key的值便交换到左边，因此不能先走left，当走right时，两者相遇的数一定是比key小或等于key.

步骤展示：

下图是对其进行的详细分析讲解

代码：

void Quicksort(int* a, int left,int right)
{
	if (left >= right)
	{
		return;
	}//n=1时即为left=right，当n<0，left>right
	int Pleft = left;
	int Pright = right;
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right]>=a[keyi])
		{
			right--;
		}
		while (left < right && a[left]<=a[keyi])
		{
			left++;
		}
		swap(&a[left], &a[right]);
	}
	swap(&a[keyi], &a[left]);
	Quicksort(a, Pleft, left - 1);
	Quicksort(a, left + 1, Pright);
}

二.挖坑法

步骤展示：

代码：

void QuickSort(int* a, int left, int right)
{
	if (left >= right)
	{
		return;
	}
	int Pleft = left;
	int Pright = right;
	int key = a[left];
	while (right > left)
	{
		while (right > left && a[right] >= key)
		{
			right--;
		}
		a[left] = a[right];
		while (right > left && a[left] <= key)
		{
			left++;
		}
		a[right] = a[left];
	}
	a[left] = key;
	QuickSort(a,Pleft,left-1);
	QuickSort(a,left+1,Pright);
}

三.前后指针法

虽然名字较指针法，但在实际上并没有运用到指针

步骤展示：

int a[] = { 6,1,2,7,9,3,4,5,10,8 };//依旧以该数组为例

pre默认为left，cur默认为pre+1

代码：

int PartQsort3(int* a, int left, int right)
{
	int keyi = left;
	int pre = left;
	int cur = pre + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++pre != cur)
		{
			swap(&a[cur], &a[pre]);
		}
		cur++;
	}
	swap(&a[pre], &a[keyi]);
	return pre;
}
void QuickSort3(int* a, int left, int right)
{

	int keyi = PartQsort3(a,left,right);
	QuickSort2(a, left, keyi - 1);
	QuickSort2(a, keyi+1, right);
}

非递归版本

前置知识

代码：

void swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

int Partsort(int *a,int left,int right)
{
	if (left >= right)
	{
		return -1;
	}
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right] >= a[keyi])
		{
			right--;
		}
		while (left < right && a[left] <= a[keyi])
		{
			left++;
		}
		swap(&a[left], &a[right]);
	}
	swap(&a[keyi], &a[left]);
	return left;
}//这里采用的hoare版本的快排

void Qucicksort(int *a,int n)
{
	ST st1;
	STInit(&st1);
	STPush(&st1, n - 1);//先压right
	STPush(&st1,0);//在压left
	while (!STempty(&st1))
	{
		int begin = STTop(&st1);
		STPop(&st1);
		int end= STTop(&st1);
		STPop(&st1);
		int keyi = Partsort(a,begin,end);
		if (keyi != -1)
		{    //压右区间
			STPush(&st1, end);
			STPush(&st1, keyi + 1);
            //压左区间
			STPush(&st1, keyi - 1);
			STPush(&st1, begin);
		}
	}
}

下方是栈中的代码

#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
//用顺序表实现栈
typedef int STtype;
typedef struct Stack {
	STtype* a;
	int top;
	int capacity;
}ST;

//初始化与销毁
void STInit(ST* p);
void STDestory(ST*p);
//压栈  出栈
void STPush(ST* p,STtype x);
void STPop(ST* p);
//获取栈顶元素
STtype STTop(ST* p);
//获取栈中元素个数
int STSize(ST* p);
//判断栈是否为空
bool STempty(ST* p);

void STInit(ST* p)
{
	assert(p);
	p->a = NULL;
	p->capacity = p->top = 0;
}

//压栈
void STPush(ST* p, STtype x)
{
	assert(p);
	if (p->top == p->capacity)
	{
		int newcapcity = p->capacity == 0 ? 4 : p->capacity * 2;
		STtype* temp = (STtype*)realloc(p->a, newcapcity*sizeof(STtype));
		if(temp==NULL)
		{
			perror("realloc fail");
			exit(1);
		}
		p->a = temp;
		p->capacity = newcapcity;
	}
	p->a[p->top] = x;
	p->top++;
}
//出栈
void STPop(ST* p)
{
	assert(p);
	assert(p->top > 0);
	p->top--;
}
//获取栈顶元素
STtype STTop(ST* p)
{
	assert(p);
	assert(p->top);
	return p->a[p->top - 1];
}
//获取栈中元素个数
int STSize(ST* p)
{
	assert(p);
	return p->top;
}
//判断栈是否为空
bool STempty(ST* p)
{
	assert(p);
	return p->top == 0;
}
void STDestory(ST* p)
{
	assert(p);
	free(p->a);
	p->a = NULL;
	p->capacity = p->top = 0;
}

快排的相关优化:

1.三数取中

在确定key值时，我们总会面临如果key的值最小，那么right向一直向前遍历如下数,或最大，left一直后遍历，都会使速率变慢，最后甚至退化到O(N^2),

因此出现了三数取中，使成为key的数即不是最大也不是最小，这样就可以避免了这种局面

三数的取值分别为数组最左边的数，最右边的数，以及中间的数，比较这三个数找到第二大的数，将其位置与left交换,因此其也不会改变left做key值

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

2.小区间优化

小区间优化主要运用到了插入排序

将上图每一个圈看成递归所开辟的空间，越到下面区间越小，且开辟的空间越多，因此当我们如果当区间数到达一定数后，不在进行快排而是进行其他类较快处理几个数的排序，那么不仅节省空间，速度也没有较大的影响.

因此小区间优化所选择的为插入排序

下方代码是在hoare基础上加入小区间优化

void swap(int* str1, int* str2)
{
	int  temp = *str1;
	*str1 = *str2;
	*str2 = temp;
}
void InsertSort(int* arr, int n)
{
	for (int i = 0;i < n-1;i++)
	{
		int end=i;
		int temp = arr[end + 1];
		while (end>=0&&arr[end] > temp)
		{
			arr[end + 1] = arr[end];
			end--;
		}
		arr[end+1] = temp;
	}
}
void Quicksort(int* a, int left,int right)
{
	if (left >= right)
	{
		return;
	}//n=1时即为left=right，当n<0，left>right

///////////////添加部分//////////////////////////////
	if (right - left + 1 < 10)
	{
		InsertSort(a + left,right-left+1);
	}
///////////////////////////////////////////////////
	int Pleft = left;
	int Pright = right;
	int keyi = left;
	while (left < right)
	{
		while (left < right && a[right]>=a[keyi])
		{
			right--;
		}
		while (left < right && a[left]<=a[keyi])
		{
			left++;
		}
		swap(&a[left], &a[right]);
	}
	swap(&a[keyi], &a[left]);
	Quicksort(a, Pleft, left - 1);
	Quicksort(a, left + 1, Pright);
}

3.自省排序

在一些特别极端的情况下，例如，左区间一个数，右区间几百万个数，这样最后会由于递归的层次过于深，导致递归会遇见一个常见的问题即为栈溢出

那么如何处理该问题呢，那就是这里所说的自省排序，当深度到达一定程度后结束继续递归的排序，进行堆排序，来避免出现堆溢出的情况

一般将最大深度设为标准深度（即每次都是在区间中间分步）的二倍，如下图

对于深度如何求，即可以参照二叉数的深度计算，当左右均匀分步时，其类似于二叉数，因此深度为logN

代码：

void AdjustDown(int* a, int n, int paraent)
{
	int child = paraent * 2 + 1;
	while (child < n)
	{
		if (child+1<n&&a[child] < a[child + 1])
		{
			child = child + 1;
		}

		if (a[child] > a[paraent])
		{
			swap(&a[child], &a[paraent]);
			paraent = child;
			child = paraent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
void HeapSort(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2;i >= 0;i--)
	{
		AdjustDown(a, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
	}
}

void InsertSort(int* arr, int n)
{
	for (int i = 0;i < n-1;i++)
	{
		int end=i;
		int temp = arr[end + 1];
		while (end>=0&&arr[end] > temp)
		{
			arr[end + 1] = arr[end];
			end--;
		}
		arr[end+1] = temp;
	}
}
int PartQsort(int* a, int left, int right)
{
	int ret = FindMidi(a, left, right);
	swap(&a[ret], &a[left]);
	int keyi = left;
	int pre = left;
	int cur = pre + 1;
	while (cur <= right)
	{
		if (a[cur] < a[keyi] && ++pre != cur)
		{
			swap(&a[cur], &a[pre]);
		}
		cur++;
	}
	swap(&a[pre], &a[keyi]);
	return pre;
}


void _QuickSort(int* a, int left, int  right, int depth, int curdep)
{
	int N = right - left + 1;//总数
	if (N < 16)
	{
		InsertSort(a + left, N);
		return;
	} 

/////////////////核心////////////////////////////////////
	if (curdep > depth)
	{
		HeapSort(a+left, N);
	}
//////////////////////////////////////////////////////////
	
else
	{
		int keyi = PartQsort(a, left, right);
		_QuickSort(a, left, keyi - 1, depth, curdep+1);
		_QuickSort(a, keyi+1,right, depth, curdep+1);
	}
}

void QuickSort(int* a, int left, int right)//自省排序
{
	int N = right - left + 1;//总数
	int curdep=0;
	int depth = 0;
	for (int i = 1;i <= N;i*=2)
	{
		depth++;
	}
	_QuickSort(a,left,right,depth*2,curdep+1);
}

4.三路划分（不常用）

当一个快排有了自省机制后，基本上不会用到三路划分，三路划分与前方几种优化机制不同，其主要是对单次遍历进行改变

主要在遇到重复数比较多时，利用三路划分可以避免出现栈溢出的现象，但是有了自省则可避免栈溢出，此外三路划分频繁的交换也增添了消耗.

代码

void swap(int* str1, int* str2)
{
	int  temp = *str1;
	*str1 = *str2;
	*str2 = temp;
}
void ThreeQuicksort(int *a,int left ,int right)
{
	if (left >= right)
	{
		return;
	}
	int Pleft = left;
	int Pright = right;
	int key = a[left];
	int cur = left + 1;
	while (cur <= right)
	{
		if (a[cur] < key)
		{
			swap(&a[left], &a[cur]);
			++left;
			++cur;
		}
		else if (a[cur] == key)
		{
			++cur;
		}
		else
		{
			swap(&a[right], &a[cur]);
			right--;
		}
	}
	ThreeQuicksort(a,Pleft,left-1);
	ThreeQuicksort(a,right+1,Pright);
}