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

有趣的算法(七)

——快速排序改进算法

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

一、概述

快速排序,被认为是最好的排序算法之一。快速排序是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 条评论
登录 后参与评论

相关文章

来自专栏阿凯的Excel

Python读书笔记20(函数与变量类型)

上期和大家分享了函数如何返回值。其中有个案例是实现知道边长输出正方形面积。 我们来回顾一下! ? 假如我们有一个L的列表,能否批量实现开平方的运算并赋值给新的列...

3354
来自专栏思考的代码世界

Python编程从入门到实践之函数|第8天

函数是带名字的代码块,用于完 成具体的工作。要执行函数定义的特定任务,可调用该函数。需要在程序中多次 执行同一项任务时,你无需反复编写完成该任务的代码,而只需调...

3427
来自专栏海天一树

小朋友学C语言(8):条件判断

(一)if...else 先动手编写一个程序 #include <stdio.h> int main() { int x = -1; if(x ...

2596
来自专栏小白的技术客栈

Python内置数据结构之字典

今天给大家讲解Python内置数据结构:字典。字典的内容比较多,今天只是简单地介绍一下,明天会继续补充字典相关的内容。 关于Windows的环境安装及配置,小白...

2844
来自专栏老司机的技术博客

人人都能学会的python编程教程8:条件判断与循环

实际的项目中条件判断可以说是使用最多的语法之一了,不管是最简单的判断还是负责的业务逻辑和算法,条件判断都如影随形。

1.2K10
来自专栏IT派

这段代码很Pythonic | 相见恨晚的 itertools 库

最近事情不是很多,想写一些技术文章分享给大家,同时也对自己一段时间来碎片化接受的知识进行一下梳理,所谓写清楚才能说清楚,说清楚才能想清楚,就是这个道理了。

723
来自专栏数据小魔方

动态图表10|可选折线图(复选框)

今天要跟大家分享的是动态图表10——可选折线图(复选框)。 本篇推送主要向大家介绍如何使用复选框控制多维图表。涉及到的核心技巧主要有:复选框;if+or函数;图...

2784
来自专栏高性能服务器开发

深入理解C/C++中的指针

C和C++中最强大的功能莫过于指针了(pointer),但是对于大多数人尤其是新手来说,指针是一个最容易出错、也最难掌握的概念了。本文将从指针的方方面面来讲述指...

821
来自专栏CDA数据分析师

工具 | 一些实用的 python 小建议

给dict设置默认值 这样能设置所有key的默认值为[],包括新添的key ? setdefault一次只能设置一个值,但好处是能使用链式语法,但default...

1885
来自专栏老司机的技术博客

宝宝都能学会的python编程教程8:条件判断与循环

先公布上期编程练习的答案,没错,L是一个指向三个列表的二维元祖。 条件判断 实际的项目中条件判断可以说是使用最多的语法之一了,不管是最简单的判断还是负责的业务逻...

3275

扫码关注云+社区