让你一看就懂的快速排序算法(Java)

快速排序

你也许会被快速排序的文章弄得迷迷糊糊,其实大体上去看,快速排序就一步:找个数做基准数,把小于它的数移到它左边,把大于它的数移到它右边。这句话是核心。然后我们只需要让基准数左边的重复上面的步骤,让基准数右边的再重复上面的步骤就完了。

比如我们有一个数组:

    int[] nums = {5, 2, 6, 8, 4, 7, 9, 1};

快速排序的思想就是使用递归,其实使用递归并不是多么复杂,在理解算法的思想后,只需要关注算法中重复的步骤,那就是递归的核心代码。

比如快速排序的算法思想,大体代码如下:

public void quick(int left, int right) {
    /*
    * 给这段代码起个名字为:基准校验
    * 把小于基准数的移到左边,把大于基准数的移到右边
    */
    quick(left, now); //继续处理左边的
    quick(now, right); //继续处理右边的
}

经过一遍基准校验,我们就找到了该基准数在完全排序后的正确位置! 大体算法的流程图:

写出上面的大体算法步骤,就表示我们已经有了雏形,现在该如何实现找个数做基准数,把小于它的数移到它左边,把大于它的数移到它右边呢?

排除不满足的情况:

        //已经不满足条件就代表可以不用递归了
        if (left > right) {
            return;
        }

我们可以定义两个指针,用于遍历数组:

        int start = left;//起点下标
        int end = right;//终点下标

再找一个基准数:

        int temp = nums[left];//把第一个数作为基准点

遍历代码:

 /*如果左右指针还没有走到一起,代表还有位置没有遍历*/
 while (start != end) {    
     //右指针先走,找到小于基准数的停止
     while (start < end && nums[end] >= temp) { 
         end--;     //这是往左移动指针
     }
     //左指针后走,找到大于基准数的停止
     while (start < end && nums[start] <= temp) { 
         start++;  //这是往右移动指针
     }
     //如果左右指针在未相遇时都找到了目标,则交换位置
     if (start < end) {    
         int i = nums[start];
         nums[start] = nums[end];
         nums[end] = i;
     }
     //左右指针走到一起,则遍历结束
 }
 //把基准数与该点交换位置,因为这就是基准数的正确位置
 nums[left] = nums[start];
 nums[start] = temp;

如果还是不太清楚,不如自己动手试试!

拷贝完整代码:

    //定义一个数组
    static int[] nums = {5, 2, 6, 8, 4, 7, 9, 1};
    static int n = nums.length - 1;

    /**
     * 递归的数据结构就是栈
     * left right代表该段数组的起点和终点
     */
    public void quick(int left, int right) {
        //已经不满足条件就可以不用递归了
        if (left > right) {
            return;
        }
        //定义俩指针 用于移动
        int start = left;//起点下标
        int end = right;//终点下标
        int temp = nums[left];//把第一个数作为基准点

        pri(left, right);//打印此时的结果,不用在意

        while (start != end) {    //如果左右指针还没有走到一起,代表还有位置没有遍历
            while (start < end && nums[end] >= temp) { //右指针先走,找到小于基准数的停止
                end--;            //这是往左在移动指针
            }
            while (start < end && nums[start] <= temp) { //左指针后走,找到大于基准数的停止
                start++;     //这是往右在移动指针
            }
            if (start < end) {    //如果左右指针在未相遇时都找到了目标,则交换位置
                int i = nums[start];
                nums[start] = nums[end];
                nums[end] = i;
            }
        }
        //此时的left和right走到了一起
        //把基准数与该点交换位置
        nums[left] = nums[start];
        nums[start] = temp;

        prin(start);//打印输出,不用在意

        //以上代码的作用就是把小于基准数的移到左边,把大于基准数的移到右边
        quick(left, start - 1); //继续处理左边的,这里是一个递归的过程
        quick(start + 1, right); //继续处理右边的 ,这里是一个递归的过程

    }

    /**
    * 主程序入口
    */
    public static void main(String[] args) {
        new Test().quick(0, n);
    }


    /**
     * 以下代码忽略即可,用于打印输出
     */
    private void pri(int start, int end) {
        StringBuffer s = new StringBuffer();
        s.append("对数组 [");
        while (start <= end) {
            s.append(nums[start] + " ");
            start++;
        }
        s.append("]");
        s.append(" 排序");
        System.out.print(s);
    }

    private void prin(int j) {
        StringBuffer s = new StringBuffer();
        s.append(", 排序后 [");
        int start = 0;
        while (start <= n) {
            if (start == j) {
                s.append("(" + nums[start] + ") ");
            } else {
                s.append(nums[start] + " ");
            }
            start++;
        }
        s.append("]");
        s.append(" ");
        System.out.println(s);
    }

