排序算法之线性时间的排序和计数排序初识

一：概述

前面已经介绍了快速排序和堆排序。它们的时间复杂度都是O(nlogn)。在这篇博文中，要说明的是计数排序的初识和线性时间排序的介绍。

二：具体说明

<1>线性时间排序

例如冒泡排序。如下图所示，因为8>3，所以8和3位置互换。

例如堆排序。如下图所示，因为10>7，所以10和7位置交换。

注意：有些特殊的排序并不基于元素的比较，如计数排序、桶排序、基数排序。

<2>初识计数排序

假设数组中有20个随机整数，取值范围为0~10，要求用最快的速度把这个20个整数从小到大进行排序。如何排序呢？由于这些整数只能够在0、1、2、3、4、5、6、7、8、9、10这11个数中取值，取值范围有限。所以根据这些有限的范围，建立一个长度为11的数组。数组的下标是1~10,元素初始值全为0。

假设有一个20个随机整数的值，首先开始遍历这个无序的随机数列，每一个整数按照其值对号入座，同时，数组下标的元素进行加1操作。

例如第1个整数是9，那么数组的下标为9的元素+1.

第二个整数是3，那么数组下标为3的元素加1.

继续遍历数组并修改数组...

最终，当数组遍历完毕时，数组的装填如下：

该数组中每一个下标位置的值代表数列中对应整数出现的次数。有了这个统计结果，排序就很简单了。直接遍历数组，输出数组元素的下标值，元素值是几，就输出几次。

注意：计数排序它适用于一些范围内的整数排序。在取值范围内不是很大的情况下，它的性能甚至快过那些时间复杂度为O(nlogn)的排序。

<3>计数排序的代码实现

public static int[] countSort(int[] array) {

    // 1. 得到数列的最大值
    int max = array[0];
    for(int i = 1; i < array.length; i++) {
        if(array[i] > max) {
            max = array[i];
        }
    }
    // .2 根据数列的最大值确定统计数组的长度
    int[] countArray = new int[max + 1];
    // 3. 遍历数列，统计数组
    for(int i = 0; i < array.length; i++) {
        countArray[array[i]]++;
    }

     // 4. 遍历统计数组，输出结果
    int index = 0;
    int[] sortedArray = new int[array.length];
    for(int i = 0; i < countArray.length; i++) {
        for(int j = 0; j < countArray[i]; j++) {
            sortedArray[index++] = i;
        }
    }
    return sortedArray;
}


 public static  void main(String[] args) {
    int[] arr = new int[] {1, 3, 2, 6, 5, 7, 8, 9, 10, 0};
    countSort(arr);
    System.out.println(Arrays.toString(arr));

这段代码在开头有一个步骤，就是求数列的最大整数值max。后面创建的统计数组countArray,长度为max+1.以此来保证数组的最后一个下标是max。