快速排序到底有多快

悠悠 2023-10-12 20:25 3阅读 0赞

> **作者主页：**paper jie的博客\_CSDN博客-C语言,算法详解领域博主
> 
> **本文作者：**大家好，我是paper jie，感谢你阅读本文，欢迎一建三连哦。
> 
> **本文录入于**《算法详解》专栏，本专栏是针对于大学生，编程小白精心打造的。笔者用重金(时间和精力)打造，将算法基础知识一网打尽，希望可以帮到读者们哦。
> 
> **其他专栏：**《系统解析C语言》《C语言》《C语言-语法篇》
> 
> **内容分享：**本期将对八大排序中的快速排序进行详细的讲解，各位看官姥爷快搬好小板凳坐好叭。
> 
>  \-------- 不要998，不要98，只要一键三连，三连买不了吃亏，买不了上当

# 前言 #

在之前的排序中，我们对交换排序中的冒泡排序进行了讲解，带学习的过程中，我们发现一个问题，冒泡排序的速度实在是太慢了，它是两个两个元素进行比较。那有没有比这种排序更快的算法呢？当然是有的，就是今天我们讲的快速排序。

# 什么是快速排序 #

快速排序由C. A. R. Hoare在1962年提出。它的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。快速排序是对冒泡排序的一种改进，大大的提升了排序的速度。

# 快速排序的实现 #

## 基本思想 ##

定义一个中心轴pivot

将小于pivot的元素放在左边

将大于pivot的元素放在右边

将子数组用递归重复上面三步骤

## 具体代码 ##

#include <stdio.h>
    
    void Quick_Sort(int arr[], int l, int r)
    {
    	//如果就子数组就一个元素了，那它本身就是有序的
    	//直接返回
    	if (l >= r)
    		return;
    	int left = l;
    	int right = r;
    	//设置最左边的为基准轴
    	int pivot = arr[left];
    
    	while (left < right)
    	{
    		//从右边开始比较
    		//大于pivot，right就--再比较前一个元素
    		while (left < right && arr[right] > pivot)
    		{
    			right--;
    		}
    		//要是小于基准轴就将它放到left指向的元素
    		//因为这个元素已经比pivot小了，left++跳过它
    		if (left < right)
    		{
    			arr[left] = arr[right];
    			left++;
    		}
    		//再从左边开始比较
    		//小于pivot，left就++
    		while (left < right && arr[left] < pivot)
    		{
    			left++;
    		}
    		//要是大于pivot，就将它放到right指向的元素
    		//再right--，因为这个元素已经知道大于pivot了
    		if (left < right)
    		{
    			arr[right] = arr[left];
    			right--;
    		}
    		//当两个指针重合时，将pivot放入其中
    		//这时比它小的都在左边，比他大的都在右边
    		if (left >= right)
    		{
    			arr[left] = pivot;
    		}
    	}
    	//递归处理左边的子数组
    	Quick_Sort(arr, l, right - 1);
    	//递归处理右边的子数组
    	Quick_Sort(arr, right + 1, r);
    
    }
    int main()
    {
    	int arr[] = { 3,2,5,8,7,1,4,6,0,9 };
    	int l = 0;
    	int sz = sizeof(arr) / sizeof(arr[0]);
    	int r = sz - 1;
    	//快速排序
    	Quick_Sort(arr, l, r);
    	//打印
    	int i = 0;
    	for (i = 0; i < sz; i++)
    	{
    		printf("%d ", arr[i]);
    	}
    	return 0;
    }

## 快速排序实现的原理 ##

排序算法的思想非常简单，在排序的数列中，我们首先要找一个数字作为基准数为了方便，我们一般选择第 1 个数字作为基准数。接下来我们需要把这个待排序的数列中小于基准数的元素移动到待排序的数列的左边，把大于基准数的元素移动到待排序的数列的右边。这时，左右两个分区的元素就相对有序了；接着把两个分区的元素分别按照上面两种方法继续对每个分区找出基准数，然后移动，直到各个分区只有一个数时为止。  
  
**这是典型的分治思想，即分治法。**下面我们代码中的例子进行算法描述，讲解快速排序的排序步骤。  
  
以 3 2 5 8 7 1 4 6 0 9的待排序的数列为例进行排序。首先我们需要在数列中选择一个基准数，我们一般会选择中间的一个数或者头尾的数，这里直接选择第 1 个数 3作为基准数，接着把比 3小的数字移动到左边，把比 3大的数字移动到右边，对于相等的数字不做移动。所以实际上我们需要找到中间的某个位置 k，这样 k 左边的值全部比 k 上的值小，k 右边的值全部比 k 上的值大。  
  
**接下来开始移动元素。怎么移动呢？其实冒泡排序也涉及对元素的移动，但是那样移动起来很累，比如把最后一个元素移动到第 1 个，就需要比较 n-1 次，同时交换 n-1 次，效率很低。其实，只需把第 1 个元素和最后一个元素交换就好了，这种思想是不是在排序时可以借鉴呢？之前说快速排序就是对冒泡排序的一个改进，就是这个原因。**  
  
快速排序的操作是这样的：首先从数列的右边开始往左边找，我们设这个下标为 i，也就是进行减减操作（i--），找到第 1 个比基准数小的值，让它与基准值交换；接着从左边开始往右边找，设这个下标为 j，然后执行加加操作（j++），找到第 1 个比基准数大的值，让它与基准值交换；然后继续寻找，直到 i 与 j 相遇时结束，最后基准值所在的位置即 k 的位置，也就是说 k 左边的值均比 k 上的值小，而 k 右边的值都比 k 上的值大。

这样就是一次比较，后面的子数组重复以上操作，到数组只有一个元素的时候就结束了，因为一个数组它就是有序的。

**画图理解：**

![0c43efc2ab724b4b9e7dfa2b4acd2fd4.png][]

# 快速排序的特点与性能 #

快速排序是在冒泡排序的基础上改进而来的，冒泡排序每次只能交换相邻的两个元素，而快速排序是跳跃式的交换，交换的距离很大，因此总的比较和交换次数少了很多，速度也快了不少。  
但是快速排序在最坏情况下的时间复杂度和冒泡排序一样，是 `O(n2)`，实际上每次比较都需要交换，但是这种情况并不常见。我们可以思考一下如果每次比较都需要交换，那么数列的平均时间复杂度是 `O(nlogn)`，事实上在大多数时候，排序的速度要快于这个平均时间复杂度。**这种算法实际上是一种分治法思想，也就是分而治之，把问题分为一个个的小部分来分别解决，再把结果组合起来。**  
快速排序只是使用数组原本的空间进行排序，所以所占用的空间应该是常量级的，但是由于每次划分之后是递归调用，所以递归调用在运行的过程中会消耗一定的空间，在一般情况下的空间复杂度为 `O(logn)`，在最差的情况下，若每次只完成了一个元素，那么空间复杂度为 `O(n)`。所以我们一般认为快速排序的空间复杂度为 `O(logn)`。  
快速排序是一个不稳定的算法，在经过排序之后，可能会对相同值的元素的相对位置造成改变。  
快速排序基本上被认为是相同数量级的所有排序算法中，平均性能最好的。

--------------------

[0c43efc2ab724b4b9e7dfa2b4acd2fd4.png]: https://img-blog.csdnimg.cn/0c43efc2ab724b4b9e7dfa2b4acd2fd4.png