登录后台

页面导航

本文编写于 2168 天前,最后修改于 1237 天前,其中某些信息可能已经过时。

前面介绍的线性表、栈、队列、树等都属于数据结构的范围,它们的主要作用是用来保存数据。接下来介绍的内容属于算法领域———排序。排序的作用是对一组数据元素(或记录)按某个关键字进行排序,排序完成的序列可用于快速查找相关记录。

排序算法的发展历史几乎和计算机的发展历史一样悠久,而且直到今天,世界范围内依然右计算机科学家正在研究着排序算法,由此可见排序算法的强大魅力。

排序算法属于算法的一种,而且是覆盖范围极小的一种。虽然排序算法是计算机科学里古老且研究人数相当多的一种算法,但千万不要把排序算法和广义的计算机算法等同起来。掌握排序算法对程序开发,程序思维的培养右很大帮助,但掌握排序算法绝不等于掌握了计算变成算法的全部。广义的算法包括客观世界运行的规律。

排序的基本概念

在计算机程序开发过程中,经常需要对一组数据元素(或记录)按某个关键字进行排序,排序完成的序列可用于快速查找的相关记录。

排序概述

排序是程序开发中一种非常常见的操作,对一组任意的数据元素(或记录)经过排序操作后,就可以把它们变成一组按关键字排序的有序序列。

假设含有 n 个记录的序列为{R1,R2,…,Rn},其相应的关键字序列为{k1,k2,…,kn}。将这些记录重新排序为{Ri1,Ri2,…,Rin},使得相应的关键字值满足条件 Ki1≤Ki2≤…≤Kin,这样的一种操作称为排序。

一旦将一组杂乱无章的记录重排成一组有序记录,接下来就能快速从这组记录中找到目标记录。因此通常来说,排序的目的是快速查找。

对于一个排序算法来说,一般从如下 3 个方面来衡量算法的优劣。

  • 时间复杂度:它主要是分析关键的比较次数和记录的移动次数;
  • 空间复杂度:分析排序算法中需要多少辅助内存;
  • 稳定性:若两个记录 A 和 B 的关键字值相等,但排序后 A、B 的先后次序保持不变,则称这种排序算法是稳定的;反之,就是不稳定的。

就现有的排序算法来看,排序大致可分为内部排序和外部排序。如果整个排序过程不需要借助于外部存储器(如磁盘等),所有排序操作都在内存中完成,这种排序就被称为内部排序。

如果参与排序的数据元素非常多,数据量非常大,计算无法把整个过程放在内存中完成,必须借助于玩不存储器(如磁盘等),这种排序就被称为外部排序。

外部排序最常用的算法是多路归并排序,即将原文件分解成多个能够一次性装入内存的部分,分别把每一部分调入内存完成排序,接下来再对多个有序的子文件进行归并排序。
外部排序需要包括以下两个步骤。

  1. 把要排序的文件中的一组记录读入内存储器的排序区,对读入的记录按上面降到的内部排序法进行排序,排序之后输出到外存储器,不断重复这一过程,每次读取一组记录,直到原文件所有记录被处理完毕;
  2. 将上一步分组排好序的记录两组两组地合并排序。在内存容量允许的条件下,每组包含的记录越大越好,这样可减少合并的次数。

对于外部排序来说,程序必须将数据分批调入内存来排序,中间结果还要及时放入外存,显然外部排序要比内部排序更复杂。实际上,也可认为外部排序是由多次内部排序组成的。

常说的排序都是指外部排序,而不是外部排序。

内部排序的分类

就内部排序来说,可以使用非常简单的排序算法来完成,如直接选择、直接插入等,但也有一些非常优秀、复杂的排序算法,如快速排序、基数排序等。就常用的内部排序来说算法来说,可以分为如下几类。

  • 选择排序(直接选择排序、堆排序);
  • 交换排序(冒泡排序、快速排序);
  • 插入排序(直接插入排序、折半插入排序、Shell 排序);
  • 归并排序;
  • 桶式排序;
  • 基数排序。

上面这些内部排序方法大致有如下的分类:

                          内部排序
       ______________________|________________________
       |        |        |         |        |        |
    选择排序  归并排序  交换排序  基数排序  桶式排序  插入排序
  ____|_____          ____|_____         ____________|______
  |        |          |        |         |        |        |
直接排序  堆排序    冒泡排序  快速排序  直接排序  插入排序  Shell排序

选择排序法

常用的选择排序方法有两种:直接选择排序和堆排序。直接排序简单直观,但性能略差;堆排序是一种较为高效的选择排序方法,但实现起来略微复杂。

直接选择排序

直接选择排序的思路很简单,它需要经过 n-1 趟比较。

第 1 趟比较:程序将记录定位在第 1 个数据上,拿第 1 个数据依次和它后面每个数据进行比较,如果第 1 个数据大于后面某个数据,交换它们……依次类对。经过第 1 趟比较,这组数据中最小的数据就被选出,它排在第 1 位。

第 2 趟比较:程序将记录定位在第 2 个数据上,拿第 2 个数据依次和它后面每个数据进行比较,如果第 2 个数据大于后面某个数据,交换它们……依次类对。经过第 2 趟比较,这组数据中第 2 小的数据就被选出,它排在第 2 位。

……

按此规则一共进行 n-1 趟比较,这组数据中第 n-1 小(第 2 大)的数据被选出,被排在第 n-1 位(倒数第 2 位);剩下的就是最大的数据,它排在最后。

直接选择排序的优点是算法简单,容易实现。

直接选择排序的缺点是,每趟只能确定一个元素,n 个数组需要进行 n-1 趟比较。

基于上面思路,实现的直接选择排序,如下所示。

class DataWrap implements Comparable<DataWrap> {
    int data;
    String flag;
    public DataWrap(int data, String flag) {
        this.data = data;
        this.flag = flag;
    }
    @Override
    public String toString() {
        return data + flag;
    }
    //根据data实例变量来决定两个DataWrap的大小
    @Override
    public int compareTo(DataWrap o) {
        return this.data > o.data ? 1 : (this.data == o.data ? 0 : -1);
    }
}
public class SelectSort {
    public static void selectSort(DataWrap[] data) {
        System.out.println("开始排序");
        int arrayLength = data.length;
        //依次进行n-1趟比较,第i趟比较将第i大的值选出放在i位置上
        for (int i = 0;i < arrayLength - 1;i++) {
            int minIndex = i;
            //第i个数据只需要和它后面的数据比较
            for (int j = i + 1;j < arrayLength;j++) {
                //如果第i位置的数据>j位置的数据,交换它们
                if (data[i].compareTo(data[j]) > 0) {
                    DataWrap tmp = data[i];
                    data[i] = data[j];
                    data[j] = tmp;
                }
            }
            System.out.println(java.util.Arrays.toString(data));
        }
    }

    public static void main(String[] args) {
        DataWrap[] data = {new DataWrap(21, ""),
                new DataWrap(30, ""),
                new DataWrap(49, ""),
                new DataWrap(30, "*"),
                new DataWrap(16, ""),
                new DataWrap(9, "")};
        System.out.println("排序之前:\n" + Arrays.toString(data));
        selectSort(data);
        System.out.println("排序之后:\n" + Arrays.toString(data));
    }
}

运行上次程序,可以看到如下结果:

排序之前:
[21, 30, 49, 30*, 16, 9]
开始排序
[9, 30, 49, 30*, 21, 16]
[9, 16, 49, 30*, 30, 21]
[9, 16, 21, 49, 30, 30*]
[9, 16, 21, 30, 49, 30*]
[9, 16, 21, 30, 30*, 49]
排序之后:
[9, 16, 21, 30, 30*, 49]

