【十大排序】带你深入分析快速排序

小鱼儿 2023-03-01 09:47 11阅读 0赞

> ☞梦想进大厂的一只程序猿☜
> 
> ☞期望毕业前力扣刷够400题☜
> 
> ☞正在复习数据结构和算法☜
> 
> ☞博客地址：[https://www.huangliangshuai.com/][https_www.huangliangshuai.com]☜

## [【2020秋招-面试题目汇总（随时更新）】][2020_-] ##

## 引言： ##

> 快速排序和归并排序是面试当中常常被问到的两种排序算法，在研究过数据结构所有的排序算法后，个人认为最复杂的当属快速排序。从代码量上来看，快速排序并不多，我之所以认为快排难以掌握是因为快排是一种递归算法，同时终止条件较多。如果你刚刚把快排的思路整理过一遍可能觉得不难，然而一个月之后呢？
> 
> 面试要求的是临场发挥，如果不是烂熟于心，基本就卡壳了。在面试官眼里，你和那些完全不懂快速排序算法的菜逼是一样的，也许实际上你可能私底下已经理解很多遍了，然而并没卵。所以当下问题就是，如何将快排烂熟于心？我觉得记忆一个算法应当在理解的基础上，当你心里面把所有终止和判断条件都一清二楚之后，手写快排就不是件难事了。

## 源代码： ##

public static void main(String[] args) {
    		int[] nums = new int[] { 2, 1, 3, 5, 0 };
    		QuickSort(nums, 0, nums.length - 1);
    		for (int i : nums) {
    			System.out.println(i);
    		}
    	}
    
    	static void QuickSort(int[] nums, int start, int end) {
    		if (start >= end) {
    			return;
    		}
    		int i = start;
    		int j = end;
    		int key = nums[i];
    		while (i < j) {
    			while (i < j && nums[j] >= key) {
    				j--;
    			}
    			nums[i] = nums[j];
    			while (i < j && nums[i] <= key) {
    				i++;
    			}
    			nums[j] = nums[i];
    		}
    		nums[i] = key;
    		QuickSort(nums, start, i - 1);
    		QuickSort(nums, i + 1, end);
    	}

## 思路整理： ##

我想，对于大多数学过数据结构的人来说，上面代码的大体思路应该是没有什么问题的，如果有问题那你是不是要好好考虑下重学一遍数据结构了。

这里我从几个判定条件入手来捋一捋算法思路：

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

### 判定条件1 while (i < j && nums\[j\] >= key)  中的 i < j ###

来看这个例子，假设我们要对 4 2 1 6 进行排序，即待排序数组 nums= \{4,2,1,6\}； 快速排序的步骤大体是这样的：

4 2 1 6 | 4 ----> 4 2 1 6 | 4 ----> 1 2 1 6 | 4 ----> 1 2 1 6 | 4 ----> 1 2 1 6 | 4 ----> 1 2 4 6 | 4（跳出循环，nums\[i\] = temp; ）

在这里，我们用蓝色代表**i**指向的元素，红色代表**j**指向的元素，橙色红色代码low和high相遇了，即 i == j，而|号后边的数字4代码选取的基准元素（默认是数组第一个数字）。

**所以，在移动low和high的过程中，终止条件就是low==high，即他们相遇了，如果我们使用i <= j 的话，我们的i指针将会指向6的位置，然后变成4，造成数据的错乱。**

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

## 判定条件2 while(i < j )\{\} ##

条件1中说了，i 和 j 不能相遇。但是为什么外面还要设置一层循环呢？咱们再看一个例子：

4 2 5 7 2 3 1 6 | 4 ----> 4 2 5 7 2 3 1 6 | 4 ----> 1 2 5 7 2 3 1 6 | 4 ----> 1 2 5 7 2 3 1 6 | 4 ----> 1 2 5 7 2 3 1 6 | 4 ----> 1 2 5 7 2 3 5 6 | 4

到这里，读者可以考虑一下如果没有外面这层while循环，下一步干嘛？没错，会这样执行1 2 4 7 2 3 5 6 | 4，但是这个数组还没有遍历完啊! 并且说好的4左边的全部比4小，4右边的全部比4大的呢？

**因此，如果low和high没有相遇，就应该让它们一直遍历下去！**

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

### 判定条件3 while (i < j && nums\[j\] >= key) 中的 nums\[j\] >= key ###

有没有想过为什么是 >= 呢？ 如果换成 > 会是什么结果？ 我可以明确的告诉你，把等号去掉就会死循环了！是不是倒吸一口凉气？我想，任何一个程序员应该都不敢轻视任意一个边界条件，所以即便是一个等号也要认真考半天，为什么要等号，可以不可以去掉？我们继续上个例子：

1 2 1 1 3 -5 0 | 1 ----> 0 2 1 1 3 -5 0 | 1 ----> 0 2 1 1 3 -5 2 | 1 ----> 0 2 1 1 3 \-5 2 | 1 ----> 0 \-5 1 1 3 \-5 2 | 1 ----> 0 -5 1 1 3 \-5 2 | 1 ----> 0 -5 1 1 3 1 2 | 1，好了，到了这里读者再往后推算几步，看看有什么发现？是不是一直在做反复赋值的死循环？

因为从 i < j一直满足， 而 nus\[j\] > key 和 nums\[i\] < key 一直都不满足，所以i 和 j 一直都不会移动了，所以自然就死循环了！

**这个时候，只有把>和<修改成>=和<=，low和high才会继续移动下去！左边的数应当是小于或等于基准元素，右边的数应当是大于等于基准元素的值才对！！！！**

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

###  ###

**好了，整个快排梳理就到这儿了，通过反复梳理记忆，快排一定会烂熟于心！**

[https_www.huangliangshuai.com]: https://www.huangliangshuai.com/
[2020_-]: https://blog.csdn.net/qq_40915439/article/details/107908926