快速排序（详解）

Dear 丶 2024-03-24 14:10 30阅读 0赞

#### 快排 ####

*  一.朴素版
 *   *  1.一层循环
     *  2.递归
 *  二.改进(选取key值)
 *   *  1.随机数取法
     *  2.三路取中
     *  3.前后指针法
 *  三，小区间（减少递归）
 *  四.非递归

## 一.朴素版 ##

### 1.一层循环 ###

![在这里插入图片描述][8e81940526624e87a3903db68d8a2d6c.png]

> **快排的每一层循环就是选出一个key值将其放到正确的位置（也就是放到已经完全有序时的位置）。**

![在这里插入图片描述][251f5b98c4e84500bd497b470d041b23.png]

> **例如以上有一组数据，我们选择6为key值，这次循环我们要将6放到正确的位置。用一个left指针和一个right指针，分别指向左右两端，left指针向右走，遇到大于key值的数就停下，然后right指针向左走，遇到小于key值的数就停下。之后两指针所对应的数交换位置，直到两指针相遇，交换left所指向的数和key值，一次循环停止。就得到key数左边的数都小于等于key，右边的数都大于等于key。**

![在这里插入图片描述][e8ea8913976e48ba9f1790d85e2b7941.png]

> **此时一次循环结束6左边的数都小于等于6，右边的数都大于等于6。（一般令最左边的数为key值）**

![在这里插入图片描述][40414144cc5e410995930424e5f20936.png]

### 2.递归 ###

> **每次循环找到一个数，那么依次递归当left>=right,也就是这次递归里已经没有元素时就说明排序完成。**

