计数排序算法图文详解

本节您将学习计数排序算法的工作原理，还会看到实现计数排序算法的 C、Java 以及 Python 程序。

计数排序算法是一种通过统计待排序序列中各个不同元素的出现次数，从而实现对整个序列进行排序的算法。

计数排序算法的工作原理

采用计数排序算法对 {4,2,2,8,3,3,1} 序列完成升序排序，需经历如下几个步骤：

1) 从序列中找到最大值。显然，该序列中的最大值为 8：

2) 初始化一个长度为 max+1、所有元素为 0 的数组（例如 count[max+1]），用于统计待排序序列中各个元素出现的次数，各个元素的出现次数存储到以该元素为下标的位置处。

如上图所示，由于元素 2 在序列**出现了两次，因此 count[2] = 2；由于元素 4 在序列**出现了一次，因此 count[4] = 1。

3) 在第二步的基础上，将 count[max+1] 数组按照如下公式进行修改：

count[i] = count[i-1] + count[i]，i 的值为 1、2、...、max

根据此公式，我们对 count[max+1] 数组进行了修改：

4) 遍历待排序序列的每个元素，以该元素作为下标获取 count 数组中相应位置处存储的值，该值即为此元素排序后应处的位置。

以元素 4 为例，count[4] 的值为 6，表明整个序列排序后，元素 4 位于第 6 的位置：

其中，output 表示的是排序后的序列，元素 4 的确位于第 6（下标为 5）的位置。

注意，当确定一个元素排序后的位置后，需将 count[max+1] 数组中以该元素为下标的值减 1。例如，array 序列中第 1 个元素 2 在已排序序列中应位于第 count[2] = 3（下标为 2）的位置，而 array 序列中第 2 个元素 2 在已排序序列中应位于第 count[2] = 2（下标为 1）的位置。

如下为实现计数排序算法的伪代码：

//计数排序算法，array 为待排序序列
countingSort(array)
    size <- len(array)      // 获取 array 序列中的元素个数
    max <- getMax(array)    // 找到 array 序列中的最大值
    for j <- 0 to size      // 创建 count[max+1] 并统计各个元素的出现次数
        count[array[j]] <- count[array[j]] + 1
    for i <- 1 to max       // 对 count[max+1] 存储的元素做累加操作
        count[i] <- count[i] + count[i - 1];
    for j <- size down to 0 // 根据 count[max+1] 中的累加值，找到各个元素排序后的具体位置
        output[count[array[i]] - 1] = array[i];
        count[array[i]] <- count[array[i]] - 1  // 确定一个元素的位置后，count[max+1] 中相应位置的数值要减 1
    return output[size]

计数排序算法的具体实现

如下是使用计数排序算法对 {4,2,2,8,3,3,1} 进行升序排序的 C 语言程序：

#include <stdio.h>
#define N 7       //待排序序列中的元素个数
#define MAX 100   //待排序序列中的最大值不能超过 100
//找到数组中的最大值
int getMax(int array[]) {
    int max = array[0];
    for (int i = 1; i < N; i++) {
        if (array[i] > max)
            max = array[i];
    }
    return max;
}

void countingSort(int array[]) {
    //第 1 步，找到序列中的最大值
    int max = getMax(array);
    int count[MAX] = {0};
    int output[N] = {0};
    //第 2 步，统计各个元素的出现次数，并存储在相应的位置上
    for (int i = 0; i < N; i++) {
        count[array[i]]++;
    }
    //第 3 步，累加 count 数组中的出现次数
    for (int i = 1; i <= max; i++) {
        count[i] += count[i - 1];
    }
   
    //第 4 步，根据 count 数组中的信息，找到各个元素排序后所在位置，存储在 output 数组中
    for (int i = N - 1; i >= 0; i--) {
        output[count[array[i]] - 1] = array[i];
        count[array[i]]--;
    }

    // 将 output 数组中的数据原封不动地拷贝到 array 数组中
    for (int i = 0; i < N; i++) {
        array[i] = output[i];
    }
}

void printArray(int array[]) {
    for (int i = 0; i < N; ++i) {
        printf("%d ", array[i]);
    }
}

int main() {
    int array[] = { 4, 2, 2, 8, 3, 3, 1 };
    //进行计数排序
    countingSort(array);
    printArray(array);
}

如下是使用计数排序算法对 {4,2,2,8,3,3,1} 进行升序排序的 Java 程序：

public class Demo {
    //找到数组中的最大值
    public static int getMax(int[] array) {
        int max = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
        }
        return max;
    }

    public static void countingSort(int[] array) {
        int length = array.length;
        //第 1 步，找到序列中的最大值
        int max = getMax(array);
        //第 2 步，初始化一个 count[max+1]
        int[] count = new int[max + 1];
        int[] output = new int[length];
        //统计各个元素的出现次数，并存储在相应的位置上
        for (int i = 0; i < length; i++) {
            count[array[i]]++;
        }
        // 第 3 步，累加 count 数组中的出现次数
        for (int i = 1; i <= max; i++) {
            count[i] += count[i - 1];
        }
        // 第 4 步，根据 count 数组中的信息，找到各个元素排序后所在位置，存储在 output 数组中
        for (int i = length - 1; i >= 0; i--) {
            output[count[array[i]] - 1] = array[i];
            count[array[i]]--;
        }

        // 将 output 数组中的数据原封不动地拷贝到 array 数组中
        for (int i = 0; i < length; i++) {
            array[i] = output[i];
        }
    }

    public static void printArray(int[] array) {
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
    }

    public static void main(String[] args) {
        // 待排序序列
        int[] array = new int[] { 4, 2, 2, 8, 3, 3, 1 };
        //进行计数排序
        countingSort(array);
        printArray(array);
    }
}

如下是使用计数排序算法对 {4,2,2,8,3,3,1} 进行升序排序的 Python 程序：

格式化复制

array = [4, 2, 2, 8, 3, 3, 1]
length = len(array)
#找到数组中的最大值
def getMax(array):
    max = array[0]
    for i in range(1,length):
        if array[i] > max:
            max = array[i]
    return max
#实现计数排序算法
def countingSort(array):
    #第 1 步，找到序列中的最大值
    max = getMax(array)
    #第 2 步，初始化一个 count[max+1]
    count = [0]*(max+1)
    output = [0]*length
    #统计各个元素的出现次数，并存储在相应的位置上
    for i in range(length):
        count[array[i]] = count[array[i]]+1
    #第 3 步，累加 count 数组中的出现次数
    for i in range(1,max+1):
        count[i] = count[i] + count[i-1]
    #第 4 步，根据 count 数组中的信息，找到各个元素排序后所在位置，存储在 output 数组中
    for i in range(length):
        output[count[array[i]]-1] = array[i];
        count[array[i]] = count[array[i]]-1;
    #将 output 数组中的数据原封不动地拷贝到 array 数组中
    for i in range(length):
        array[i] = output[i];

def printArray(array):
    for i in range(length):
        print(array[i],end=' ')

countingSort(array)
printArray(array)

以上程序的输出结果均为：

1 2 2 3 3 4 8