开发者社区> jackcode0323> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

排序算法之快速排序

简介: 快速排序(Quick Sort)
+关注继续查看

快速排序(Quick Sort)


1.什么是快速排序

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较,但这种状况并不常见。事实上,快速排序通常明显比其他 Ο(nlogn) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。


快速排序使用分治法(Divide and conquer)策略来把一个串行(list)分为两个子串行(sub-lists)。


2.算法步骤

从数列中挑出一个元素,称为 "基准"(pivot);


重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;


递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;


3.动图演示

007S8ZIlly1ghtn5m0uv2g30mj070gsm.gif


4.代码实现

public static void main(String[] args) {
        //初始化数组
        int[] arr = {5, 3, 1, 4, 2, 7, 8, 6, 10, 9};
        quickSort(arr,0,arr.length -1);
        System.out.println(Arrays.toString(arr));
    }
    private static void quickSort(int[] arr,int l, int r){
        if(l >= r){
            return;
        }
        int left = l; 
        int right = r; 
        int pivot = arr[left];
        while(left < right){
            
            while(left < right && arr[right] >= pivot){
                right --;
            }
            if(left < right){
                arr[left] = arr[right];
            }
            while (left < right && arr[left] <= pivot){
                left ++;
            }
            if (left < right){
                arr[right] = arr[left];
            }else{
                arr[left] = pivot;
            }
        }
        quickSort(arr,l,right -1);
        quickSort(arr,right + 1,r);
    }

注释版本:


public static void main(String[] args) {
        //初始化数组
        int[] arr = {5, 3, 1, 4, 2, 7, 8, 6, 10, 9};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
    private static void quickSort(int[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int left = l; // 0
        int right = r; // 9
        int pivot = arr[left]; // 5
        while (left < right) {
            /**
             *  第一次循环:0 < 9 && arr[right] (9)   9 >= 5  条件满足  9 --  = 8
             *  第二次循环:0 < 8 && arr[right] (8)   10 >= 5 条件满足  8 --  = 7
             *  第三次循环:0 < 7 && arr[right] (7)   6 >= 5  条件满足  7 --  = 6
             *  第四次循环:0 < 6 && arr[right] (6)   8 >= 5  条件满足  6 --  = 5
             *  第五次循环:0 < 5 && arr[right] (5)   7 >= 5  条件满足  5 --  = 4
             *  第六次循环:0 < 4 && arr[right] (4)   2 >= 5  条件不满足  此时 left = 0; right = 4
             */
            while (left < right && arr[right] >= pivot) {
                right--;
            }
            /**
             *  0 < 4
             */
            if (left < right) {
                /**
                 *  arr[left] = 5
                 *  arr[right] = 2
                 *  执行之后,数组变成如下:
                 *  {2, 3, 1, 4, 2, 7, 8, 6, 10, 9};
                 */
                arr[left] = arr[right];
            }
            /**
             *  第一次循环:0 < 4 && arr[left] (2) <= 5 条件满足  0 ++  = 1
             *  第二次循环:1 < 4 && arr[left] (3) <= 5 条件满足  1 ++  = 2
             *  第三次循环:2 < 4 && arr[left] (1) <= 5 条件满足  2 ++  = 3
             *  第四次循环:3 < 4 && arr[left] (4) <= 5 条件满足  3 ++  = 4
             *  第四次循环:4 < 4 条件不满足,此时 left = 4; right = 4
             */
            while (left < right && arr[left] <= pivot) {
                left++;
            }
            /**
             *  4 < 4 不满足条件进入else
             */
            if (left < right) {
                arr[right] = arr[left];
            } else {
                /**
                 * arr[left] = 2;
                 * pivot = 5;
                 * arr[left] = 5;
                 * 此时数组变成如下:
                 * {2, 3, 1, 4, 5, 7, 8, 6, 10, 9};
                 */
                arr[left] = pivot;
            }
        }
        /**
         * l = 0
         * right = 4
         * {2, 3, 1, 4};
         * quickSort(arr,0,4-1);
         * 排序基准左侧的数
         */
        quickSort(arr, l, right - 1);
        /**
         * right = 4
         * r = 9
         * {7, 8, 6, 10, 9};
         * quickSort(arr,4 + 1,9);
         * 排序基准右侧的数
         */
        quickSort(arr, right + 1, r);
    }
    
    


5.输出结果

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
经典算法之快速排序
经典算法之快速排序
23 0
经典算法---快速排序
快速排序是冒泡排序的改进算法,主要思想是在待排序列中取一个元素(通常为第一个)作为参照,将序列分为两个子序列,比参照值小的元素和比参照值大的元素各自组成一个子序列。每趟排序会使参照元素归位,并得到两个子序列。在子序列中继续执行该步骤,直到子序列的长度为0或1.
15 0
算法渣-排序-快速
没有一身好内功,招式再多都是空;算法绝对是防身必备,面试时更是不可或缺;跟着算法渣一起从零学算法
345 0
快速排序算法
快速排序算法通过多次比较和交换来实现排序,其排序流程如下
22 0
【算法】快速排序
【算法】快速排序
21 0
排序算法:快速排序
排序算法:快速排序
32 0
算法-快速排序
快速排序是广泛使用的排序算法,它在平均情况下进行n log n比较,以对 n 个元素的数组进行排序。该算法遵循分而治之的方法。分而治之是一种将算法分解为子问题,然后解决子问题,并将结果组合在一起以解决原始问题的技术。
35 0
+关注
60
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载