打印输出:

对数组 [5 2 6 8 4 7 9 1 ] 排序, 排序后 [4 2 1 (5) 8 7 9 6 ] 
对数组 [4 2 1 ] 排序, 排序后 [1 2 (4) 5 8 7 9 6 ] 
对数组 [1 2 ] 排序, 排序后 [(1) 2 4 5 8 7 9 6 ] 
对数组 [2 ] 排序, 排序后 [1 (2) 4 5 8 7 9 6 ] 
对数组 [8 7 9 6 ] 排序, 排序后 [1 2 4 5 6 7 (8) 9 ] 
对数组 [6 7 ] 排序, 排序后 [1 2 4 5 (6) 7 8 9 ] 
对数组 [7 ] 排序, 排序后 [1 2 4 5 6 (7) 8 9 ] 
对数组 [9 ] 排序, 排序后 [1 2 4 5 6 7 8 (9) ] 

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏五分钟学算法

每周一算:Move Zeros

思路:创建一个临时数组nonZeroElements,遍历nums,将nums中非0元素赋值到nonZeroElements中,而后按顺序将nonZeroEle...

1102
来自专栏GreenLeaves

JavaScript引用类型之Array数组的排序方法

数组中已经存在两个JavaScript给我们定义好的重排序的方法:reverse()和sort()方法,下面来简单分析下: 1、reverse()    用于反...

2116
来自专栏老九学堂

嘀 , 嘀嘀 ... 常用排序算法再总结

  这篇文章中再和小伙伴们来探讨一下常用的非比较排序算法:计数排序,基数排序,桶排序。在一定条件下,它们的时间复杂度可以达到O(n)。

1263
来自专栏武培轩的专栏

排序算法-插入排序

算法简介 插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应...

2754
来自专栏编程

python学习第二天:python的函数、循环和条件、类

第一天学习了Python的基本操作,以及几种主要的容器类型,今天学习 ,这样才算对Python有一个大致的了解。今天的学习大纲如下: 三、函数 1、定义函数 四...

1796
来自专栏云霄雨霁

排序----插入排序

1450
来自专栏C语言及其他语言

【蓝桥杯系列】第一节 C的基本用法

置顶编程范收获更多热门编程快讯 大家好,最近很多小伙伴向我反应小编!我参加了蓝桥杯但是我连那是什么都不知道,我该怎么训练?是不是在网站刷题就可以啊? 在这里我要...

3967
来自专栏一“技”之长

JavaScript基础之三——基本运算符 原

    大多数语言支持的基本运算符都差别不大。其中最常用的莫属赋值运算符,编程初学者总是会将赋值运算符与相等运算符混淆,需要注意,赋值运算符用于将等号右侧的值赋...

701
来自专栏编程

python奇遇记:深入的了解函数

很久没更新了,抱歉。最近一段时间忙着对付各种考试,现在总算是考完了,继续来聊聊Python。Python中的函数使用def关键字定义,这个大家都知道,而且Pyt...

17710
来自专栏Python小屋

Python中的循环结构

Python主要有for循环和while循环两种形式的循环结构,多个循环可以嵌套使用,并且还经常和选择结构嵌套使用。while循环一般用于循环次数难以提前确定的...

3836

扫码关注云+社区

领取腾讯云代金券