快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，因此很多软件公司的笔试面试，包括像BAT、字节、美团等知名IT公司都喜欢考查快速排序原理和手写源码。

一、概念

快速排序，顾名思义就是一种以效率快为特色的排序算法，快速排序（Quicksort）是对冒泡排序的一种改进。由英国计算机专家:托尼·霍尔（Tony Hoare）在1960年提出。

二、基本思想

从排序数组中找出一个数，可以随机取，也可以取固定位置，一般是取第一个或最后一个，称为基准数。然后将比基准小的排在左边，比基准大的放到右边；

如何放置呢，就是和基准数进行交换，交换完左边都是比基准小的，右边都是比较基准大的，这样就将一个数组分成了两个子数组，然后再按照同样的方法把子数组再分成更小的子数组，直到不能分解（子数组只有一个值）为止。以此达到整个数据变成有序序列。

快速排序采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)，现在各种语言中自带的排序库很多使用的都是快速排序。

空间复杂度

快速排序是一种原地排序，只需要一个很小的栈作为辅助空间，空间复杂度为O(log2n)，所以适合在数据集比较大的时候使用。

时间复杂度

时间复杂度比较复杂，最好的情况是O(n)，最差的情况是O(n2)，所以平时说的O(nlogn)，为其平均时间复杂度。

O(n)：理想的情况，每次划分所选择的中间数恰好将当前序列几乎等分，经过log2n趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlog2n)。O(n2)：最坏的情况，每次所选的中间数是当前序列中的最大或最小元素，这使得每次划分所得的子表中一个为空表，另一子表的长度为原表的长度-1。这样，长度为n的数据表的快速排序需要经过n趟划分，使得整个排序算法的时间复杂度为O(n2)。三、算法步骤

1.选定一个基准数（一般取第一位数字）作为中心点（Pivot）；2.将大于Pivot的数字放到Pivot的左边；3.将小于Pivot的数字放到Pivot的右边；4.第一次排序结束后，分别对左右子序列继续递归重复前三步操作。

四、具体示例

实例数组：arr[] = {19，97，9，17，1，8}；

1.取出基准数Pivot，以该值为中心轴。

快速排序中的规则：右边有坑，就从左边Arr[L + n]取值来填，反之左边有坑，则从右边Arr[R - n]取值来填；

2.从左边取的基准值，左边的Arr[L]就空出来了，则先从右侧取值来填，从最右侧下标开始，在Arr[R] 取到第一个值“8”；

3.将取到的Arr[R]与基准值比较，发现小于基准值，则插入到Arr[R]，占到了基准值Pivot的位置上。

4.然后从Arr[L+1]的位置取出值，继续向右匹配并排序，将匹配到的值（匹配规则如下）插入到右侧Arr[R]的空位置上；

匹配规则：大于基准值的插入到Arr[R]，如果小于，则直接忽略并跳过，继续向右取值，直到坐标L和坐标R重合。

5.发现取出的值大于Pivot（基准值），则将其插入到Arr[R]。

6.左边有坑，从右边Arr[R-1]继续匹配，Arr[R-1] = 1，小于基准值，则插入到Arr[L]的坑中；

7.右边有坑了，继续从左边取值继续匹配，则取到Arr[L+1] = 9,小于基准值，则忽略并跳过，继续找Arr[L + 1]继续匹配。

8.继续从左边坐标 + 1 取值继续匹配，则取到Arr[L] = 17，又小于基准值，则忽略并跳过，继续找Arr[L + 1]继续匹配。

9.最后L坐标和R坐标重合了，将Pivot基准值填入

10.至此，快速排序第一轮完整流程结束，分出了左右子序列，左边都是小于Pivot基准值的，右边都是大于Pivot基准值的。

11.继续对左、右子序列递归进行处理，一直缩小到左、右都是一个值，则快速排序结束，最终得出顺序数组{1,8,9,17,19,97}；中间递归流程这里不再赘述。

五、快排代码@java代码

