Java快排算法详解[通俗易懂]

Java架构师必看

发布于 2022-10-24 06:30:40

86702

代码可运行

文章被收录于专栏：Java架构师必看Java架构师必看

运行总次数：2

代码可运行

大家好，我是架构君，一个会写代码吟诗的架构师。今天说一说Java快排算法详解[通俗易懂],希望能够帮助大家进步!!!

快排算法底层基本思想：

先取出数列中的第一个数作为基准数。
将数列中比基准数大的数全部放在他的右边，比基准数小的数全部放在它的左边。
然后在对左右两部分重复第二步，直到各个区间只有一个数。

具体Java代码实现

public class QuickSort { 
   
    public static void sort(int[] array, int low, int high) { 
   
        if (low < high) { 
   
            int part = partition(array, low, high);//获取中间索引，将区间一分为二，分为两个子区间
            sort(array, low, part - 1);//对前面的子区间快速排序
            sort(array, part + 1, high);//对后面的子区间快速排序
        }
    }
    //一趟快速排序，返回值是本次基准的最终索引位置
    private static int partition(int[] array, int low, int high) { 
   
        int benchmark = array[low];//初始化基准，不妨将低位索引值赋给基准
        //从数组的两端向中间开始扫描，寻找基准元素位置
        while (low < high) { 
   
            //高位指针开始向中间寻找比基准小的元素
            while ((low < high) && array[high] >= benchmark) { 
   
                high--;
            }
            //比基准小的高位索引元素赋值到低位索引
            if (low < high) { 
   
                array[low] = array[high];
            }
            //低位指针开始向中间寻找比基准大的元素
            while ((low < high) && (array[low] <= benchmark)) { 
   
                low++;
            }
            //比基准大的低位索引元素赋值到高位索引
            if (low < high) { 
   
                array[high] = array[low];
            }
        }
        //将基准元素归位，基准元素的索引位置就是两个索引指针相遇的位置
        array[low] = benchmark;
        return low;//返回基准元素的最终索引
    }
}

只听到从架构师办公室传来架构君的声音:

旧时王谢堂前燕，飞入寻常百姓家。有谁来对上联或下联?

TestMain类：

import java.util.Arrays;

public class TestMain { 
   
    public static void main(String[] args) { 
   
        int[] array = new int[]{ 
   46,36,96,26,86,16,76,-17};
        int low = 0;//初始低位索引
        int high = array.length-1;//初始高位索引
        System.out.print("排序前：");
        System.out.println(Arrays.toString(array));
        //使用快速排序算法对数组排序
        QuickSort.sort(array,low,high);
        System.out.print("排序后：");
        System.out.println(Arrays.toString(array));
    }
}

运行结果如下：

排序前：[46, 36, 96, 26, 86, 16, 76, -17]
排序后：[-17, 16, 26, 36, 46, 76, 86, 96]

简结快速排序的性能

时间效率：快速排序的平均时间复杂度是O(nlog2n)，当n较大时，通常快速排序被认为在同数量级的排序方法中平均性能是最好的；
空间效率：快速排序是递归过程，每层递归调用时的指针和参数均要用栈来存放，递归调用的深度与对应的二叉树深度是一样的。因此最好的空间复杂度是O(nlog2n)，最坏的空间复杂度是O(n)，平均3. 空间复杂度是O(nlog2n)；稳定性：快速排序是一个不稳定的排序方法。

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-10-232，如有侵权请联系 cloudcommunity@tencent.com 删除

java