计数排序

  计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排 序要求输入的数据必须是有确定范围的整数。
  计数排序(Counting sort)是一种稳定的排序算法。计数排序使用一个额外的数组C,其中第i个元素是待排序数组A中值等于i的元素的个数。然后根据数组C来将A中的元素排到正确的位置。它只能对整数进行排序。
  找出待排序的数组中最大和最小的元素;
  统计数组中每个值为i的元素出现的次数,存入数组C的第i项;
  对所有的计数累加(从C中的第一个元素开始,每一项和前一项相加);
  反向填充目标数组:将每个元素i放在新数组的第C(i)项,每放一个元素就将C(i)减去1。

动图演示

计数排序

C代码

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
//计数排序
void CountSort(int *a, int len)
{
    assert(a);
    //通过max和min计算出临时数组所需要开辟的空间大小
    int max = a[0], min = a[0];
    for (int i = 0; i < len; i++){
        if (a[i] > max)
            max = a[i];
        if (a[i] < min)
            min = a[i];
    }
    //使用calloc将数组都初始化为0
    int range = max - min + 1;
    int *b = (int *)calloc(range, sizeof(int));
    //使用临时数组记录原始数组中每个数的个数
    for (int i = 0; i < len; i++){
        //注意:这里在存储上要在原始数组数值上减去min才不会出现越界问题
        b[a[i] - min] += 1;
    }
    int j = 0;
    //根据统计结果,重新对元素进行回收
    for (int i = 0; i < range; i++){
        while (b[i]--){
            //注意:要将i的值加上min才能还原到原始数据
            a[j++] = i + min;
        }
    }
    //释放临时数组
    free(b);
    b = NULL;
}
//打印数组
void PrintArray(int *a, int len)
{
    for (int i = 0; i < len; i++){
        printf("%d ", a[i]);
    }
    printf("\n");
}
int main()
{
    int a[] = { 3, 4, 3, 2, 1, 2, 6, 5, 4, 7 };
    printf("排序前:");
    PrintArray(a, sizeof(a) / sizeof(int));
    CountSort(a, sizeof(a) / sizeof(int));
    printf("排序后:");
    PrintArray(a, sizeof(a) / sizeof(int));
    system("pause");
    return 0;
}

分析:

  当输入的元素是n 个0到k之间的整数时,它的运行时间是 O(n + k)。计数排序不是比较排序,排序的速度快于任何比较 排序算法。由于用来计数的数组C的长度取决于待排序数组中数据的范围(等于待排序数组的最大值与最小值的差加上1),这使得计数 排序对于数据范围很大的数组,需要大量时间和内存。   最佳情况:T(n) = O(n+k) 最差情况:T(n) = O(n+k) 平均情况:T(n) = O(n+k)

Copyright © zs0813.com 2020 all right reserved,powered by Gitbook该文件修订时间: 2020-10-09 10:41:12

results matching ""

    No results matching ""