交换排序之高速排序[通俗易懂]

交换排序之高速排序

大家好,又见面了,我是全栈君。

今天大鹏哥跟大家一起学习下交换排序中的高速排序。

高速排序是对冒泡排序的一种改进。它的基本思想是。通过一趟排序将待排记录切割成独立的两部分,当中一部分记录的keyword均比还有一部分的keyword小。则可分别对这两部分记录继续进行排序,以达到真个序列有序。

高速排序基本步骤:

         Step1、定义两个变量low和high,他们的初值分别为low和high,此外另一个变量pivotkey。

         Step2、首先从high所指位置向前搜索找到第一个keyword小于pivotkey的记录和pivotkey交换。

         Step3、从low所指位置向后搜索。找到第一个keyword大鱼pivotkey的记录和pivotkey交换。

         Step4、反复以上步骤直到low=high为止。

 

待排序列:49   38   65   97   76   13   27  49

1、附设low和high以及设枢轴记录的keyword为pivotkey:

                    49   38   65   97  76   13   27   49

                     ↑(low)                               ↑(high)

                    ↑(pivotkey)

2、从high所指位置向前搜索,找到第一个小于pivotkey的记录(此处为27)和枢轴记录互相交换:

                    27   38   65   97  76   13   49   49

                     ↑(low)                               ↑(high)

                                                            ↑(pivotkey)

3、从low所指位置向后搜索,找到第一个大于pivotkey的记录(此处为65)和枢轴记录互相交换:

                   27   38   49  97   76   13   65   49

                              ↑(low)              ↑(high)

                              ↑(pivotkey)

4、反复2、3步直至low=high为止。

                 27   38   13   97  76   49   65   49

                           ↑(low)         ↑(high)

                                            ↑(pivotkey)

                27   38   13   49  76   97   65   49

                                ↑(low) ↑(high)

                                ↑(pivotkey)

                 27   38   13   49  76   97   65   49

                                ↑(low=high)

                                ↑(pivotkey)

上面给出的是一趟快排过程,整个快排过程可递归进行,上述操作完毕后,再分别对两个子序列进行高速排序。

Java实现例如以下:

        

public class QuickSort {

 

    public static void main(String[] args) {

       // TODO Auto-generatedmethod stub

       int[] a={49,38,65,97,76,13,27,49};

       int pivotloc,low=0,high=a.length-1;

       System.out.print(排序前:”);

       for(int x:a){

           System.out.print(x+“,”);

       }

       if(low<high){

           pivotloc = quickSort(a,low,high);

           quickSort(a,low,pivotloc-1);

           quickSort(a,pivotloc+1,high);

       }

       System.out.print(排序后:”);

       for(int x:a){

           System.out.print(x+“,”);

       }

    }

 

    private static int quickSort(int[] a, int low, int high) {

       int pivotkey=a[low];

       while(low<high){

           while(low<high&&a[high]>=pivotkey)

              high–;

           a[low]=a[high];

           while(low<high&&a[low]<=pivotkey)

              low++;

           a[high]=a[low];

       }

       a[low]=pivotkey;

       return low;

    }

 

}

高速排序的时间复杂度为O(NlogN)。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

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

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

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

(0)


相关推荐

  • CentOS7安装Jenkins教程

    CentOS7安装Jenkins教程1.下载JenkinsJenkins下载地址:http://jenkins-ci.org/2.安装jenkins1.卸载旧jenkinsrpm-qa|grepjenkins2.卸载jenkinsrpm-e–nodepsjenkins3.彻底删除jenkins残留文件find/-inamejenkins|xargs-n1000rm-r…

  • bindService与startService区别

    bindService与startService区别1.StartedService中使用startService()方法来进行方法的调用,调用者和服务之间没有联系,即使调用者退出了,服务依然在进行【onCreate()->onStart

  • Flink学习之flink sql「建议收藏」

    Flink学习之flink sql「建议收藏」???? 昨天我们学习完TableAPI后,今天我们继续学SQL,TableAPI和SQL可以处理SQL语言编写的查询语句,但是这些查询需要嵌入用Java、Scala和python编写的程序中。hadoop专题:hadoop系列文章.spark专题:spark系列文章.flink专题:Flink系列文章.????只需要具备SQL的基础知识即可,不需要其他编程经验。我的SQL客户端选择的是docker安装的FlinkSQLClick,大家根据自己的需求安装即可。目录1.1.

  • sql中declare的用法_sql局部变量

    sql中declare的用法_sql局部变量换工作了,以后主要和SqlServer打交道了,仿佛回到了大学,不知道学校的饭还是那么好吃又便宜吗?北京的饭好贵;不知道门口哪家板面的生意是不是还是那么红火,好想再去吃一碗。。。咳咳,不多说了,直接进入主题declare这个类型,其实可以理解为Java里面的public类型变量,全局有效,当然非要较真的话,我觉得归到protected类也可以(不理解的话不要看后半段,只是为了严谨)Java修饰符 public:对所有类可见。使用对象:类、接口、变量、方法 protect..

  • angular第一天

    angular第一天

  • java8中的Collectors.groupingBy用法「建议收藏」

    java8中的Collectors.groupingBy用法「建议收藏」Collectors.groupingBy根据一个或多个属性对集合中的项目进行分组数据准备:publicProduct(Longid,Integernum,BigDecimalprice,Stringname,Stringcategory){ this.id=id; this.num=num; this.price=price; this.name=…

发表回复

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

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