您当前的位置: 首页 >  Java

暂无认证

  • 0浏览

    0关注

    92582博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

JAVA实现常见排序算法 快速排序

发布时间:2019-05-30 10:27:18 ,浏览量:0

欢迎点击「算法与编程之美」↑关注我们!

本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。

基本思想:用选取的初始值(一般是第一个)将待排序序列分为小于初始值和大于初始值的两部分,然后重复此操作,最终到排序完成。该算法是一个不稳定的算法(如果待排序序列中存在相同的元素,经过排序后他们的相对位置不发生改变那么这个算法就是稳定的排序算法)

空间复杂度最坏为O(n),平均640?wx_fmt=png

时间复杂度最坏为O(n2),最好为640?wx_fmt=png

Java实现:

public static int[] quickSort(int[] n,  int low, int high) {

         int lowMark = low, highMark = high;

         int record;

         if (low < high) {

            //记录值

            record = n[low];

            while (lowMark != highMark) {

                //高位指针偏移

                while (lowMark < highMark  && n[highMark] >= record) {

                    highMark--;

                }

                //交换元素

                n[lowMark] = n[highMark];

                //低位指针偏移

                while (lowMark < highMark  && n[lowMark] <= record) {

                    lowMark++;

                }

                //交换元素

                n[highMark] = n[lowMark];

            }

            //将记录值写到最后低位指针的位置

            n[lowMark] = record;

            //两边分别进行排序操作

            quickSort(n, low, lowMark - 1);

            quickSort(n, lowMark + 1, high);

         }

         return n;

     }

 where2go 团队

   

微信号:算法与编程之美          

640?wx_fmt=jpeg

长按识别二维码关注我们!

温馨提示:点击页面右下角“写留言”发表评论,期待您的参与!期待您的转发!

关注
打赏
1653961664
查看更多评论
立即登录/注册

微信扫码登录

1.0253s