有趣的算法(七) ——快速排序改进算法

有趣的算法(七)

——快速排序改进算法

(原创内容,转载请注明来源,谢谢)

一、概述

快速排序,被认为是最好的排序算法之一。快速排序是20世纪60年代被提出的,其基本过程如下:

现假设长度为n的数组a[n],需要进行排序。步骤如下:

1)随机选其中一个元素,假设为a[i],将所有值比a[i]小的元素,移到a[i]的左边,假设为数组b;所有比a[i]大的元素,移到a[i]的右边,假设为数组c。

2)将数组b、c分别递归执行步骤1,即将数组不断的分割成大的半部分和小的半部分,并且得到的结果继续递归执行第1步,直到满足第3步的条件。

3)当一个数组的元素只有两个的时候,则直接比较这两个元素的大小,并返回比较结果;当数组元素只有一个,则直接返回这个数组。

快速排序的速度很快,只需要O(nlogn),而且可以不需要额外的空间。

二、问题分析

快速排序在众多排序算法中,属于非常优秀的算法,不过这几十年来,还是有许多人对其进行贡献,提供了一些很好的改进。

从上述步骤中,分析出快速排序主要存在几个问题:

1)第一步需要随机选取一个元素作为切分元素。

现有数组:[1, 2,3, 5, 8, 2, 6, 10],如果恰好取到第一个元素作为切分元素,则比较的结果,是所有后面的元素都要进入大的数组,而小数组没有内容。这样会导致效率低下。

因此,对于切分元素,不能选的太随意,需要改进。

2)快速排序是一个递归的排序算法。

在数组元素很少的时候,如果也用快速排序,则要不断的递归与函数调用,效率较低。而有一些简单的算法,对于数组数量较少的时候,不需要递归,而且方便。

因此,对于数组元素较少的情况,可以采用其他算法。

3)元素值一样的问题。

上述分析,都只考虑大于小于,而没有考虑等于的情况。则在排序的时候,对于等于的元素,也会被移动或者递归,效率较低。

因此,需要考虑多个元素值一致的情况。

三、解决方案

针对上述三个问题,分别有解决方案。

1、切分元素选取

首先,针对传过来的数组,需要打散数组,或者随机选取一个元素,作为基准切分元素,假设为i,则值是a[i],假设v=a[i]。

接着,设定左右扫描指针(实质是数组下标),一个从第一个元素开始(假设下标为p),一个从最后一个元素开始(假设下标为q)。

在每次循环的时候,p从前往后移动,直到找到一个比v小的值的下标;q则从后往前取比v大的下标。将这两个下标对应的值互换。

循环结束的条件是p>=q。结束循环后,将a[i]和a[q]进行互换,实现将切分元素换到数组的中间位置。

代码如下:

    /**
     * 获取快速排序的切分元素,并进行部分排序,保证切分元素左侧元素都小,右侧都大
     */
    private static int partition(Comparable[]a, int low, int high){
        int i = low - 1, j = high + 1;//左右扫描指针
        int randomIndex = (int)(low +Math.random()*(high - low + 1));
        Comparable v = a[randomIndex];//切分元素
        while(true){
            //左边找到比v大的元素
            while(less(a[++i], v, true)){
                if(i >= high) break;
           }
            //右边找到比v小的元素
            while(less(v, a[--j], true)){
                if(j <= low) break;
            }
            //扫描结束退出条件
            if(i >= j) break;
            //交换左右两边找到的元素,保证相对有序
            exchange(a, i, j);
        }
        //将切分元素换到中间
        exchange(a, randomIndex, j);
        return j;
    }

上面代码中,less是自定义方法,用于比较两个数大小;exchange也是自定义方法,用于交换数组下标i、j的值。

经过上述方法,在获取切分元素的同时,实际上已经完成了以切分元素值为中值,对数组进行的切分。

如下图所示:

2、小数组排序

当数组元素较少,不采用快速排序。经过前人研究,数组元素少于5~15个的时候,用插入排序的效率更高。

因此,在递归的返回条件中,将high<low改成high<low+5即可。整个代码如下:

    /**
     * 快速排序
     */
    private static voidstartQuickSort(Comparable[] a, int low, int high){
        if(a.length <= 5 || high < low +5){
            insertSort(a);//数组长度5以内采用插入排序
            return;
        }
        int partitionNum = partition(a, low,high);
        startQuickSort(a, low, partitionNum-1);
        startQuickSort(a, partitionNum+1,high);
}
    /**
     * 插入排序,数组长度5以内采用此方法
     */
    private static void insertSort(Comparable[]a){
        int n = a.length;
        for(int i=1;i<n;i++){
            for(int j=i;j>0 &&less(a[j], a[j-1], false);j--){
                exchange(a, j, j-1);
            }
        }
}