从上面直接排序算法可以看出,直接选择排序算法的关键就是 n-1 趟比较,每趟比较的目的就是选择出本趟比较中最小的数据,并将该数据放在本趟比较的第 1 位。在这里的描述不难发现,其实直接选择排序的每趟比较最多只需交换依次就够:只要找到本趟比较中最小的数据,然后拿它和本趟比较中第 1 位的数据交换。

对于上面的算法实现,其实有一个很大问题:在每趟比较过程中,程序一旦发现某个数据比第 1 位数据项小,立即交换它们。这保证了在每趟比较的所有比较过的数据中,第 1 位的数据永远是最小的,但这没有太大必要,反而正价的交换的次数,导致算法效率低。

对上面直接选择排序算法进行改进,改进后的直接选择排序算法如下。

public class SelectSort2 {
    public static void selectSort(DataWrap[] data) {
        System.out.println("开始排序");
        int arrayLength = data.length;
        //依次进行n-1趟比较,第i趟比较将第i大的值选出放在i位置上
        for (int i = 0;i < arrayLength - 1;i++) {
            //minIndex永远保留本趟比较中最小值的索引
            int minIndex = i;
            //第i个数据只需和它后面的数据比较
            for(int j = i+1;j < arrayLength;j++) {
                //如果第minIndex位置的数据>j位置的数据
                if (data[minIndex].compareTo(data[j]) > 0) {
                    //将j的值赋给minIndex
                    minIndex = j;
                }
            }
            //每趟比较最多交换依次
            if (minIndex != i) {
                DataWrap tmp = data[i];
                data[i] = data[minIndex];
                data[minIndex] = tmp;
            }
            System.out.println(Arrays.toString(data));
        }
    }

    public static void main(String[] args) {
        DataWrap[] data = {new DataWrap(21, ""),
                new DataWrap(30, ""),
                new DataWrap(49, ""),
                new DataWrap(30, "*"),
                new DataWrap(16, ""),
                new DataWrap(9, "")};
        System.out.println("排序之前:\n" + Arrays.toString(data));
        selectSort(data);
        System.out.println("排序之后:\n" + Arrays.toString(data));
    }
}

从上面的成可以可以看出,在这种排序算法的规则下,每趟比较的目的只是找出本趟比较中最小数据的索引——也就是上面程序 minIndex 变量所保存的值。当本趟比较的第 1 位(由 i 变量保存)与 minIndex 不相等时,交换 i 和 minIndex 两处的数据。

运行上面的程序,将会看到如下的结果:

排序之前:
[21, 30, 49, 30*, 16, 9]
开始排序
[9, 30, 49, 30*, 16, 21]
[9, 16, 49, 30*, 30, 21]
[9, 16, 21, 30*, 30, 49]
[9, 16, 21, 30*, 30, 49]
[9, 16, 21, 30*, 30, 49]
排序之后:
[9, 16, 21, 30*, 30, 49]

从上面的结果可以看出,直接选择排序的第 n 趟比较至多交换一次,永远总是拿 n-1 位的数据和中间某项数据(本趟比较中最小的数据)进行交换。如果本趟比较时第 n-1 位(本趟比较的第 1 位)数据已经是最小,那就无需交换。

对于直接选择排序算法而言,假设有 n 项数据,数据交换的次数最多有 n-1 次,但程序比较的次数较多。总体来说,其时间效率为 O(n^2)。

直接排序排序算法空间效率很高,它只需要一个附加程序单元用于交换,其空间效率很高为 O(1)。

从上面程序中两个 data 为 30 的 DataWrap 的排序结果来看,直接排序是不稳定的。

堆排序

介绍堆排序之前,先来介绍一下堆有关的概念。

假设有 n 个数据元素的序列 k0,k1,…,kn-1,当且仅当满足如下关系时,可以将这组数据称为小顶堆(小根堆)。
ki <=k2i+1 且 ki <= k2i+2(其中 i=0,2,…,(n-1)/2)
或者,满足如下关系时,可以将这组数据称为大顶堆(大根堆)。
ki >= k2i+1 且 ki >= k2i+2(其中 i=0,2,…,(n-1)/2)
对于满足小顶堆的数据序列 k0,k1,…,kn-1,如果将它们顺序排成一颗完全二叉树,则次数的特点是:树中所有节点的值都小于其左右子节点的值,此树的根节点的值必然最小。反之,对于满足大顶堆的数据序列 k0,k1,…,kn-1,如果将它们顺序排成一颗完全二叉树,则此树的特点是:树中所有节点的值都大于其左右子节点的值,次树的根节点的值必然最大。

通过上面介绍不难发现一点,小顶堆的任意子树也是小顶堆,大顶堆的任意子树还是大顶堆。

对于一颗顺序结构的完全二叉树而言,对于索引为 k 的节点,它的两个子节点的索引分别为 2k+1、2k+2;反过来,对于索引为 k 的节点,其父节点的索引 k-1/2。

例如,判断数据序列 9, 30, 49, 46, 58, 79 是否为堆,将其转换为一颗完全二叉树,则有如下所示的二叉树。

        9(0)
       /    \
    /          \
  30(1)        49(2)
  /    \      /
46(3) 58(4) 79(5)

上面所示二叉树括号里的数组代表该节点的数据在底层数组中索引,这个二叉树完全满足小顶堆的要求,每个父节点的值总小于等于它的左、右子节点。

判断数据序列 93, 82, 76, 63, 58, 67, 55 是否为堆,将其转换为一颗完全二叉树,则有如下所示的二叉树。

        93(0)
       /    \
    /          \
  82(1)        76(2)
  /    \      /    \
63(3) 58(4) 67(5) 55(6)

上面所示二叉树完全满足大顶堆的要求,每个父节点的值总大于等于它的左、右子节点。

经过上面介绍不难发现一点,大顶堆的根节点一定是这组数据中值最大的节点。也就是说,如果需要堆一组数据进行排序,只需先将这组数据建成大顶堆,就选择出了这组数据的最大值。

堆排序的关键在于建堆,它按如下步骤完成排序。

第 1 趟将索引 0~n-1 处的全部数据建大顶(或小顶)堆,就可以选择出这组数据中最大(或最小)值。

将上一步所建的大顶(或小顶)堆的根节点与这组数据的最后一个节点交换,就使得这组数据中最大(或最小)的值排在最后。

第 2 趟将索引 0~n-2 处的全部数据建大顶(或小顶)堆,就可以选择出这组数据中最大(或最小)值。

将上一步所建的大顶(或小顶)堆的根节点与这组数据的倒数第 2 个节点交换,就使得这组数据中最大(或最小)值排在倒数第 2 位。

……

第 k 趟将索引 0~n-k 处的全部数据建大顶(或小顶)堆,就可以选择出这组数据中最大(或最小)值。

将上一步所建的大顶(或小顶)堆的根节点与这组数据的倒数第 k 个节点交换,就使得这组数据中最大(或最小)值排在倒数第 k 位。

通过上面介绍不难发现,堆排序的步骤就是重复执行以下两步。

  1. 建堆;
  2. 拿堆的根节点和最后一个节点交换。

由此可以见,对于包含 n 个数据元素的数组而言,堆排序需要经过 n-1 次建堆,每次建堆的作用就是选出该堆个最大值或最小值。因为堆排序的本质上依然是一种选择排序。

