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

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

引言:

快速排序和归并排序是面试当中常常被问到的两种排序算法,在研究过数据结构所有的排序算法后,个人认为最复杂的当属快速排序。从代码量上来看,快速排序并不多,我之所以认为快排难以掌握是因为快排是一种递归算法,同时终止条件较多。如果你刚刚把快排的思路整理过一遍可能觉得不难,然而一个月之后呢?

面试要求的是临场发挥,如果不是烂熟于心,基本就卡壳了。在面试官眼里,你和那些完全不懂快速排序算法的菜逼是一样的,也许实际上你可能私底下已经理解很多遍了,然而并没卵。所以当下问题就是,如何将快排烂熟于心?我觉得记忆一个算法应当在理解的基础上,当你心里面把所有终止和判断条件都一清二楚之后,手写快排就不是件难事了。

源代码:

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 21 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才会继续移动下去!左边的数应当是小于或等于基准元素,右边的数应当是大于等于基准元素的值才对!!!!


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


相关文章
|
机器学习/深度学习 算法 搜索推荐
八大排序(二)--------冒泡排序
八大排序(二)--------冒泡排序
40 1
十大排序引出的问题()
十大排序引出的问题()
40 0
|
7月前
|
算法
【六大排序详解】终篇 :冒泡排序 与 快速排序
冒泡排序如同泡泡上升一样,逐个逐个向上冒,一个接一个的冒上去。两两比较,较大者(较小者)向后挪动。全部遍历一遍即可完成排序
49 2
|
7月前
|
搜索推荐 测试技术
【六大排序详解】开篇 :插入排序 与 希尔排序
排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。 排序存在稳定性,稳定性是评估排序的重要标准。
56 1
|
7月前
|
存储 搜索推荐 算法
十大基础排序算法
十大基础排序算法
|
7月前
|
搜索推荐 算法
拒绝水文!八大排序(二)【适合初学者】冒泡排序和选择排序
拒绝水文!八大排序(二)【适合初学者】冒泡排序和选择排序
|
7月前
|
算法
【十大排序】深入浅出冒泡排序
【十大排序】深入浅出冒泡排序
|
7月前
|
搜索推荐 算法
【十大排序】带你深入了解归并排序
【十大排序】带你深入了解归并排序
八大排序——快速排序
八大排序——快速排序
|
存储 移动开发 算法
十大排序算法
十大排序算法
138 0