面试官：手写一个快速排序。
我：懵逼 ，我不会。。

没事，如果你觉得你也不会，没事继续看下去，动手写一写，你也可以轻松解决。

声明：本文以快速排序的升序排序作为分享

一、了解它

1.什么是快速排序？

快速排序（英语：Quicksort），又称分区交换排序（partition-exchange sort），简称快排，一种排序算法，最早由东尼·霍尔提出。在平均状况下，排序{\displaystyle n}n个项目要{\displaystyle \ O(n\log n)}{\displaystyle \ O(n\log n)}（大O符号）次比较。在最坏状况下则需要{\displaystyle O(n^{2})}{\displaystyle O(n^{2})}次比较，但这种状况并不常见。事实上，快速排序{\displaystyle \Theta (n\log n)}{\displaystyle \Theta (n\log n)}通常明显比其他算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地达成。 --来自维基百科

2.为什么要学习它？

因为它快，大家都耳熟能详的冒泡排序，那么冒泡排序和快速排序时间复杂度差多少呢？ 虽然说在最坏的情况下，快速排序和冒泡排序的时间复杂度是相同的，但是啥事也不总是最坏的条件吧，那也太倒霉了，所以综合来说，它还是很快的。

3.快速排序的思想

• 首先建立一个基准数，通常以左边的第一个元素作为基准数。
• 然后准备两个指针（即左指针和右指针），左指针指向第一个元素（即：当前情况下，左指针和基准数重合），右指针指向最后一个元素。

如图：最左边为基准数，左指针在最左侧，右指针在最右侧。

• 然后从基准数的另一次开始（即：当前情况从后指针开始）：用（右）指针指向的元素和基准数进行比较，
  • 如果比基准数小，则停下来
  • 否则（即：大于等于基准数），继续前进，进行比较。

例如：基准数和左指针均未移动，因为31、27、14、都大于等于基准数5，直到4的时候，才小于基准数，所以右指针停到了4这个元素的位置。

• 当基准数另外一侧的（即：右）指针停止后，左指针开始向右移动，用（左）指针和基准数进行比较：

  • 如果左指针比基准数大，就停下来
  • 否则（左指针小于或者等于基准数），则左指针继续移动。
    例如：右指针停止移动，因为2小于于等于基准数5，所以左指针停到了2这个元素的位置。
    

• 如果左指针和右指针都停下来了，那么就需要左指针的数据和右指针的数据进行交换。

例如：此时将左指针的指向的数据元素6和右指针指向的元素4交换位置，结果如下图

此时移动右指针，直到停下，然后继续移动左指针，直到停下，在交换位置，直到左指针和右指针相遇的时候
例如：此时经过多次的交换（交换规则重复上面的），直到左指针和右指针重合，结果如下图

• 此时左指针和右指针相遇，那么就用基准数和左指针（因为左右指针重合，所以也是右指针）交换位置。
  例如：此时交换基准数和左指针（因为左右指针重合，所以也是右指针），结果如下图
  
• 此时的结果为:
  • 基准数左边的都比基准数小或者相等
  • 基准数右边的都比基准数大或者相等
• 那么接下来进行递归操作，将基准数左边的部分作为一个数组，基准数右边的部分作为另一个数组，两个数组分别调用快速排序。
• 基准数左边的和右边的都排序结束以后，继续将排序的结果根据当时的基准数继续递归排序，直到排序完整个数组。

Java代码实现

package com.qz.test;/*** @Description 快速排序* @Author qizhi* @Date: 2020/9/14 16:45* @Version: 1.0**/
public  class QuickSort {private static   int[] array ;public static   int[] qucikSort(int[] arr, int left , int right){array=arr;sort(left , right);return array;}private static void sort(int left ,int right){/*** 判断左指针和右指针的关系* ->如果左指针小于右指针，继续执行* ->如果左指针等于右指针，*/if(left>right){return;}//定义一个变量用来存放基准数int base =array[left];//定义一个左指针int l=left;//定义一个右指针int r=right;//当l和r不相遇的时候，即左指针和右指针并没有相遇while(l!=r){//当右指针比基准数小的时候就停下来,并且左指针要比右指针小(否则，超出索引，无意义)//条件一：反过来说，当右指针比基准数大或者等于基准数的时候，就继续前进//条件二：左指针比右指针小，while(array[r]>=base && l<r) r--;//当左指针比基准数大的时候就停下来,并且左指针要比右指针小(否则，超出索引，无意义)//条件一：反过来说，当左指针比基准数小或者等于基准数的时候，就继续前进//条件二：左指针比右指针小，while(array[l]<=base && l<r) l++;//走到这里其实有两种情况//1.左指针和右指针分别被条件限制，不能前进，需要交换位置//2.左指针和右指针重复。//如果走到这里：//就证明左指针和右指针都停止了下来，那么就需要交换元素的位置.int temp=array[l];array[l]=array[r];array[r]=temp;}//走到这里，证明左指针和右指针重合，那么需要交换基准数和左（右）指针上的元素//因为左指针和右指针重合，所以左指针和右指针的元素是同一个。array[left]=array[l];array[l]=base;/*** 此时基准数已经和左（右）指针交换位置（此时的基准数在中间），此时数组的现状是：* ->基准数左边的元素都小于等于基准数* ->基准数右边的元素都大于等于基准数* 分别将基准数两侧的数组，堪称两个元素，分别在进行快速排序。*/sort(left,l-1);sort(l+1,right);}}

package com.qz.test;import org.junit.Test;
import java.util.*;
import java.util.function.Consumer;/*** @Description* @Author qizhi* @Date: 2020/6/18 8:18* @Version: 1.0**/
public class MyTest {@Testpublic void test(){int [] array=new int [] {1,9,3,2,5,4,12,634,987};System.out.println("*********************排序前");forList(array);System.out.println();System.out.println("*********************排序后");int[] test = QuickSort.qucikSort(array, 0, array.length - 1);forList(test);}private void forList(int [] array){for(int i : array){System.out.print(i+"  ");}}
}

运行结果：

感谢你的阅读，如果有问题，或者有其他想法，欢迎留言。。。。