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

你的名字 2024-02-22 02:10 49阅读 0赞

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

**目录**

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

--------------------

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

**有趣的算法（七）**

——**快速排序改进算法**

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

一、概述

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

四、总结

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