计数排序

计数排序是一个非基于比较的排序算法，该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时，它的复杂度为Ο(n+k)（其中k是整数的范围），快于任何比较排序算法

计数排序假设n个输入元素都是位于[0, k]之间的整数。

基本思想为对于每一个输入元素x，确定出小于x的元素个数，然后直接将x放置在最终数组的位置上。

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

void counting_sort(int A[], int B[], int length, int max);

int main(){
    int num, i;
    printf("Input the number:
");
    scanf("%d", &num);
    int *array = malloc((num + 1) * sizeof(int));
    int *arrayB = malloc((num + 1) * sizeof(int));
    int max = -1;
    printf("Input the element:");
    for(i = 1; i <= num; i++){
        scanf("%d", &array[i]);
        if(max < array[i])
            max = array[i];
    }

    counting_sort(array, arrayB, num, max);
    for(i = 1; i <= num; i++)
        printf("%d ", arrayB[i]);
    printf("
");

    return 0;
}

/*
 * 基本思想是对每一个输入元素x，统计小于x元素的个数，然后把x直接放到最终输出的数组中的正确位置上。
 * 当出现多个元素值一样的时候，需要一些修改，因为不能把相同的元素放到同一个位置上。
 * 数组A为输入数组，数组B为存放最终结果。
 */
void counting_sort(int A[], int B[], int length, int max){
    int i;
    int *C = malloc((max+1) * sizeof(int)); //数组C提供临时存储区
    for(i = 0; i <= max; i++)
        C[i] = 0;
    
    int j;
    for(j = 1; j <= length; j++)
        C[A[j]]++;
    /*C[j]记录等于j的元素个数*/
    
    for(i = 1; i <= max; i++)
        C[i] += C[i-1];
    /*C[j]此时存储的值为小于等于j的元素个数*/

    for(j = length; j >= 1; j--){
        B[C[A[j]]] = A[j];
        C[A[j]]--;
    }
    
    /*
    for(j = 1; j <= length; j++){
        B[C[A[j]]] = A[j];
        C[A[j]]--;
    }
    */
}

计数排序的总运行时间为θ(k + n)，当k = O(n)时，运行时间为Θ(n)

优于比较排序的下界Ω(nlgn)，因为在计数排序的过程中没有出现输入元素之间的比较，而是用了输入元素的实际值来确定它们在数组的位置。

额外插入排序算法的稳定。

排序算法的稳定的定义为：具有相同值的元素在输出数组中的相对次序与它们在输入数组中的次序相同。可参考维基

对于简单数据的排序，稳定性好像没什么作用，但是对于复杂数据（不只一项属性）的排序，稳定性很重要。

计数排序是稳定的排序，因此计数排序被用作基数排序算法的子过程。

练习8.2-2

在counting_sort过程中，假设将for(j = length; j >= 1; j--) 改为for(j = 1; j <= length; j++)。证明该算法仍能正常地工作，修改后的算法是稳定的吗？

计数排序算法不依赖数组A的顺序，所以仍能正常运行，而且结果正确。

但是修改后的算法不稳定。因为没修改前，在数组A里靠后的元素，在数组B也靠后（针对与元素值相同），如果修改后，结果会相反。违反了具有相同值的元素在输出数组中的相对次序与它们在输入数组中的次序相同，即稳定性。

练习8.2-4

给出一个算法，使之对于给定介于0和k之间的n个整数进行预处理，并能在O(1)时间内，回答出输入的整数中有多少个落在区间[a..b]内。你给出的算法的预处理时间应为Θ(n + k)。

用一个数组C，记录小于或等于其每个下标的值的元素个数。C[b] - C[a-1]为落在区间内的元素个数。

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

int count(int A[], int length, int k, int a, int b);

int main(){
    int num, i, k, a, b, cnt;
    printf("Input the k:
");
    scanf("%d", &k);
    printf("Input the a and b:
");
    scanf("%d %d", &a, &b);
    printf("Input the number of the elements:
");
    scanf("%d", &num);
    int *array = malloc((num + 1) * sizeof(int));
    printf("Input the element:");
    for(i = 1; i <= num; i++){
        scanf("%d", &array[i]);
    }
    
    cnt = count(array, num, k, a, b);
    printf("The number of the elements which are in the [a..b] is %d
", cnt);
    return 0;
}

int count(int A[], int length, int k, int a, int b){
    int i;
    int *C = malloc((k + 1) * sizeof(int));
    for(i = 0; i <= k; i++)
        C[i] = 0;

    int j;
    for(j = 1; j <= length; j++)
        C[A[j]]++;

    for(i = 1; i <= k; i++)
        C[i] += C[i-1];

    return C[b] - C[a-1] ;
}

转自：http://www.cnblogs.com/alan-forever/p/3349824.html

基数排序：参看：http://www.cnblogs.com/youxin/p/3295399.html