堆排序与直接选择排序的区别在于,堆排序可通过树形结构保存部分比较结果,可减少比较次数。对于直接选择排序而言,为了从 a1、a2、a3…an 中选出最小的数据,必须进行 n-1 次比较;然后在 a2、a3…an 中选出关键字最小的记录,又需要做 n-2 次比较。事实上,后面的 n-2 次比较中,有许多比较可能在前面的 n-1 次比较重已经做过,但由于前一趟排序时未保留这些比较结果,所以后一趟排序时又重复执行了这些比较操作。堆排序可通过树形结构来保存前面的部分比较结果,从而提高效率。

接下来的关键就是建堆的过程。建堆其实比较简单,不断重复如下步骤即可(以建大顶堆为例)。

从最后一个非叶子节点开始,比较该节点和它两个子节点的值;如果某个子节点的值大于父节点的,就把父节点和较大的子节点交换。

向前逐步调整直到根节点,即保证每个父节点的值都大于等于其左、右子节点的值,建堆完成。

例如有如下数据:9, 79, 46, 30, 58, 49。下面逐步介绍对其建堆的过程。

  1. 先将其转换为完全二叉树,转换得到的完全二叉树如下:

         9(0)
        /    \
     /          \
      79(1)        46(2)
      /    \      /
    30(3) 58(4) 49(5)
  2. 完全二叉树的最后一个非叶子节点,也就是最后一个节点的父节点。最后一个节点的索引为 数组长度-1,也就是 len-1,那么最后一个非叶子节点的索引应该是为 (len-2)/2。也就是从索引为 2 的节点开始,如果其子节点的值大于它本身的值,则把它和较大子节点进行交换,即将索引 2 处节点和索引 5 处的元素进行交换,交换后的结果如下所示:

         9(0)
        /    \
     /          \
      79(1)        49(2)
      /    \      /
    30(3) 58(4) 46(5)
    建堆从最后一个非叶子节点开始即可,因为只要保证每个非叶子节点的值大于等于其左、右子节点的值。
  3. 向前处理前一个节点,也就是索引为 1 的节点,此时 79>30、79>58,因此无需交换。
  4. 向前处理前一个节点,也就是处理索引为 0 的节点,此时 9<79、9<58,因此需要交换。应该拿索引 0 的节点和索引 1 的节点交换 (9 的两个子节点中,索引为 1 的节点的值交大),交换后的完全二叉树如下所示:

         79(0)
        /    \
     /          \
      9(1)        49(2)
      /    \      /
    30(3) 58(4) 46(5)
  5. 如果某个节点和它的某个子节点交换后,该子节点又有子节点,系统还需要再次堆该子节点进行判断。例如,在上面的步骤中索引 0 的节点和索引 1 的节点交换后,索引 1 的节点还有子节点,因此程序必须再次保证索引 1 处节点的值大于等于其左、右子节点的值。因此还需要交换依次,交换后的大顶堆如下:

         79(0)
        /    \
     /          \
      58(1)        49(2)
      /    \      /
    30(3) 9(4) 46(5)

下面程序实现了一个堆排序。

public class HeapSort {
    public static void heapSort(DataWrap[] data) {
        System.out.println("开始排序");
        int arrayLength = data.length;
        //循环建堆
        for (int i = 0;i < arrayLength - 1;i++) {
            //建堆
            buildMaxHeap(data, arrayLength - 1 - i);
            //交换堆顶和最后一个元素
            swap(data, 0, arrayLength - 1 - i);
            System.out.println(Arrays.toString(data));
        }
    }

