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

交换排序之高速排序

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

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

高速排序是对冒泡排序的一种改进。它的基本思想是。通过一趟排序将待排记录切割成独立的两部分,当中一部分记录的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)


相关推荐

  • pycharm2021年激活码(破解版激活)

    pycharm2021年激活码(破解版激活),https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • java json对象转map_java引用对象

    java json对象转map_java引用对象1.由json字符串转换成Map对象如json字符串:{“contend”:[{“bid”:“22”,“carid”:“0”},{“bid”:“22”,“carid”:“0”}],“result”:100,“total”:2}下面直接附代码://json字符串Stringjsondata=”{\”contend\”:[{\”bid\”:\”22\”,\”carid\”:\”0\”},{\”bid\”:\”22\”,\”carid\”:\”0\”}],\”result\”:100,\”total\”

  • IDEA快捷键超好看桌面壁纸「建议收藏」

    IDEA快捷键超好看桌面壁纸「建议收藏」idea设置背景图(原帖):https://blog.csdn.net/qq_22194659/article/details/81224193IDEA快捷键超好看桌面壁纸(原帖):https://blog.csdn.net/weixin_44399524/article/details/88232793感谢以上两位大佬提供教程与资源。接下来该我上货了,先看效果:效果图1…

  • Flask中jsonify和json.dumps用法以及区别(简单案例)[通俗易懂]

    Flask中jsonify和json.dumps用法以及区别(简单案例)[通俗易懂]环境:python3.6,Flask1.0.3flask提供了jsonify函数供用户处理返回的序列化json数据,而python自带的json库中也有dumps方法可以序列化json对象.其二者的区别,写个简单的案例实测一下便见分晓。fromflaskimportFlaskfromflaskimportjsonifyimportjsonapp=F…

  • 【翻译自mos文章】当指定asm disk 为FRA时,11.2.0.3的dbua hang住

    【翻译自mos文章】当指定asm disk 为FRA时,11.2.0.3的dbua hang住

  • 投影矩阵 视图模型矩阵「建议收藏」

    投影矩阵 视图模型矩阵「建议收藏」
        OpenGL在设置场景时,要用到两个矩阵:投影矩阵和模型视图矩阵通过glMatrixMode来指定下面的矩阵操作是针对哪一个矩阵进行的。
        gluLookatup,glTranslate,glRotate,glScale,glOrtho,gluPerspective等函数只根据其参数计算出一个矩阵M,然后与当前的栈顶元素T相乘;但这些函数本身不能自动找到应该对应的矩阵堆栈,你可以将它们放在任何矩阵堆栈操作中,比如可以将gluLookatup放在glMat

发表回复

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

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