有趣的算法（七） ——快速排序改进算法

有趣的算法（七） ——快速排序改进算法

目录

有趣的算法（七） ——快速排序改进算法

---

 

 

本文章向大家介绍有趣的算法（七） ——快速排序改进算法，主要内容包括其使用实例、应用技巧、基本知识点总结和需要注意事项，具有一定的参考价值，需要的朋友可以参考一下。

 

有趣的算法（七）

——快速排序改进算法

（原创内容，转载请注明来源，谢谢）

一、概述

快速排序，被认为是最好的排序算法之一。快速排序是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

    /**
     * 快速排序
     */
    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
            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]
            else i++;//相同的情况，则直接比较下一个元素
        }
        start3WayQuickSort(a, low, equalLeft-1);
        start3WayQuickSort(a, equalRight+1,high);
}

四、总结

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