    //对data数组从0到lastIndex建大顶堆
    private static void buildMaxHeap(DataWrap[] data, int lastIndex) {
        //从lastIndex处节点(最后一个节点)的父节点开始
        for (int i = (lastIndex - 1) / 2;i >= 0;i--) {
            //k保存当前正在判断的节点
            int k = i;
            //如果当前k节点的子节点存在
            while (k * 2 + 1 <= lastIndex) {
                //k节点的左子节点的索引
                int biggerIndex = 2 * k + 1;
                //如果binggerIndex小于lastIndex,即biggerIndex+1
                //代表的k节点的右子节点存在
                if (biggerIndex < lastIndex) {
                    //如果右子节点的值较大
                    if (data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0) {
                        //biggerIndex总是记录较大子节点的索引
                        biggerIndex++;
                    }
                }
                //如果k节点的值小于其较大子节点的值
                if (data[k].compareTo(data[biggerIndex]) < 0) {
                    //交换它们
                    swap(data, k, biggerIndex);
                    //将biggerIndex赋给k,开始while循环的下一次循环
                    //重新保证k节点的值大于其左、右子节点的值
                    k = biggerIndex;
                } else {
                    break;
                }
            }
        }
    }
    //交换data数组中i,j两个索引处的元素
    private static void swap(DataWrap[] data, int i, int j) {
        DataWrap tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
    public static void main(String[] args) {
        DataWrap[] data = {new DataWrap(21, ""),
                new DataWrap(30, ""),
                new DataWrap(49, ""),
                new DataWrap(30, "*"),
                new DataWrap(16, ""),
                new DataWrap(9, "")};
        System.out.println("排序之前:\n" + Arrays.toString(data));
        heapSort(data);
        System.out.println("排序之后:\n" + Arrays.toString(data));
    }
}

上面堆排序的关键在于 buildMaxHeap() 方法。该方便用于对 data 数组从 0 到 lastIndex 索引范围内的元素建大顶堆,这样就选择出数组索引从 0 到 lastIndex 范围的最大元素。采用循环不断重复上面过程即可完成堆排序。运行上面程序,可以看到如下结果。

排序之前:
[21, 30, 49, 30*, 16, 9]
开始排序
[9, 30, 21, 30*, 16, 49]
[16, 30*, 21, 9, 30, 49]
[9, 16, 21, 30*, 30, 49]
[9, 16, 21, 30*, 30, 49]
[9, 16, 21, 30*, 30, 49]
排序之后:
[9, 16, 21, 30*, 30, 49]

对于堆排序而言,假设有 n 项数据,需要进行 n-1 次建堆,每次建堆本身耗时为 log2(n),则其时间效率为 O(nlog2(n))。

堆排序蒜贩空间效率很高,它只需要一个附加程序单元用于交换,其空间效率为 O(1)。

堆排序是不稳定的。

交换排序

交换排序的主体操作是对数据租中的数据不断进行交换操作。交换排序主要有冒泡排序和快速排序,这两种排序都是广为人知且应用极广的排序算法。

有人认为,所有排序算法都应该可称为可交换排序,因为所有排序算法里都会包含前面的 swap() 方法或其中代码。这个说法有一半是堆的,既然要对数据进行排序,所以肯定要进行数据交换,但并不代表所有排序都是交换排序。交换排序的绝大部分操作都是交换,但对于前面的直接选择、堆排序而言,它们的主要操作是不断地选择,所以将它们归为选择排序。

冒泡排序

冒泡排序是最广为人知的交换排序之一,它具有算法思路简单、容易实现的特点。

对于一组包含 n 个数组的的一组记录,最坏的情况下,冒泡排序需要进行 n-1 趟比较。

第 1 趟:依次比较 0 和 1、1 和 2、2 和 3……n-2 和 n-1 索引的元素,如果发现第一个数据是大于后一个数据,交换它们。经过第 1 趟,最大的元素排到了最后。

第 1 趟:依次比较 0 和 1、1 和 2、2 和 3……n-3 和 n-2 索引的元素,如果发现第一个数据是大于后一个数据,交换它们。经过第 2 趟,第 2 大的元素排到了倒数第 2 位。

……

第 n-1 趟:依次比较 0 和 1元素,如果发现第一个数据是大于后一个数据,交换它们。经过第 n-1 趟,第 2 小的元素排到了第 2 位。

实际上,冒泡排序的每趟交换结束后,不仅能将当前最大值挤出最后面的位置,还能部分理顺前面其它元素;一旦某趟没有交换发生,即可提前结束排序。

假设有如下数据序列,2, 16, 21*, 23, 30, 49, 21, 30*。只需要经过如下几趟排序。
第 1 趟:9, 16, 21*, 23, 30, 21, 30*, 49
第 2 趟:9, 16, 21*, 23, 21, 30, 30*, 49
第 3 趟:9, 16, 21*, 21, 23, 30, 30*, 49
第 4 趟:9, 16, 21*, 21, 23, 30, 30*, 49

从上面排序过程可以看出,虽然上面该组数组包含了 8 个元素,但采用冒泡排序只需要经过 4 次比较。因为经过第 3 趟排序后,这组数据已经处于有序状态,这样,第 4 趟将不会发生囧啊换,因此可以提前结束循环。

冒泡排序的示例程序如下。

public class BubbleSort {
    public static void bubbleSort(DataWrap[] data) {
        System.out.println("开始排序");
        int arrayLength = data.length;
        for (int i = 0;i < arrayLength - 1;i++) {
            boolean flag = false;
            for (int j = 0;j < arrayLength - 1 - i;j++) {
                //如果j索引处的元素大于j+1索引处的元素
                if (data[j].compareTo(data[j + 1]) > 0) {
                    //交换它们
                    DataWrap tmp = data[j + 1];
                    data[j + 1] = data[j];
                    data[j] = tmp;
                    flag = true;
                }
            }
            System.out.println(Arrays.toString(data));
            //如果某趟没有发生交换,则表明已经处于有序状态
            if (!flag) {
                break;
            }
        }
    }
    public static void main(String[] args) {
        DataWrap[] data = {new DataWrap(21, ""),
                new DataWrap(30, ""),
                new DataWrap(49, ""),
                new DataWrap(30, "*"),
                new DataWrap(16, ""),
                new DataWrap(9, "")};
        System.out.println("排序之前:\n" + Arrays.toString(data));
        bubbleSort(data);
        System.out.println("排序之后:\n" + Arrays.toString(data));
    }
}

运行上面程序之后,激昂会看到如下的结果。

排序之前:
[21, 30, 49, 30*, 16, 9]
开始排序
[21, 30, 30*, 16, 9, 49]
[21, 30, 16, 9, 30*, 49]
[21, 16, 9, 30, 30*, 49]
[16, 9, 21, 30, 30*, 49]
[9, 16, 21, 30, 30*, 49]
排序之后:
[9, 16, 21, 30, 30*, 49]

对于冒泡排序而言的时间效率是不确定的:最好的情况下,初始数据序列已经处于有序状态,执行 1 趟冒泡即可,做 n-1 次比较,无需进行任何交换;但在最坏的情况下,初始数据处于完全逆序,蒜贩要执行 n-1 趟冒泡,第 i 趟(1<i<n)做了 n-i 次比较,执行n-i-1 次对象交换。此时的比较总次数为 n*(n-1)/2,记录移动总次数为 n*(n-1)*3/2。

冒泡排序算法空间效率很高,它只需要一个附加程序单元用于交换,其空间效率为 O(1)。

冒泡排序是稳定的。

快速排序

快速排序是一个速度非常快的交换排序方法,它的基本思路很简单:从待排的数据序列中任取一个元素(如第一个元素)作为分界值,所有比它小的数据元素一律放到左边,所有比它大的数据元素一律放到右边。这样经过一趟下来,该序列形成了左右两个子序列,左边序列中数据元素的值都比分界值小,右边序列中数据元素的都比分界值大。

接下来堆左、右两个子序列进行递归,堆两个子序列重新选择中心元素并依此规则调整,直到每个子表的元素只剩一个,排序完成。

从上面算法分析可以看出,实现快速排序的关键在于第一趟要做的事情,如下所示。

  1. 选出指定的分界值——这个很容易完成;
  2. 将所有比分界值小的数据元素放在左边;
  3. 将所有比分界值大的数据元素放在右边。

现在的问题是:如何实现上面的 2、3步骤?这个时候就要用到交换了,思路如下。