void Swap(int* a, int* b)
    {
        
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    void QuickSort(int* a, int left, int right)
    {
        
    	if (left >= right)
    		return;
    	int begin = left, end = right;
    	int key = left;
    	while (right > left)
    	{
        
    		while (left<right&&a[right] >= a[key])
    			right--;
    		while (left<right&&a[left] <= a[key])
    			left++;
    		Swap(&a[left], &a[right]);
    	}
    	Swap(&a[left], &a[key]);
    	key = left;
    	QuickSort(a, begin,key-1);
    	QuickSort(a, key + 1, end);
    }

## 二.改进(选取key值) ##

*缺陷*

> **如果改数据已经是升序或者逆序的话，我们每次选最左边为key值，那么每次递归只能减少一个数（无法做到理想情况下的二分）。如果有100w个数，就容易造成栈溢出，所以需要改进。**

### 1.随机数取法 ###

> **其实快排的缺陷主要是由key值的选取造成的，那么我们可以随机选key值，就可以避免最坏的情况。**

![在这里插入图片描述][3af4ecd1fce946f8b34f7c000788b881.png]

### 2.三路取中 ###

> **选随机数是可行的，但有人认为太过于不确定了，所以又出炉了一个新方法，取中间（max>a\[mid\]>min）的坐标。**

![在这里插入图片描述][65b3463102b0477594b63878c918600a.png]

![在这里插入图片描述][55e0beacd1cf40989e65b890a8923cda.png]

### 3.前后指针法 ###

> **简单来说就是一个cur指针从最左边走起，pre初始位置在cur+1位置，pre向后走，如果a\[pre\]<a\[key\],就交换a\[++cur\]和a\[pre\]，直到pre走到最右边。**

![在这里插入图片描述][2e2a41e981db445ab4b8df9135b42999.png]

![在这里插入图片描述][2193e2c7e7b84754bff53805d8f7d4f9.png]

*源代码*

#include<stdio.h>
    #include<time.h>
    #include<stdlib.h>
    
    void Swap(int* a, int* b)
    {
        
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    int GetMid(int* a, int left, int right)
    {
        
    	int mid = (left + right) / 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 left;
    		else
    			return right;
    	}
    }
    
    void QuickSort(int* a, int left, int right)
    {
        
    	if (left >= right)
    		return;
    
    	//int begin = left, end = right;
    
    	//随机选key
    	//int randi =left+ rand() % (right - left);//让产生的随机数在left和right之间
    	//Swap(&a[randi], &a[left]);//为了避免扰乱后面的排序，我们将其调到最左边的位置
    
    	//三数取中
    	int mid = GetMid(a, left, right);
    	Swap(&a[mid], &a[left]);
    
    	/*int key = left;
    	while (right > left)
    	{
    		while (left<right&&a[right] >= a[key])
    			right--;
    		while (left<right&&a[left] <= a[key])
    			left++;
    		Swap(&a[left], &a[right]);
    	}
    	Swap(&a[left], &a[key]);
    	key = left;
    	QuickSort(a, begin,key-1);
    	QuickSort(a, key + 1, end);*/
    	
    	//前后指针法
    	int cur = left, pre = cur + 1,key=left;
    	while (pre<=right)
    	{
        
    		if (a[pre] < a[key])
    		{
        
    			cur++;
    			Swap(&a[pre], &a[cur]);
    		}
    		pre++;
    	}
    	Swap(&a[cur], &a[key]);
    	key = cur;
    	QuickSort(a, left, key-1);
    	QuickSort(a, key + 1, right);
    }
    int main()
    {
        
    	int a[20000];
    	srand((unsigned int)time(NULL));
    	for (int i = 0; i < 20000; i++)
    	{
        
    		a[i] = rand() % 1000;
    	}
    	QuickSort(a,0,19999);
    	int st = 0;
    	for (int i = 0; i < 19998; i++)
    	{
        
    		if (a[i] > a[i + 1])
    		{
        
    			printf("%d->%d,%d\n", a[i], a[i + 1], i);
    			st = 1;
    			break;
    		}
    	}
    	if (st)
    	{
        
    		printf("out of order");
    	}
    	else
    	{
        
    		printf("order");
    	}
    }

## 三，小区间（减少递归） ##

> **我们知道快排是按二叉树形式排列的，而在理想情况下，最后一层递归就占总递归的二分之一。实际上当每个子树只剩下10个数时，我们就可以考虑不再递归改用插入排序，那么这样（在理想情况下）就可以去除最后三层递归，也就会减少87.5%的递归。**

![在这里插入图片描述][baaf3d80549f48d4a39f0d7e3a366152.png]

> **不了解插入排序的可以看看这篇博客[插入排序][Link 1]**

![在这里插入图片描述][fba7e4ffa61545da8c0b267dcd543403.png]

#include<stdio.h>
    #include<time.h>
    #include<stdlib.h>
    
    void Swap(int* a, int* b)
    {
        
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    int GetMid(int* a, int left, int right)
    {
        
    	int mid = (left + right) / 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 left;
    		else
    			return right;
    	}
    }
    
    void QuickSort(int* a, int left, int right)
    {
        
    	if (left >= right)
    		return;
    
    	//int begin = left, end = right;
    
    	//随机选key
    	//int randi =left+ rand() % (right - left);//让产生的随机数在left和right之间
    	//Swap(&a[randi], &a[left]);//为了避免扰乱后面的排序，我们将其调到最左边的位置
    
    	//三数取中
    	int mid = GetMid(a, left, right);
    	Swap(&a[mid], &a[left]);
    
    	/*int key = left;
    	while (right > left)
    	{
    		while (left<right&&a[right] >= a[key])
    			right--;
    		while (left<right&&a[left] <= a[key])
    			left++;
    		Swap(&a[left], &a[right]);
    	}
    	Swap(&a[left], &a[key]);
    	key = left;
    	QuickSort(a, begin,key-1);
    	QuickSort(a, key + 1, end);*/
    
    	//前后指针法
    	if (right - left + 1 > 10)
    	{
        
    		int cur = left, pre = cur + 1, key = left;
    		while (pre <= right)
    		{
        
    			if (a[pre] < a[key])
    			{
        
    				cur++;
    				Swap(&a[pre], &a[cur]);
    			}
    			pre++;
    		}
    		Swap(&a[cur], &a[key]);
    		key = cur;
    		QuickSort(a, left, key - 1);
    		QuickSort(a, key + 1, right);
    	}
    	else//插入排序
    	{
        
    		for (int i = 1; i < 10; i++)
    		{
        
    			int end = i - 1;
    			int tmp = a[i];
    			while (end >= 0)
    			{
        
    				if (a[end] > tmp)
    				{
        
    					a[end + 1] = a[end];
    					end--;
    				}
    				else
    				{
        
    					break;
    				}
    			}
    			a[end + 1] = tmp;
    		}
    	}
    }
    int main()
    {
        
    	int a[20000];
    	srand((unsigned int)time(NULL));
    	for (int i = 0; i < 20000; i++)
    	{
        
    		a[i] = rand() % 1000;
    	}
    	QuickSort(a,0,19999);
    	int st = 0;
    	for (int i = 0; i < 19998; i++)
    	{
        
    		if (a[i] > a[i + 1])
    		{
        
    			printf("%d->%d,%d\n", a[i], a[i + 1], i);
    			st = 1;
    			break;
    		}
    	}
    	if (st)
    	{
        
    		printf("out of order");
    	}
    	else
    	{
        
    		printf("order");
    	}
    }

## 四.非递归 ##

> **使用栈先进后出来模拟实现深度优先遍历。如果不了解栈可以看看这篇博客[栈][Link 2]**

![在这里插入图片描述][5077b6ffbe3a44658912082043d9c234.png]

#include"stack.h"
    
    
    #include<stdio.h>
    #include<time.h>
    #include<stdlib.h>
    
    void Swap(int* a, int* b)
    {
        
    	int tmp = *a;
    	*a = *b;
    	*b = tmp;
    }
    
    int GetMid(int* a, int left, int right)
    {
        
    	int mid = (left + right) / 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 left;
    		else
    			return right;
    	}
    }
    
    int PartSort(int* a, int left, int right)
    {
        
    	// 三数取中
    	int midi = GetMid(a, left, right);
    	if (midi != left)
    		Swap(&a[midi], &a[left]);
    
    	int keyi = left;
    
    	int prev = left;
    	int cur = left + 1;
    	while (cur <= right)
    	{
        
    		if (a[cur] < a[keyi] && ++prev != cur)
    			Swap(&a[cur], &a[prev]);
    
    		++cur;
    	}
    
    	Swap(&a[prev], &a[keyi]);
    	keyi = prev;
    
    	return keyi;
    }
    
    void QuickSort(int* a, int left, int right)
    {
        
    	ST st;
    	STInit(&st);
    	STPush(&st, right);
    	STPush(&st, left);
    
    	while (!STEmpty(&st))
    	{
        
    		int begin = STTop(&st);
    		STPop(&st);
    		int end = STTop(&st);
    		STPop(&st);
    
    		int keyi = PartSort(a, begin, end);
    		// [begin,keyi-1] keyi [keyi+1, end]
    		if (keyi + 1 < end)
    		{
        
    			STPush(&st, end);
    			STPush(&st, keyi + 1);
    		}
    
    		if (begin < keyi - 1)
    		{
        
    			STPush(&st, keyi - 1);
    			STPush(&st, begin);
    		}
    	}
    
    	STDestroy(&st);
    }
    int main()
    {
        
    	/*int a[11] = {3,3,8,7,6,5,4,3,2,1,0};
    	QuickSort(a, 0, 10);
    	for (int i = 0; i < 10; i++) printf("%d ", a[i]);*/
    	int a[200000];
    	srand((unsigned int)time(NULL));
    	for (int i = 0; i < 200000; i++)
    	{
        
    		a[i] = rand() % 1000;
    	}
    	QuickSort(a, 0, 199999);
    	int st = 0;
    	for (int i = 0; i < 199998; i++)
    	{
        
    		if (a[i] > a[i + 1])
    		{
        
    			printf("%d->%d,%d\n", a[i], a[i + 1], i);
    			st = 1;
    			break;
    		}
    	}
    	if (st)
    	{
        
    		printf("out of order");
    	}
    	else
    	{
        
    		printf("order");
    	}
    }

