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

有趣的算法(七)

——快速排序改进算法

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

一、概述

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

相关文章

来自专栏AI派

Numpy 修炼之道(1) —— 什么是 Numpy

简单来说,Numpy 是 Python 的一个科学计算包,包含了多维数组以及多维数组的操作。

2814
来自专栏Python小屋

奇怪,Python有的函数调用需要两对括号?(2)

在Python中,允许嵌套定义函数,也就是在一个函数A中可以定义另一个函数B。另外,在Python中,可调用对象可以分为三类:1)函数,2)类,3)含有特殊方法...

2789
来自专栏Golang语言社区

【Go 语言社区】面向对象

面向对象 Go是面向对象的,但没有如下概念: class类 extends继承 implements实现 我们首先看看Go使用type来表达类型,type关键词...

3277
来自专栏zaking's

用js来实现那些数据结构03(数组篇03-排序及多维数组)

  终于,这是有关于数组的最后一篇,下一篇会真真切切给大家带来数据结构在js中的实现方式。那么这篇文章还是得啰嗦一下数组的相关知识,因为数组真的太重要了!不要怀...

2925
来自专栏和蔼的张星的图像处理专栏

365. 二进制中有多少个1

思路一:遍历每一位,如果是1,计数器加1即可,也是最容易想到的,需要遍历一次,可以用不断除2来做,也可以用位操作,后者更简单些:

532
来自专栏青青天空树

取随机数

  常用于去随机数的函数为rand()(在stdlib.h头文件中,不同的编译器可能有不同),但是实际在使用这个函数时却发现每次程序运行产生的数都是一样的,这是...

672
来自专栏瓜大三哥

HLS Lesson13-for循环优化:合并

#include"ap_int.h" #define DATAW 8 #define CTRLW 1 #define N 4 #define M 2 typed...

20710
来自专栏web前端教室

[先行者周日课程-0305] web前端组件 之 拖动窗口

学习笔记如下: 今天的内容,是拖动窗口。 js的引用数据类型,基本数据类型。 js它有5种基本数据类型: undefined , null, Boolean,...

1798
来自专栏听雨堂

Python学习笔记(3):数据集操作-列的统一操作

对数据库查询,将得到一个数据集: rs=AccessDB.GetData("select * from log where f_code='600259' ...

1929
来自专栏我的博客

正则表达式–应用篇

匹配年月日(常见三种格式2012-12-12、2012/12/12、2012年12月12日) <?php //匹配格式如:2012年12月12日 $mode...

2453

扫描关注云+社区