《算法导论》学习笔记——计数排序

计数排序

1.计数排序原理

  前面所涉及的插入排序、归并排序、堆排序、快速排序等算法都具有这样一个性质：在排序的最终结果中，各元素的次序依赖于它们之间的比较。因此我们将这类排序都称为比较排序。我们现在介绍新的三种排序：计数排序、基数排序和桶排序，这些算法是通过运算而不是比较来确定排序顺序的。这篇文章我们单讲计数排序。

  计数排序假设n个输入元素中的每一个都是在区间0到k内的整数，其中k为某一整数。当k = O(n)时，排序运行时间近似为O(n)。计数排序的思想如下：对于每一个输入元素x，确定小于元素x的个数。利用这一信息就可以直接把x放到它在输出数组中的位置了。譬如假若有7个元素小于x，那么x就在输出数组数组的第18个位置上，如果有相同大小的元素。对这一方案微调即可。

  因此，在计数排序算法中，假设输入是一个数组A[1...n]，A.length = n。我们还需要两个数组：B[0...k]提供临时存储空间，C[1...n]存储排序的输入。伪代码如下（注：伪代码里面的数组B[]对应下面图示中的数组C[]，伪代码里面的数组C[]对应下面图示中的数组B[]）：

COUNT_SORT
    Let B[0...k] be a new array
    for i = 0 to k
        B[i] = 0
    for j = 1 to A.length
        B[A[j]] = B[A[j]] + 1
    // B[i] now contains the number of elements equal to i
    for i = i to k
        B[i] = B[i] + B[i - 1]
    //B[i] now contains the number of elements less than or equal to i
    for j = A.length down to 1
        C[B[A[j]]] = A[j]
        B[A[j]] = B[A[j]] - 1

  下图展示了计数排序的全过程。

  根据前面的叙述，可以得知计数排序的下界优于O(nlogn)，因为它并不是一个比较排序的算法，实际上，可以看到基数排序的算法中完全没有两个元素之间的比较，计数排序是根据输入元素的实际值来确定其在数组中的位置。

  计数排序的一个重要性质就是它是稳定的：据有相同值得元素在输出数组中的相对次序与他们在输入数组中的相对次序相同。也就是说，对两个大小相同的元素来说，在输入数组中先出现的元素，在输出数组中的次序也位于前面。一般来说，当进行排序的数组还附带卫星数据是这种稳定性就显得尤为重要，因此，计数排序经常会被用作基数排序算法的子过程，有关基数排序的算法我们在下一节论述。

2.代码实现(C,Java,Python)

  注意到数组下标是从0开始的，因此实现伪代码时一定要避免数组越界问题。

C

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int *array_a, *array_b, *array_c;

void count_sort(int length, int k) {
    int i;
    for(i = 0; i < k; i++)
        array_b[i] = 0;
    for(i = 0; i < length; i++)
        array_b[array_a[i]] += 1;
    for(i = 1; i < k; i++)
        array_b[i] += array_b[i - 1];
    for(i = length - 1; i >= 0; i--) {
        array_c[array_b[array_a[i]] - 1] = array_a[i];
        array_b[array_a[i]] -= 1;
    }
}


int main() {
    int length, k = 10, i;
    printf("Enter the lengrh of array: ");
    scanf("%d", &length);
    array_a = (int *)malloc(length * sizeof(int));
    array_b = (int *)malloc(k * sizeof(int));
    array_c = (int *)malloc(length * sizeof(int));
    srand((unsigned)time(NULL));
    for(i = 0; i < length; i++)
        array_a[i] = rand() % k;
    printf("The original array is:\n");
    for(i = 0; i < length; i++)
        printf("%d ", array_a[i]);
    printf("\n");
    count_sort(length, k);
    printf("The sorted array is:\n");
    for(i = 0; i < length; i++)
        printf("%d ", array_c[i]);
    free(array_a);
    free(array_b);
    free(array_c);
    return 0;
}

Java

import java.util.*;

public class CountSort{
    public static void display(Iterator<Integer> it){
        while (it.hasNext()){
            Integer element = it.next();
            System.out.print(element + " ");
        }
    }
    public static void main(String[] args){
        ArrayList<Integer> array = new ArrayList<Integer>();
        Scanner in = new Scanner(System.in);
        System.out.print("Enter the maximun number of the array: ");
        int max = in.nextInt();
        System.out.print("Enter the length of the array: ");
        int length = in.nextInt();
        Random rand = new Random();
        for (int i = 0; i < length; i++)
            array.add(rand.nextInt(max));
        in.close();
        display(array.iterator());
        System.out.println();
        Sort sort = new Sort(array);
        array = sort.countSort(max, length);
        display(array.iterator());
    }
}

class Sort{
    public Sort(ArrayList<Integer> array){
        this.array_a = array;
        this.array_b = new ArrayList<Integer>();
        this.array_c = new ArrayList<Integer>();
    }

    public ArrayList<Integer> countSort(int max, int length){
        for (int i = 0; i < max; i++)
            array_b.add(0);
        for (int i = 0; i < length; i++){
            array_b.set(array_a.get(i), array_b.get(array_a.get(i)) + 1);
            array_c.add(0);
        }
        for (int i = 1; i < max; i++)
            array_b.set(i, array_b.get(i) + array_b.get(i - 1));
        for (int i = length - 1; i >= 0; i--){
            array_c.set(array_b.get(array_a.get(i)) - 1, array_a.get(i));
            array_b.set(array_a.get(i), array_b.get(array_a.get(i)) - 1);
        }
        return array_c;
    }


    private ArrayList<Integer> array_a;
    private ArrayList<Integer> array_b;
    private ArrayList<Integer> array_c;
}

Python

countSort.py

import random

def countSort(maximum, length):
    array_a = [random.randint(0, maximum - 1) for i in range(0, length)]
    array_b = [0] * maximum
    array_c = [0] * length
    print "The original array is " + str(array_a)
    for i in range(0, length):
        array_b[array_a[i]] += 1
    for i in range(1, maximum):
        array_b[i] += array_b[i - 1]
    for i in range(length - 1， -1， -1):
        array_c[array_b[array_a[i]] - 1] = array_a[i]
        array_b[array_a[i]] -= 1
    return array_c

test.py

import countSort

sortedArray = countSort.countSort(5, 10)
print "The sorted array is " + str(sortedArray)