首页 > 算法 > 算法系列之 计数排序

算法系列之 计数排序

计数排序

之前讲的各种排序算法:插入排序、选择排序、冒泡排序、归并排序、快速排序、堆排序和希尔排序等,这些排序算法复杂度都不是线性的。
有没有可能找到一种线性的排序算法? 答案是肯定的。只要我们不比较,不交换元素,而在扫描到元素的时候,就能确定此元素在有序序列中的位置,就可以达到线性算法复杂度。这种排序叫计数排序。
它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法。

算法实现

计数排序使用一个额外的数组counted_a,以待排序数组a每个元素的值为key,对应待排序数组a中元素的值出现的次数为value。然后根据数组counted_a来将待排序数组a中的元素排到正确的位置。

void CountingSort(int a[], int n, int k)
{
     //counted_a用于存放计数
     int *counted_a = (int *)malloc(sizeof(int) * k);
     //sorted_a用于存放已经排序好的元素
     int *sorted_a = (int *)malloc(sizeof(int) * n);

     int i;
     for (i = 0; i < k; i++)
     {
          counted_a[i] = 0;
     }
     // 计数:统计待排序数组中元素的出现次数
     for (i = 0; i < n; i++)
     {
          counted_a[a[i]] ++;
     }

     //求计数和
     for (i = 1; i < k; i++)
     {
          counted_a[i] += counted_a[i - 1];
     }

     // 整理:根据数组counted_a来将待排序数组a中的元素排到正确的位置
     for (i = n-1; i >= 0; i--)
     {
          sorted_a[counted_a[a[i]] - 1] = a[i];
          counted_a[a[i]]--;
     }
     //将已经排序的数组复制回原来初始数组
     memcpy(a, sorted_a, sizeof(int) *n); 

     free(counted_a);
     free(sorted_a);

}

(转载本站文章请注明出处 www.helloitworks.com ,请勿用于任何商业用途)

分类: 算法 标签:
  1. 本文目前尚无任何评论.
  1. 本文目前尚无任何 trackbacks 和 pingbacks.