  1. 定义一个 i 变量从左边第一个索引开始,找大于分界值的元素的索引,并用 i 来记录它;
  2. 定义一个 j 变量从右边第一个索引开始,找小于分界值的元素的索引,并用 j 来记录它;
  3. 如果 i < j,交换 i、j 两个索引处的元素;

重复执行以上 1、2、3 步,直到 i >= j,可以判断 j 左边的数据元素都小于分界值,j 右边的元素都大于分界值,最后将分界值和 j 索引处的元素交换即可。

接下来实现开始排序,程序如下。

public class QuickSort {
    //将指定数组的i和j索引处的元素交换
    private static void swap(DataWrap[] data, int i, int j) {
        DataWrap tmp = data[i];
        data[i] = data[j];
        data[j] = tmp;
    }
    //对data数组中从start~end索引范围的子序列进行处理
    //使之满足所有小于分界值的放在左边,所有大于分界值的放在右边
    private static void subSort(DataWrap[] data, int start, int end) {
        //需要排序
        if (start < end) {
            //以第一个元素作为分界值
            DataWrap base = data[start];
            //i从左边开始搜索,搜索大于分界值的元素的索引
            int i = start;
            //j从右边开始搜索,搜索小于分界值的元素的索引
            int j = end;
            while (true) {
                //找到大于分界值的元素的索引,或者i已经到了end处
                while (i < end && data[i].compareTo(base) <= 0) {
                    i++;
                }
                //找到小于分界值的元素的索引,或者j已经到了start处
                while (j > start && data[j].compareTo(base) >= 0) {
                    j--;
                }
                if (i < j) {
                    swap(data, i, j);
                } else {
                    break;
                }
            }
            swap(data, start, j);
            //递归左子序列
            subSort(data, start, j - 1);
            //递归右子序列
            subSort(data, j + 1, end);
        }
    }
    public static void quickSort(DataWrap[] data) {
        subSort(data, 0, data.length - 1);
    }
    public static void main(String[] args) {
        DataWrap[] data = {new DataWrap(9, ""),
                new DataWrap(-16, ""),
                new DataWrap(21, "*"),
                new DataWrap(23, ""),
                new DataWrap(-30, ""),
                new DataWrap(-49, ""),
                new DataWrap(21, ""),
                new DataWrap(30, "*"),
                new DataWrap(13, "*")};
        System.out.println("排序之前:\n" + Arrays.toString(data));
        quickSort(data);
        System.out.println("排序之后:\n" + Arrays.toString(data));
    }
}

快速排序的时间效率很好,因为它每趟没确定的元素呈指数增长。

快速排序需要使用递归,而递归使用栈,因此它的空间效率为 O(log2(n))。

快速排序中包含跳跃式交换,因此是不稳定的排序算法。

插入排序

插入排序也是一类常见的排序方法,它主要包含直接插入、Shell 插入和折半插入等几种常见的排序方法。

直接插入排序

直接插入排序的思路非常简单:依次将待排序的数据元素按其关键字值的大小插入前面的有序序列。

细化来说,对于一个有 n 个元素数据序列,排序需要进行 n-1 趟插入操作,如下所示。
第 1 趟插入:将第 2 个元素插入的有序子序列——此时前面只有一个元素,当然是有序的。
第 2 趟插入:将第 3 个元素插入前面的有序子序列,前面 2 个元素都是有序的。
……
第 n-1 趟插入:将第 n 个元素插入前面的有序子序列,前面 n-1 个元素都是有序的。

掌握上面商品思路之后,如下代码实现了直接插入排序。

public class InsetSort {
    public static void insertSort(DataWrap[] data) {
        System.out.println("开始排序:\n");
        int arrayLength = data.length;
        for (int i = 1;i < arrayLength;i++) {
            //当整体后移时,保证data[i]的值不会丢失
            DataWrap tmp = data[i];
            //i索引处的值已经比前面所有值都大,表名已经有序,无需插入
            //(i-1 索引之前的数据已经是有序的,i-1 索引处元素的值就是最大值)
            if (data[i].compareTo(data[i - 1]) < 0) {
                int j = i - 1;
                for (;j >= 0 && data[j].compareTo(tmp) > 0;j--) {
                    data[j + 1] = data[j];
                }
                //最后将tmp值插入合适位置
                data[j + 1] = tmp;
            }
            System.out.println(Arrays.toString(data));
        }
    }
    public static void main(String[] args) {
        DataWrap[] data = {new DataWrap(9, ""),
                new DataWrap(-16, ""),
                new DataWrap(21, "*"),
                new DataWrap(23, ""),
                new DataWrap(-30, ""),
                new DataWrap(-49, ""),
                new DataWrap(21, ""),
                new DataWrap(30, "*"),
                new DataWrap(30, "")};
        System.out.println("排序之前:\n" + Arrays.toString(data));
        insertSort(data);
        System.out.println("排序之后:\n" + Arrays.toString(data));
    }
}

运行上面程序,将显示如下结果。

排序之前:
[9, -16, 21*, 23, -30, -49, 21, 30*, 30]
开始排序:

[-16, 9, 21*, 23, -30, -49, 21, 30*, 30]
[-16, 9, 21*, 23, -30, -49, 21, 30*, 30]
[-16, 9, 21*, 23, -30, -49, 21, 30*, 30]
[-30, -16, 9, 21*, 23, -49, 21, 30*, 30]
[-49, -30, -16, 9, 21*, 23, 21, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
排序之后:
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]

直接插入的时间效率并不高,如果在最坏的情况下,所有元素的比较次数总和为 (0+1+…+n-1)=O(n^2)。其它情况下也要考虑移动元素的次数,故时间复杂度为 O(n^2)。

直接插入空间效率很好,它只需要 1 个缓存数据单元,也就是说空间效率为 O(1)。

直接插入排序是稳定的。

折半插入排序

折半插入排序是对直接插入排序的简单改进。对于简单插入排序而言,当第 i-1 趟需要将第 i 个元素插入前面的 0~i-1 个元素序列中时,它总是从 i-1 个元素开始,逐个比较每个元素,知道找到它的位置。这显然没有利用前面 0~i-1 个元素已经有序的这个特点,而折半插入排序则改进了这一点。

对于折半插入排序而言,当第 i-1 趟需要将 i 个元素插入前面的 0~i-1 个元素序列中时,它不会直接从 i-1 个元素开始逐个比较每个元素。折半插入排序的做法如下。

  1. 计算 0~i-1 索引的中间点,也就是用 i 索引处的元素和 (0+i-1)/2 索引处的元素进行比较,如果 i 索引处的元素大,就直接在 (0+i-1)/2~i-1 半个范围内搜索;反之,就在 0~(0+i-1)/2 半个范围内搜索,这就是所谓的折半。
  2. 在半个范围内搜索时,再按第 1 步方法进行折半搜索。总是不断的折半,这样就可以将搜索范围缩小到 1/2、1/4、1/8,从而快速确定第 i 个元素的插入位置。