3、同值元素问题

因为当前的快速排序,仅考虑大于和小于。对于等于的情况,可以在设定一个数组,专门存放于切分元素值一样的元素,且放于数组的中间位置。

这个解决方案,被称为三取样切分。和普通的快速排序,区别就在于切分多预留一个区间。

如下图所示:

核心代码如下:

   /**
     * 三取样切分
     */
    private static voidstart3WayQuickSort(Comparable[] a, int low, int high){
        if(a.length <= 5 || high < low +5){
            insertSort(a);//数组长度5以内采用插入排序
            return;
        }
        //equalLeft~equalRight区间是等值的情况,low~equal~equalLeft是小的
        int equalLeft = low, equalRight = high,i = equalLeft +1;
        Comparable v = a[low];
        while(i <= equalRight){
            int cmp = a[i].compareTo(v);
            if(0 < cmp) exchange(a, i,equalRight--);//a[i]>v,交换i和当前最后一个元素,并将最后一个元素-1
            else if(0 > cmp) exchange(a,equalLeft++, i++);//a[i]<v,交换i和左边的元素,并且指针往后
            else i++;//相同的情况,则直接比较下一个元素
        }
        start3WayQuickSort(a, low, equalLeft-1);
        start3WayQuickSort(a, equalRight+1,high);
}

四、总结

快速排序采用三采样切分的改进方案后,在加上小数组情况下引入插入排序,其排序的速度非常快,适合大部分的排序场景。

完整的代码见https://github.com/linhxx/taskmanagement/blob/master/src/main/java/com/lin/service/algorithm/QuickSortService.java,另外,也欢迎到github下载整个项目,这是一个基于springboot的网站,路径:

https://github.com/linhxx/taskmanagement.git

——written by linhxx 2017.10.12

原文发布于微信公众号 - 决胜机器学习(phpthinker)

原文发表时间:2017-10-12

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏彭湖湾的编程世界

【算法】哈希表的诞生

《算法(java)》                           — — Robert Sedgewick, Kevin Wayne

16570
来自专栏大数据和云计算技术

由快速排序到分治思想

算法是基础,小蓝同学准备些总结一系列算法分享给大家,这是第一篇《由快速排序到分治思想》,非常赞!希望对大家有帮助,大家会喜欢! 快速排序是一种基于分治思想...

36360
来自专栏HTML5学堂

原生JS | 数据类型检测,并没你想象的那么简单

HTML5学堂-码匠:看上去,JavaScript中的数据类型检测,并没有什么难度,但是……它包含了不少的知识,如果你只知道一个typeof的话,那很建议你读读...

35150
来自专栏数据小魔方

左手用R右手Python系列13——字符串处理与正则表达式

学习数据分析,掌握一些灵巧的分析工具可以使得数据清洗效率事半功倍,比如在处理非结构化的文本数据时,如果能够了解一下简单的正则表达式,那么你可以免去大量的冗余代码...

39540
来自专栏快乐八哥

JavaScript循环读书笔记

循环知识:自我重复的风险 第一部分: 重复运行的代码就可以使用循环来解决。JavaScript的重复机制为循环(loop) for:适合重复动作已知次数的循环。...

20770
来自专栏ACM算法日常

简单计算器(栈的变种)- HDU 1237

测试输入包含若干测试用例,每个测试用例占一行,每行不超过200个字符,整数和运算符之间用一个空格分隔。没有非法表达式。当一行中只有0时输入结束,相应的结果不要输...

14410
来自专栏liuchengxu

Scala 最佳实践:纯函数

我们所处的是一个命令式编程(imperative programming)的时代,这也是我们为何更喜欢用命令式风格写代码的原因。在我们周围的一切都是可变的。虽然...

9210
来自专栏magicsoar

Effective Modern C++翻译(7)-条款6:当auto推导出意外的类型时,使用显式的类型初始化语义

条款6:当auto推导出意外的类型时,使用显式的类型初始化语义 条款5解释了使用auto来声明变量比使用精确的类型声明多了了很多的技术优势,但有的时候,当你想要...

185100
来自专栏MyBlog

Effective.Java 读书笔记(8)关于equals方法

重写equals看上去十分简单对吧,但是我觉得很多时候重写equals可能会招致一些问题,这些问题有时可能会特别严重,当然了不重写不就完事了吗?但是这只适用于那...

9440
来自专栏python学习之旅

Python笔记(七):字典、类、属性、对象实例、继承

(一)  简单说明    字典是Python的内置数据结构,将数据与键关联(例如:姓名:张三,姓名是键,张三就是数据)。例如:下面这个就是一个字典 {'姓名':...

39150

扫码关注云+社区

领取腾讯云代金券