【面试必备】——快速排序算法

逃离我推掉我的手 2022-12-07 15:08 118阅读 0赞

# 快速排序介绍 #

快速排序使用的是分治策略

它的基本思想：选择一个基数，通过一趟排序将要排序的数据分隔成 独立的两部分；其中一部分的所有 数据比另外一部分的所有数据都要小。 然后，按照此方法对这两部分数据分别就行快速排序，整个过程可以递归进行，以此达到整个数据变成有序序列

# 快速排序的流程 #

1）选择一个基准值（一般就采用第一个数）

2）将所有比基准值小的数 移动到基准值前面，所有比基准值大的数移动到基准值后面(相同的数据可以放在任何一边)；在这个分区退出以后，该基准就处在数列的中间位置

3）采用递归方式，将基准值前面的序列 和 基准值后面的序列 进行排序

# 图文流程介绍 #

下面以数列a=\{30,40,60,10,20,50\}为例，演示它的快速排序过程(如下图)。

![fdc760798fdb4f00558dc3662a2d9a24.png][]

上图只是给出了第1趟快速排序的流程。在第1趟中，设置x=a\[i\]，即x=30。  
1) 从"右 --> 左"查找小于x的数：找到满足条件的数a\[j\]=20，此时j=4；然后将a\[j\]赋值a\[i\]，此时i=0；接着从左往右遍历。  
2) 从"左 --> 右"查找大于x的数：找到满足条件的数a\[i\]=40，此时i=1；然后将a\[i\]赋值a\[j\]，此时j=4；接着从右往左遍历。  
3) 从"右 --> 左"查找小于x的数：找到满足条件的数a\[j\]=10，此时j=3；然后将a\[j\]赋值a\[i\]，此时i=1；接着从左往右遍历。  
4) 从"左 --> 右"查找大于x的数：找到满足条件的数a\[i\]=60，此时i=2；然后将a\[i\]赋值a\[j\]，此时j=3；接着从右往左遍历。  
5) 从"右 --> 左"查找小于x的数：没有找到满足条件的数。当i>=j时，停止查找；然后将x赋值给a\[i\]。此趟遍历结束！

按照同样的方法，对子数列进行递归遍历。最后得到有序数组！

# 代码实现： #

public static void quickSort(int[] array,int low,int high){
            if (low <high){
                int index = getIndex(array, low, high);
                quickSort(array,low,index -1);
                quickSort(array,index +1,high);
    
            }
        }
    
        public static int getIndex(int[] array,int i,int j){
            int x = array[i];
            while (i < j){
    
                //从右向左 寻找小于x 的值
                while (i < j && array[j] >= x){
                    j--;
                }
                array[i] = array[j];
    
                //从右向左 寻找大于x 的值
                while (i <j && array[i] <= x){
                    i ++;
                }
                array[j] = array[i];
    
            }
            array[i] = x;
            return i;
        }
    
        public static void main(String[] args) {
            int[] arr = { 49, 38, 65, 97, 23, 22, 76, 1, 5, 8, 2, 0, -1, 22 };
            quickSort(arr, 0, arr.length - 1);
            System.out.println("排序后:");
            for (int i : arr) {
                System.out.println(i);
            }
    
    
    
        }

[fdc760798fdb4f00558dc3662a2d9a24.png]: /images/20221123/22e6bb83d17343e388d016f26b68721c.png