快速排序Java实现_快速排序实现java

快速排序Java实现_快速排序实现java高快省的排序算法有没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢。假设我们现在对“61279345108”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一个数6作为基准数吧。接下来,需要将这个序列中所有比基准数大的数放…

大家好,又见面了,我是你们的朋友全栈君。

高快省的排序算法

有没有既不浪费空间又可以快一点的排序算法呢?那就是“快速排序”啦!光听这个名字是不是就觉得很高端呢。

假设我们现在对“6 1 2 7 9 3 4 5 10 8”这个10个数进行排序。首先在这个序列中随便找一个数作为基准数(不要被这个名词吓到了,就是一个用来参照的数,待会你就知道它用来做啥的了)。为了方便,就让第一个数6作为基准数吧。接下来,需要将这个序列中所有比基准数大的数放在6的右边,比基准数小的数放在6的左边,类似下面这种排列:

3 1 2 5 4 6 9 7 10 8

在初始状态下,数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置,假设这个位置是k。现在就需要寻找这个k,并且以第k位为分界点,左边的数都小于等于6,右边的数都大于等于6。想一想,你有办法可以做到这点吗?

排序算法显神威

方法其实很简单:分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从找一个小于6的数,再从找一个大于6的数,然后交换他们。这里可以用两个变量i和j,分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边(即i=1),指向数字6。让哨兵j指向序列的最右边(即=10),指向数字。

这里写图片描述
首先哨兵j开始出动。因为此处设置的基准数是最左边的数,所以需要让哨兵j先出动,这一点非常重要(请自己想一想为什么)。哨兵j一步一步地向左挪动(即j–),直到找到一个小于6的数停下来。接下来哨兵i再一步一步向右挪动(即i++),直到找到一个数大于6的数停下来。最后哨兵j停在了数字5面前,哨兵i停在了数字7面前。
这里写图片描述
这里写图片描述
现在交换哨兵i和哨兵j所指向的元素的值。交换之后的序列如下:

6 1 2 5 9 3 4 7 10 8
这里写图片描述
这里写图片描述
到此,第一次交换结束。接下来开始哨兵j继续向左挪动(再友情提醒,每次必须是哨兵j先出发)。他发现了4(比基准数6要小,满足要求)之后停了下来。哨兵i也继续向右挪动的,他发现了9(比基准数6要大,满足要求)之后停了下来。此时再次进行交换,交换之后的序列如下:

6 1 2 5 4 3 9 7 10 8

第二次交换结束,“探测”继续。哨兵j继续向左挪动,他发现了3(比基准数6要小,满足要求)之后又停了下来。哨兵i继续向右移动,糟啦!此时哨兵i和哨兵j相遇了,哨兵i和哨兵j都走到3面前。说明此时“探测”结束。我们将基准数6和3进行交换。交换之后的序列如下:

3 1 2 5 4 6 9 7 10 8

这里写图片描述
这里写图片描述
这里写图片描述

到此第一轮“探测”真正结束。此时以基准数6为分界点,6左边的数都小于等于6,6右边的数都大于等于6。回顾一下刚才的过程,其实哨兵j的使命就是要找小于基准数的数,而哨兵i的使命就是要找大于基准数的数,直到i和j碰头为止。

OK,解释完毕。现在基准数6已经归位,它正好处在序列的第6位。此时我们已经将原来的序列,以6为分界点拆分成了两个序列,左边的序列是“3 1 2 5 4”,右边的序列是“9 7 10 8”。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧,我们已经掌握了方法,接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。

左边的序列是“3 1 2 5 4”。请将这个序列以3为基准数进行调整,使得3左边的数都小于等于3,3右边的数都大于等于3。好了开始动笔吧

如果你模拟的没有错,调整完毕之后的序列的顺序应该是:

2 1 3 5 4

OK,现在3已经归位。接下来需要处理3左边的序列“2 1”和右边的序列“5 4”。对序列“2 1”以2为基准数进行调整,处理完毕之后的序列为“1 2”,到此2已经归位。序列“1”只有一个数,也不需要进行任何处理。至此我们对序列“2 1”已全部处理完毕,得到序列是“1 2”。序列“5 4”的处理也仿照此方法,最后得到的序列如下:

1 2 3 4 5 6 9 7 10 8

对于序列“9 7 10 8”也模拟刚才的过程,直到不可拆分出新的子序列为止。最终将会得到这样的序列,如下

1 2 3 4 5 6 7 8 9 10

到此,排序完全结束。细心的同学可能已经发现,快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。
这里写图片描述

这是为什么呢?

快速排序之所比较快,因为相比冒泡排序,每次交换是跳跃式的。每次排序的时候设置一个基准点,将小于等于基准点的数全部放到基准点的左边,将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换,交换的距离就大的多了。因此总的比较和交换次数就少了,速度自然就提高了。当然在最坏的情况下,仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2),它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。我们后面还会遇到“二分”思想,到时候再聊。先上代码,如下

代码实现:

public class QuickSort {
    public static void quickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>high){
            return;
        }
        i=low;
        j=high;
        //temp就是基准位
        temp = arr[low];

        while (i<j) {
            //先看右边,依次往左递减
            while (temp<=arr[j]&&i<j) {
                j--;
            }
            //再看左边,依次往右递增
            while (temp>=arr[i]&&i<j) {
                i++;
            }
            //如果满足条件则交换
            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }

        }
        //最后将基准为与i和j相等位置的数字交换
         arr[low] = arr[i];
         arr[i] = temp;
        //递归调用左半数组
        quickSort(arr, low, j-1);
        //递归调用右半数组
        quickSort(arr, j+1, high);
    }


    public static void main(String[] args){
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        quickSort(arr, 0, arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}
输出为
1
2
2
3
4
4
7
7
8
9
10
19
62
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/124795.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • C/C++学习路线

    C/C++学习路线随着互联网及互联网+深入蓬勃的发展,经过40余年的时间洗礼,C/C++俨然已成为一门贵族语言,出色的性能使之成为高级语言中的性能王者。而在今天,它又扮演着什么样重要的角色呢?请往下看:后端服务器,移

  • 什么是模型,什么是模式

    模型(model)与模式(Pattern),英文显然是两个词,但是,在实际使用过程中,却是比较混乱。虽然,我还不清楚厘清这两个词的关系,对基层的数学工作者有怎样的价值,但是至少对理解什么是数学是有益处的,能够帮助我们不止是了解数学的结论,而且了解数学的思考方法。  一、模型与数学模型     (一)模型的定义:     数学辞海第5卷第109页有关于模型的定义:模型

  • 公益代理-开发人员的福音

    公益代理-开发人员的福音

  • C# Sort排序

    C# Sort排序List的Sort方法排序有三种结果1,0,-1分别表示大于,等于,小于。1.对于数值类型的List(List),直接使用Sort进行排序。ListscoreList=newList(){89,100,78,23,67};scoreList.Sort();//默认按升序排列,相当于:scoreList.Sort((x,y)=>x.CompareTo(y))scoreLis

  • ghost备份系统有什么用_win备份和ghost备份的区别

    ghost备份系统有什么用_win备份和ghost备份的区别  Ghost(是GeneralHardwareOrientedSoftwareTransfer的缩写译为“面向通用型硬件系统传送器”)软件是美国赛门铁克公司推出的一款出色的硬盘备份还原工具,可以实现FAT16、FAT32、NTFS、OS2等多种硬盘分区格式的分区及硬盘的备份还原。俗称克隆软件。  1、特点:既然称之为克隆软件,说明其Ghost的备份还原是以硬盘的扇区为单位进行的

  • Qwt、QChart、QCustomPlot使用

    Qwt、QChart、QCustomPlot使用Qwt、QChart、QCustomPlot使用文档文章目录Qwt、QChart、QCustomPlot使用文档@[toc]效果图比较Qwt1、下载源码2、将Qwt编译成共享库3、添加Qwt4、使用Qwt5、添加帮助文档6、示例QCustomPlot1、下载源码2、使用源码3、将QCustomPlot编译成共享库4、示例QChart1、安装2、示例效果图QwtQcustomplotQChart比较美观方面:Qcustomplot≈Qchart>QwtQ

    2022年10月17日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号