    此处介绍的折半插入,其实就是通过不断地折半来快速确定第 i 个元素的插入位置,这实际上是一种查找算法——折半查找。Java 的 Arrays 类里有一个 binarySearch() 方法,它就是一个折半查找的实现,它用于从指定数组(或数组的一部分)中查找指定元素,前提是该数组(或者数组的一部分)已经处于有序状态。
  3. 一旦确定了第 i 个元素的插入位置,剩下的事情就简单多了。程序将该位置以后的元素整体后移动一位,然后将第 i 个元素放入该位置。

下面代码实现了一个折半插入排序。

public class BinaryInsertSort {
    public static void binaryInsertSort(DataWrap[] data) {
        System.out.println("开始排序:\n");
        int arrayLength = data.length;
        for (int i = 1;i < arrayLength;i++) {
            //当整体后移时,保证 data[i]的值不会丢失
            DataWrap tmp = data[i];
            int low = 0;
            int high = i - 1;
            while (low <= high) {
                //找出low、high中间的索引
                int mid = (low + high) / 2;
                //如果tmp值大于low、high中间元素的值
                if (tmp.compareTo(data[mid]) > 0) {
                    //限制在索引大于mid的那一半搜索
                    low = mid + 1;
                } else {
                    //限制在索引小于mid的那一半搜索
                    high = mid - 1;
                }
            }
            //将low到i处的所有元素向后整体移一位
            for (int j = i;j > low;j--) {
                data[j] = data[j - 1];
            }
            //最后将tmp的值插入合适位置
            data[low] = tmp;
            System.out.println(Arrays.toString(data));
        }
    }
    public static void main(String[] args) {
        DataWrap[] data = {new DataWrap(9, ""),
                new DataWrap(-16, ""),
                new DataWrap(21, "*"),
                new DataWrap(23, ""),
                new DataWrap(-30, ""),
                new DataWrap(-49, ""),
                new DataWrap(21, ""),
                new DataWrap(30, "*"),
                new DataWrap(30, "")};
        System.out.println("排序之前:\n" + Arrays.toString(data));
        binaryInsertSort(data);
        System.out.println("排序之后:\n" + Arrays.toString(data));
    }
}

在上面的程序中,会拿 tmp 的值和 mid 索引(就是中间索引)处的值进行比较,如果 tmp 大于 mid 索引处的元素,将 low(搜索范围的下限)设置为 mid+1,即表明到 mid+1~原 high 范围内的搜索;反之,将 high (搜索范围的上限)设置为 mid-1,即表明到原 low~mid-1 范围内搜索。

上面程序的排序效果与简单插入排序的效果基本相同,只是更快一些,因为折半插入排序可以更快地确定第 i 个元素的插入位置。

Shell 排序

Shell 排序由 Donald L. Shell 于 1959 年发现,该排序算法其实是以其名字命名的。

于直接插入排序而言,当擦汗如排序执行到一半时,待插值左边的所有数据都已经处于有序状态,直接插入排序将待插值储存在一个临时变量里。然后,从待插值左边第一个数据单元开始,只要该数据单元的值大于待插值,该数据单元就右移一格,直到找到第一个小于待插值的数据单元。接下来,将临时变量里的值放入小于待插值的数据单元之后(前面所有数据都右移过一格,因此该数据单元有一个空格)。

从上面算法可以发现一个问题:如果一个很小的数据单元位于很靠近右端的位置上,为了把这个数据单元移动到左边正确的位置上,中间所有的数据单元都需要向右移动一格。这个步骤堆每一个数据项都执行了近 N 次的赋值。虽不是所有数据项都必须移动 N 个位置,平均下来,每个数据项都会移动 N/2 格,总该是 (N^2)/2 次复制。因此,插入排序的执行效率是 O(N^2)。

Shell 排序对直接插入排序进行了简单改进:它通过加大插入排序中元素之间的间隔,并在这些间隔的元素中进行插入排序,从而使数据项大幅度地移动。当这些数据项排过一趟序后,Shell 排序算法减小数据项的间隔再进行排序,依次进行下去。进行这些排序时的数据项之间的间隔被称为增量,习惯上用字母 h 来表示这个增量。

下面以如下数据序列为例,进行说明。
9, -16, 21*, 23, -30, -49, 21, 30*, 30
如果采用直接插入排序,第 i 趟插入会将第 i+1 个元素插入前面的有序序列中,将看到:
-16, 9, 21*, 23, -30, -49, 21, 30*, 30——第 1 趟,将第 2 个元素插入,前 2 个元素有序;
-16, 9, 21*, 23, -30, -49, 21, 30*, 30——第 2 趟,将第 3 个元素插入,前 3 个元素有序;
……

Shell 排序就不这样了。假设本次 Shell 排序的 h 为 4,其插入操作如下。
-30, -16, 21*, 23, 9, -49, 21, 30*, 30
-30, -49, 21*, 23, 9, -16, 21, 30*, 30
-30, -49, 21*, 23, 9, -16, 21, 30*, 30
-30, -49, 21*, 23, 9, -16, 21, 30*, 30
-30, -49, 21*, 23, 9, -16, 21, 30*, 30

注意上面排序过程中的粗体字代码。

当 h 增量为 4,第 i 趟将保证索引为 0、4、8 的数据元素已经有序。第 1 趟完成后,算法向右移一步,对索引为 1、5 的数据元素进行排序。这个排序过程持续进行,直到所有数据项都已经完成以 4 为增量的排序。也就是说,所有间隔为 4 的数据项之间都已经排列有序。

当完成以 4 为增量的 Shell 排序后,所有元素离它在最终有序序列中的位置相差不到 2 个单元,这就是数组“基本有序”的含义,也正是 Shell 排序的奥秘所在。通过创建这种交错的内部有序的数据项集合,就可以减少直接插入排序中数据项“整体搬家”的工作量。

上面已经演示了以 4 为增量的 Shell 排序,接下来应该减少增量,直到完成以 1 为增量的 Shell 排序,此时数据序列将会变为有序。

通过上面介绍不难发现,可以认为直接插入排序是 Shell 排序的一种特征——直接使用增量为 1 的 Shell 排序就是直接插入排序。

从上面介绍可知,最终确定 Shell 排序算法的关键就在于确定 h 序列的值。常用的 h 序列由 Knuth 提出,该序列从 1 开始,通过如下公式产生。
h = 3 * h + 1

上面公式用于从 1 开始计算这个序列,可以看到 h 序列为 1、4、13、40……。反过来,程序中还需要反向计算 h 序列,那应该使用如下公式。
h = (h - 1) / 3

上面公式从最大的 h 开始计算,假设 h 从 40 开始,可以看到 h 序列为 40、13、4、1。

Shell 排序笔插入排序快很多,因为当 h 值大的时候,数据项每一趟排序需要移动元素的个数很少,但数据项移动的距离很长,这是非常有效率的。当 h 减少时,每一趟排序需要移动的元素的个数增多,但是此时数据项已经接近于它们排序后最终的位置,这对于排序可以更有效率。

正是这两种情况结合才使 Shell 排序效率那么高。

下面程序实现了一个简单的 Shell 排序。

public class ShellSort {
    public static void shellSort(DataWrap[] data) {
        System.out.println("开始排序:");
        int arrayLength = data.length;
        //h变量保存可变增量
        int h = 1;
        //按h*3+1得到增量序列的最大值
        while (h <= arrayLength / 3) {
            h = h * 3 + 1;
        }
        while (h > 0) {
            System.out.println("===h 的值:" + h + "===");
            for (int i = h;i < arrayLength;i++) {
                //当整体后移时,保证data[i]的值不会丢失
                DataWrap tmp = data[i];
                //i索引处的值已经笔前面所有值都大,表明已经有序,无需插入
                //(i-1索引之前的数据已经有序的,i-1索引处元素的值就是最大值)
                if (data[i].compareTo(data[i - h]) < 0) {
                    int j = i - h;
                    //整体后移h格
                    for (;j >= 0 && data[j].compareTo(tmp) > 0;j -= h) {
                        data[j + h] = data[j];
                    }
                    //最后将tmp的值插入合适位置
                    data[j + h] = tmp;
                }
                System.out.println(Arrays.toString(data));
            }
            h = (h - 1) / 3;
        }
    }
    public static void main(String[] args) {
        DataWrap[] data = {new DataWrap(9, ""),
                new DataWrap(-16, ""),
                new DataWrap(21, "*"),
                new DataWrap(23, ""),
                new DataWrap(-30, ""),
                new DataWrap(-49, ""),
                new DataWrap(21, ""),
                new DataWrap(30, "*"),
                new DataWrap(30, "")};
        System.out.println("排序之前:\n" + Arrays.toString(data));
        shellSort(data);
        System.out.println("排序之后:\n" + Arrays.toString(data));
    }
}

上面代码于直接插入排序的差别在于:直接插入排序中的 h 会用 1 代替。这也证明了前面的理论:直接插入排序是直接以 1 为增量的 Shell 排序。

运行上面程序,可以看到如下结果。

排序之前:
[9, -16, 21*, 23, -30, -49, 21, 30*, 30]
开始排序:
===h 的值:4===
[-30, -16, 21*, 23, 9, -49, 21, 30*, 30]
[-30, -49, 21*, 23, 9, -16, 21, 30*, 30]
[-30, -49, 21*, 23, 9, -16, 21, 30*, 30]
[-30, -49, 21*, 23, 9, -16, 21, 30*, 30]
[-30, -49, 21*, 23, 9, -16, 21, 30*, 30]
===h 的值:1===
[-49, -30, 21*, 23, 9, -16, 21, 30*, 30]
[-49, -30, 21*, 23, 9, -16, 21, 30*, 30]
[-49, -30, 21*, 23, 9, -16, 21, 30*, 30]
[-49, -30, 9, 21*, 23, -16, 21, 30*, 30]
[-49, -30, -16, 9, 21*, 23, 21, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]
排序之后:
[-49, -30, -16, 9, 21*, 21, 23, 30*, 30]

Shell 排序是直接插入排序的改进版,因此它也是稳定的,它的空间开销也是 O(1),时间开销估计在 O(N3/2)~O(N7/6) 之间。

归并排序

归并基本思想是将两个(或以上)有序的序列合并成一个新的有序序列。当然,此处介绍的归并排序主要是将两个有序的数据序列合并成一个新的有序序列。

细化来说,归并排序先将长度为 n 的无序序列看成是 n 个长度为 1 的有序子序列,首先做两两合并,得到 n/2 个长度为 2 的有序子序列,再做两两合并……不断地重复这个过程,最终可以得到一个长度为 n 的有序序列。

“归并”这个名字也是早期由计算机专家翻译出来的,可以说它其实是一个生造词,往往给初学者制造很大的障碍。“归并”由 merg 翻译二来,merge 一般翻译为合并。从这个角度来说,归并排序应该翻译为“合并排序”,因为这种排序方法的关键就在于合并。

假设有如下数据序列,21, 30, 49, 30*, 97, 62, 72, 08, 37, 16, 54。

长度为 16 的数据序列,只需经过 4 次合并。也就是说,对于长度为 n 的数据序列,只需要经过 log2(n) 次合并。

对于归并排序而言,其算法关键就在“合并”。如何将两个有序的数据序列合并成一个新的有序序列?合并算法的具体步骤如下。