package com.softsec.demo; /** * Created with IDEA * * @Author Chensj * @Date 2020/5/17 19:04 * @Description * @Version 1.0 */public class quickSortDemo {     public static void main(String[] args) {        // 创建测试数组        int[] arr = new int[]{19,97,9,17,1,8};        System.out.println("排序前：");        showArray(arr); // 打印数组        // 调用快排接口        quickSort(arr);        System.out.println("\n" + "排序后：");        showArray(arr);// 打印数组    }     /**     * 快速排序     * @param array     */    public static void quickSort(int[] array) {        int len;        if(array == null                || (len = array.length) == 0                || len == 1) {            return ;        }        sort(array, 0, len - 1);    }     /**     * 快排核心算法，递归实现     * @param array     * @param left     * @param right     */    public static void sort(int[] array, int left, int right) {        if(left > right) {            return;        }        // base中存放基准数        int base = array[left];        int i = left, j = right;        while(i != j) {            // 顺序很重要，先从右边开始往左找，直到找到比base值小的数            while(array[j] >= base && i < j) {                j--;            }             // 再从左往右边找，直到找到比base值大的数            while(array[i] <= base && i < j) {                i++;            }             // 上面的循环结束表示找到了位置或者(i>=j)了，交换两个数在数组中的位置            if(i < j) {                int tmp = array[i];                array[i] = array[j];                array[j] = tmp;            }        }         // 将基准数放到中间的位置（基准数归位）        array[left] = array[i];        array[i] = base;         // 递归，继续向基准的左右两边执行和上面同样的操作        // i的索引处为上面已确定好的基准值的位置，无需再处理        sort(array, left, i - 1);        sort(array, i + 1, right);    }     /**     * 数组打印     * @param num     */    private static void showArray(int[] num) {        for (int i = 0; i < num.length; i++) {            System.out.print(num[i] + " ");        }    }}

返回结果：

排序前：19 97 9 17 1 8 排序后：1 8 9 17 19 97 Process finished with exit code 0

#快速排序 传入列表、开始位置和结束位置def quick_sort( li , start , end ):    # 如果start和end碰头了，说明要我排的这个子数列就剩下一个数了，就不用排序了    if not start < end :        return     mid = li[start] #拿出第一个数当作基准数mid    low = start   #low来标记左侧从基准数始找比mid大的数的位置    high = end  #high来标记右侧end向左找比mid小的数的位置     # 我们要进行循环，只要low和high没有碰头就一直进行,当low和high相等说明碰头了    while low < high :        #从high开始向左，找到第一个比mid小或者等于mid的数，标记位置,（如果high的数比mid大，我们就左移high）        # 并且我们要确定找到之前，如果low和high碰头了，也不找了        while low < high and li[high] > mid :            high -= 1        #跳出while后，high所在的下标就是找到的右侧比mid小的数        #把找到的数放到左侧的空位 low 标记了这个空位        li[low] = li[high]        # 从low开始向右，找到第一个比mid大的数，标记位置,（如果low的数小于等于mid，我们就右移low）        # 并且我们要确定找到之前，如果low和high碰头了，也不找了        while low < high and li[low] <= mid :            low += 1        #跳出while循环后low所在的下标就是左侧比mid大的数所在位置        # 我们把找到的数放在右侧空位上，high标记了这个空位        li[high] = li[low]        #以上我们完成了一次 从右侧找到一个小数移到左侧，从左侧找到一个大数移动到右侧    #当这个while跳出来之后相当于low和high碰头了，我们把mid所在位置放在这个空位    li[low] = mid    #这个时候mid左侧看的数都比mid小，mid右侧的数都比mid大     #然后我们对mid左侧所有数进行上述的排序    quick_sort( li , start, low-1 )    #我们mid右侧所有数进行上述排序    quick_sort( li , low +1 , end )  #入口函数if __name__ == '__main__':    li = [19,97,9,17,1,8]    quick_sort(li , 0 , len(li) -1 )    print(li)

快速排序是当前最为流行的排序算法之一，各大公司面试中频频出现，希望通过这篇文章，让你对快速排序知识点有一定的了解，在日后面试或各种考试中对你有所帮助！

目前在职Java开发，如果你现在也在学习Java，在入门学习Java的过程当中缺乏基础入门的视频教程， 可以关注并私信我：01。免费领取2020年最新Java基础精讲视频教程，学习手册，面试题，开发工具，PDF文档书籍教程，以下资料截图：

关注并私信我：01。即可领取以上学习资料。