[排序算法]--快速排序的Java实现

缺乏、安全感 2022-07-12 01:00 181阅读 0赞

# 快速排序 #

> 所谓快速排序：基于分治的思想，是冒泡排序的改进型。首先在数组中选择一个基准点并把基准点放于序列的开头（该基准点的选取可能影响快速排序的效率，关于基准点的选择方法后面再讲解），然后分别从数组的两端扫描数组，设两个指示标志（lo指向起始位置，hi指向末尾)，首先从后半部分开始，如果发现有元素比该基准点的值小，就交换lo和hi位置的值，然后从前半部分开始扫秒，发现有元素大于基准点的值，就交换lo和hi位置的值，如此往复循环，直到lo>=hi,然后把基准点的值放到hi这个位置，一次排序就完成了。之后再采用递归的方式分别对前半部分和后半部分排序，当前半部分和后半部分均有序时该数组自然也就有序了。

在网上找的关于一次快速排序的示意图如下图：  
![一次快速排序的示意图][SouthEast]

算法的实现:  
1) 首先是进行一轮快速排序的函数：

/** * 一次快速排序 * @param array 数组 * @param lo 数组的前下标 * @param hi 数组的后下标 * @return key的下标index，也就是分片的间隔点 */
    public static int partition(int []array,int lo,int hi){
        /** 固定的切分方式 */
        int key=array[lo];//选取了基准点
        while(lo<hi){
            //从后半部分向前扫描
            while(array[hi]>=key&&hi>lo){
                hi--;
            }
            array[lo]=array[hi];
            //从前半部分向后扫描
            while(array[lo]<=key&&hi>lo){
                lo++;
            }
            array[hi]=array[lo];
        }
        array[hi]=key;//最后把基准存入
        return hi;
    }

2） 快速排序的函数如下：

/** * 快速排序 * @param array * @param lo * @param hi */
    public static void quickSort(int[] array,int lo ,int hi){
        if(lo>=hi){
            return ;
        }
        //进行第一轮排序获取分割点
        int index=partition(array,lo,hi);
        //排序前半部分
        quickSort(array, lo, index - 1);
        //排序后半部分
        quickSort(array,index+1,hi);
    }

3) 测试函数：

public static void main(String[] args) {
        int[] arr = {
       1,9,3,12,7,8,3,4,65,22};
    
        quickSort(arr, 0, arr.length-1);
    
        for(int i:arr){
            System.out.print(i+",");
        }
    }

输出是：

1,3,3,4,7,8,9,12,22,65,

# 快速排序基准点的优化 #

对于基准点的优化一般有三种：固定切分，随机切分和三数取样切分。固定切分的效率并不是太好，随机切分是常用的一种切分，效率比较高，最坏情况下时间复杂度有可能为O(N^2)。对于三数取中选择基准点是最理想的一种。

下面给出三个数取中间数的算法实现：

//三数取中
    //下面的两步保证了array[hi]是最大的；
    int mid=lo+(hi-lo)/2;
    if(array[mid]>array[hi]){
        swap(array[mid],array[hi]);
    }
    if(array[lo]>array[hi]){
        swap(array[lo],array[hi]);
    }
    
    //接下来只用比较array[lo]和array[mid]，让较小的在array[lo]位置就OK。
    if(array[mid]>array[lo]){
        swap(array[mid],array[lo]);
    }
    int key=array[lo];

上面的swap(a, b); 函数的含义就是交换a和b的值。

本文完整代码的github地址：[https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Algorithm/QuickSort.java][https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Algorithm_QuickSort.java]

[SouthEast]: /images/20220711/9a48b88648004abfbceaf24b5e8942a5.png
[https_github.com_leetcode-hust_leetcode_blob_master_louyuting_src_leetcode_Algorithm_QuickSort.java]: https://github.com/leetcode-hust/leetcode/blob/master/louyuting/src/leetcode/Algorithm/QuickSort.java