  1. 定义变量 i,i 从 0 开始,依次等于 A 序列中每个元素的索引。
  2. 定义变量 j,j 从 0 开始,依次等于 B 序列中每个元素的索引。
  3. 拿 A 序列中 i 索引处元素和 B 序列中 j 索引处的元素进行比较,将较小的复制到一个临时数组中。
  4. 如果 i 索引处的元素小,i++;如果 j 索引处的元素小,j++。

不断地重复上面 4 个步骤,即可将 A、B 两个序列中的数据元素复制到临时数组中,知道其中一个数组中的所有元素都被复制到临时数组中。最后,再将另一个数组中多出来的元素全部复制到临时数组中,合并即完成,再将临时数组中数据复制回去即可。

掌握了归并排序的理论之后,接下来使用如下 Java 程序来实现归并排序。

package com.yeskery.sort.merge;

import java.util.Arrays;

/**
 * @author yeskery
 * @date 2018/05/03
 */
class DataWrap implements Comparable<DataWrap> {
    int data;
    String flag;
    public DataWrap(int data, String flag) {
        this.data = data;
        this.flag = flag;
    }

    @Override
    public String toString() {
        return data + flag;
    }
    //根据data实例变量来决定两个DataWrap的大小
    @Override
    public int compareTo(DataWrap dw) {
        return this.data > dw.data ? 1 : (this.data == dw.data ? 0 : -1);
    }
}
public class MergeSort {
    //利用归并排序算法对数组data进行排序
    public static void mergeSort(DataWrap[] data) {
        //归并排序
        sort(data, 0, data.length - 1);
    }
    /**
     * 将索引从left到right范围的数组元素进行归并排序
     * @param data 待排序的数组
     * @param left 待排序的数组的第一个元素索引
     * @param right 待排序的数组的最后一个元素索引
     */
    private static void sort(DataWrap[] data, int left, int right) {
        if (left < right) {
            //找出中间索引
            int center = (left + right) / 2;
            //对左边数组进行递归
            sort(data, left, center);
            //对右边数组进行递归
            sort(data, center + 1, right);
            //合并
            merge(data, left, center, right);
        }
    }
    /**
     * 将两个数组进行归并,归并前两个数组已经有序,归并后依然有序
     * @param data 数组对象
     * @param left 左数组的第一个元素的索引
     * @param center 左数组的最后一个元素的索引,center+1是右数组第一个元素的索引
     * @param right 右数组的最后一个元素的索引
     */
    private static void merge(DataWrap[] data, int left, int center, int right) {
        DataWrap[] tmpArr = new DataWrap[data.length];
        int mid = center + 1;
        //third记录中间数组的索引
        int third = left;
        int tmp = left;
        while (left <= center && mid <= right) {
            //从两个数组中取出小的放入中间数组
            if (data[left].compareTo(data[mid]) <= 0) {
                tmpArr[third++] = data[left++];
            } else {
                tmpArr[third++] = data[mid++];
            }
        }
        //剩余部分依次放入中间数组
        while (mid <= right) {
            tmpArr[third++] = data[mid++];
        }
        while (left <= center) {
            tmpArr[third++] = data[left++];
        }
        //将中间数组的内容复制拷回原数组
        //原left~right范围的内容被复制回原数组
        while (tmp < right) {
            data[tmp] = tmpArr[tmp++];
        }
    }
    public static void main(String[] args) {
        DataWrap[] data = {new DataWrap(9, ""),
                new DataWrap(-16, ""),
                new DataWrap(21, "*"),
                new DataWrap(23, ""),
                new DataWrap(-30, ""),
                new DataWrap(-49, ""),
                new DataWrap(21, ""),
                new DataWrap(30, "*"),
                new DataWrap(30, "")};
        System.out.println("排序之前:\n" + Arrays.toString(data));
        mergeSort(data);
        System.out.println("排序之后:\n" + Arrays.toString(data));
    }
}

从上面算法实现可以看出,归并算法需要递归地进行分解、合并,每进行一趟两路归并排序需要调用 merge() 方法一次,每次执行 merge 方法需要比较 n 次,因此归并排序算法时间复杂度为 O(nlog2(n))。

归并排序算法的空间效率较差,它需要一个与原始序列同样大小的辅助序列。

归并排序算法是稳定的,

桶式排序

桶式排序不再是一种基于比较的排序方法,它是一种非常巧妙的排序方式,但这种排序方式需要待排序列满足两个特征:

  • 待排序列的所有值处于一个可枚举范围内;
  • 待排序列所在的这个可枚举范围不应该太大,否则排序开销太大。

下载介绍桶式的详细过程,以如下待排序列为例。5、4、2、4、1,这个待排序列处于 0、1、2、3、4、5 这个可枚举范围内,而且这个范围也很小,正是桶式排序待派用场之时。

具体步骤如下:

  1. 对这个可枚举范围构建一个 buckets 数组,用于记录“落入”每个桶中的元素的个数,如下:
0 1 2 3 4 5 //可枚举范围
0 1 1 0 2 1 //buckets数组
  1. 对上面所示的 buckets 数组的元素进行重新结算,按如下公式进行重新结算。buckets[i] = buckets[i] + buckets[i - 1](其中1 <= i < buckets.length)。
原buckets数组:
0 1 2 3 4 5 //可枚举范围
0 1 1 0 2 1 //buckets数组

新buckets数组:
0 1 2 3 4 5 //可枚举范围
0 1 2 2 4 5 //buckets数组

重新计算后的 buckets 数组元素保存了“落入”当前桶和“落入”前面所有桶中元素的总数目,而且定义的桶本身就是从小到达排列的,也就是说,“落入”前面桶的元素肯定小于“落入”当前桶的元素。综合上面两点,得到一个结论:每个 buckets 数组元素的值小于、等于“落入”当前桶中元素的个数。也就是说,“落入”当前桶中的元素在有序序列应该排在 buckets 数组元素值所确定的位置。

上面理论还有点抽象。以待排序列中最后一个元素 1 为例,找到新 buckets 数组中元素 1 对应桶的值,该值为 1,这表明元素 1 就应该排在第 1 位;再以待排序列中倒数第 2 个元素 4 为例,找到新 buckets 数组中元素 4 对应桶的值,该值为 4,这表明元素 4 就应该排在第 4 位…………一次类推。

下面程序实现了桶式排序。

public class BucketSort {
    