[8e81940526624e87a3903db68d8a2d6c.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/6ac36548d4c94ceaa03d8e3f92b4b206.png
[251f5b98c4e84500bd497b470d041b23.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/2dbe2d8a19f242268cce618defdfc697.png
[e8ea8913976e48ba9f1790d85e2b7941.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/213743413cf64a5397506d2e29464be0.png
[40414144cc5e410995930424e5f20936.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/82fb167c2755447e990a1e3dcc6634fe.png
[3af4ecd1fce946f8b34f7c000788b881.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/058a08270e7c402fbba2ab8ffb1e34cf.png
[65b3463102b0477594b63878c918600a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/74eab9a325144041999ea23ec6a2d0fa.png
[55e0beacd1cf40989e65b890a8923cda.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/25e6763ea4a34abb9a6f174a8ab0142f.png
[2e2a41e981db445ab4b8df9135b42999.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/5e6f68e5d97b42c4bd0039c4291a4295.png
[2193e2c7e7b84754bff53805d8f7d4f9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/8de850588a4c4cbaa2ccee6f81e02b5b.png
[baaf3d80549f48d4a39f0d7e3a366152.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/a12793f49e724ba0ad3862590c506d10.png
[Link 1]: http://t.csdn.cn/Gc99F
[fba7e4ffa61545da8c0b267dcd543403.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/478e204d7ae84cf1818f1f1f0773e31d.png
[Link 2]: http://t.csdn.cn/0CiMS
[5077b6ffbe3a44658912082043d9c234.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/ba59302746a04980b01a15919c55e455.png