    public static void bucketSort(DataWrap[] data, int min, int max) {
        System.out.println("开始排序:");
        //arrayLength记录待排序数组的长度
        int arrayLength = data.length;
        DataWrap[] tmp = new DataWrap[arrayLength];
        //buckets数组相当于定义了max-min个桶
        //buckets数组用于记录待排序元素的信息
        int[] buckets = new int[max - min];
        //计算每个元素在序列出现的次数
        for (int i = 0;i < arrayLength;i++) {
            //buckets数组记录了DataWrap出现的次数
            buckets[data[i].data - min]++;
        }
        System.out.println(Arrays.toString(buckets));
        //计算“落入”各桶内的元素在有序序列中的位置
        for (int i = 1;i < max - min;i++) {
            //前一个bucket的值+当前bucket的值=当前bucket新的值
            buckets[i] = buckets[i] + buckets[i - 1];
        }
        //循环结束后,buckets数组元素记录了“落入”前面所有桶和
        //“落入”当前bucket中元素的总数
        //也就是说,buckets数组元素的值代表了“落入”当前桶的元素在有序序列中的位置
        System.out.println(Arrays.toString(buckets));
        //将data数组中数据完全复制到tmp数组中缓存起来
        System.arraycopy(data, 0, tmp, 0, arrayLength);
        //根据buckets数组中的信息将待排序列的各元素放入对应的位置
        for (int k = arrayLength - 1;k >= 0;k--) {
            data[--buckets[tmp[k].data - min]] = tmp[k];
        }
    }
    public static void main(String[] args) {
        DataWrap[] data = {new DataWrap(9, ""), new DataWrap(5, ""),
                new DataWrap(-1, ""), new DataWrap(8, ""), new DataWrap(5, "*"),
                new DataWrap(7, ""), new DataWrap(3, ""), new DataWrap(-3, ""),
                new DataWrap(1, ""), new DataWrap(3, "*")};
        System.out.println("排序之前:\n" + Arrays.toString(data));
        bucketSort(data, -3, 10);
        System.out.println("排序之后:\n" + Arrays.toString(data));
    }
}

运行的结果如下:

排序之前:
[9, 5, -1, 8, 5*, 7, 3, -3, 1, 3*]
开始排序:
[1, 0, 1, 0, 1, 0, 2, 0, 2, 0, 1, 1, 1]
[1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 8, 9, 10]
排序之后:
[-3, -1, 1, 3, 3*, 5, 5*, 7, 8, 9]

桶式排序是一种非常优秀的排序算法,时间效率极高,它只需要经过 2 轮遍历:第 1 轮遍历待排数据,统计每个待排数据“落入”各桶中的个数;第 2 轮遍历用于重新计算每个 buckets 数组元素的值。2 轮遍历后就可得到每个待排数据在有序序列中的位置,然后将各个数据项一次放入指定位置即可。

桶式排序的空间开销较大,它需要两个数组:第 1 个 buckets 数组用于记录“落入”各桶中元素的个数,进而保存各元素在有序序列中的位置;第 2 个数组用于缓存待排数据。

桶式排序是稳定的。

基数排序

基数排序已经不再是一种常规排序方法,它更多地像一种排序方法的应用,基数排序必须依赖于另外的排序方法。基数排序的总体思路就是将待排序数据拆分成多个关键词进行排序,也就是说,基数排序的实质是多关键字排序。

多关键字排序的思路是将待排数据里的排序关键字拆分成多个排序关键字:第 1 子关键字、第 2 子关键字、第 3 子关键字…………然后,根据子关键字对待排数据进行排序。

多关键字排序时有两种解决方案:

  • 最高为优先法 MSD(Most Significant Digit first);
  • 最低位优先法 LSD(Least Significant Digit first)。

例如,对如下数据进行排序。192, 221, 13, 23,可以观察到它每个数据至多只有 3 位,因此可以将每个数据拆分成 3 个关键字:百位(高位)、十位、个位(低位)。

如果按照习惯思维,会先比较百位,百位大的数据大;百位相同的再比较十位,十位大的数据大;最后再比较个位。人的习惯思维是最高位优先方式。

如果按照人的思维方式,计算机实现起来有一定困难,当开始比较十位时,程序还需要判断它们的百位是否相同————这就人为的增加了难度。计算机通常会选择最低位优先法,如下所示。

第 1 轮先比较个位,对个位关键字排序后得到序列为:221, 192, 13, 23

第 2 轮再比较十位,对十位关键字排序后得到序列为:13, 23, 221, 192

第 2 轮再比较百位,对百位关键字排序后得到序列为:13, 23, 192, 221

从上面介绍可以看出:基数排序方法对任一子关键字排序时必须借助于另外一种排序方法,而且这种排序方法必须是稳定的。

如果这种排序算法不稳定,比如上面排序过程中,经过第 2 轮十位排序后,13 位于 23 之前,在第 3 轮百位排序时,如果该排序算法是稳定的,那么 13 依然位于 23 之前;如果该算法不稳定,那可能 13 跑到 23 之后,这将导致排序失败。

现在的问题是:对子关键字排序时,到底选择哪种排序方式更合适呢?答案是桶式排序。回顾桶式排序的两个要求:

  • 待排序列的所有值处于一个可枚举范围内;
  • 待排序列所在的这个可枚举范围不应该太大。

对于多关键字拆分出来的子关键字,它们一定位于 0~9 这个可枚举范围内,这个范围也不大,因此用桶式排序效率非常好。

下面以桶式排序为基础来实现多关键字的基数排序。

public class MultiKeyRadixSort {
    /**
     * 
     * @param data 待排序的数组
     * @param radix 指定关键字拆分的进制。如radix=10,表明按10进制拆分
     * @param d 指定将关键字拆分成几个子关键字
     */ 
    public static void radixSort(int[] data, int radix, int d) {
        System.out.println("开始排序");
        int arrayLength = data.length;
        //需要一个临时数组
        int[] tmp = new int[arrayLength];
        //buckets数组是桶式排序必须buckets数组
        int[] buckets = new int[radix];
        //以此从最高位的子关键字对待排序数据进行排序
        //下面循环中rate用于保存当前计算的位(比如十位时 rate=10)
        for (int i = 0,rate = 1;i < d;i++) {
            //重置count数组,开始统计第2个关键字
            Arrays.fill(buckets, 0);
            //将data数组的元素复制到temporary数组中进行缓存
            System.arraycopy(data, 0, tmp, 0, arrayLength);
            //计算每个待排序数据的子关键字
            for (int j = 0;j < arrayLength;j++) {
                //计算数据指定位上的子关键字
                int subKey = (tmp[j]/rate) % radix;
                buckets[subKey]++;
            }
            for (int j = 1;j < radix;j++) {
                buckets[j] = buckets[j] + buckets[j - 1];
            }
            //按子关键字对指定数据进行排序
            for (int m = arrayLength - 1;m >= 0;m--) {
                int subKey = (tmp[m]/rate) % radix;
                data[--buckets[subKey]] = tmp[m];
            }
            System.out.println("对" + rate + "位上子关键字排序:" + Arrays.toString(data));
            rate *= radix;
        }
    }
    public static void main(String[] args) {
        int[] data = {1100, 192, 221, 12, 13};
        System.out.println("排序之前:\n" + Arrays.toString(data));
        radixSort(data, 10, 4);
        System.out.println("排序之后:\n" + Arrays.toString(data));
    }
}

上面的基数排序其实就是多轮桶式排序而已,程序从最低位到最高位依次对待排数据进行排序,最后即可得到有序序列。运行上面程序,可以得到如下的结果。

排序之前:
[1100, 192, 221, 12, 13]
开始排序
对1位上子关键字排序:[1100, 221, 192, 12, 13]
对10位上子关键字排序:[1100, 12, 13, 221, 192]
对100位上子关键字排序:[12, 13, 1100, 192, 221]
对1000位上子关键字排序:[12, 13, 192, 221, 1100]
排序之后:
[12, 13, 192, 221, 1100]
对于多关键字排序来说,程序将待排数据拆分成多个子关键字后,对于关键字排序既可使用桶式排序,一颗使用任何一种稳定的排序方法。

本文转载自:《疯狂Java 突破程序员基本功的16课》第十二章 常用的内部排序