1. 云栖社区>
  2. 技术文集>
  3. 列表>
  4. 正文

排序算法之 计数排序 及其时间复杂度和空间复杂度__算法

作者:用户 来源:互联网 时间:2018-06-01 16:02:23

数据结构面试排序算法基数排序计数排序

排序算法之 计数排序 及其时间复杂度和空间复杂度__算法 - 摘要: 本文讲的是排序算法之 计数排序 及其时间复杂度和空间复杂度__算法,        计数排序是一个非基于比较的排序算法,该算法于1954年由 Harold H. Seward 提出。它的优势在于在对一定范围内的整数排序时,它的复杂度为Ο(n+k)(其中k是整数的范围),快于任何比较排序算法

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


算法分析         主要思想:根据array数组元素的值进行排序,然后统计大于某元素的元素个数,最后就可以得到某元素的合适位置;比如:array[4] = 9;统计下小于array[4]的元素个数为:8;所以array[4] = 9 应该放在元素的第8个位置;         主要步骤:        1、根据array数组,把相应的元素值对应到tmpArray的位置上;      2、然后根据tmpArray数组元素进行统计大于array数组各个元素的个数;      3、最后根据上一步统计到的元素,为array元素找到合适的位置,暂时存放到tmp数组中;
        如下图所示:array 是待排序的数组;tmpArray 是相当于桶的概念; tmp 是临时数组,保存array排好序的数组;

        排序算法之 计数排序 及其时间复杂度和空间复杂度__算法

        注意:计数排序对输入元素有严格要求,因为array元素值被用来当作tmpArray数组的下标,所以如果array的元素值为100的话,那么tmpArray数组就要申请101(包括0,也就是 mix - min + 1)。


代码实现

<pre name="code" class="cpp">#include<stdio.h>
#include<stdlib.h>
 
 void print_array(int *array, int length)
 {
     int index = 0;
     printf("array:\n");
     for(; index < length; index++){
         printf(" %d,", *(array+index));
     }   
     printf("\n\n");
 }
 
 void countSort(int *array, int length)
 {
   /*
     int *tmpArray = (int*)malloc(sizeof(int)*length);
     int i, j, count;
 
     for (i = 0; i < length; i++) tmpArray[i] = 0;
         
     for (i = 0; i < length; i++){
         for (count = 0, j = 0; j < length; j++){
             if (array[i] < array[j])count++;
         }               
         while(tmpArray[count])count++;
         tmpArray[count] = array[i];
     }   
 
     for (i = 0; i < length; i++)array[i] = tmpArray[i];
 
     free(tmpArray);
  */

     int *tmpArray = (int*)malloc(sizeof(int)*(length+1));//申请内存空间,记得大小为length + 1(因为array元素值为 0~9)
     int tmp[length];
     int i, j, k;
 
     for (i = 0; i < length; i++){ // 初始化数组
         tmpArray[i] = 0;  
         tmp[i] = 0;
     }   
 
     for (i = 0; i < length; i++) tmpArray[array[i]]++; // 表示该桶内有多少个元素
 
     for (i = 1; i <= length; i++) tmpArray[i] += tmpArray[i-1];// 统计大于该元素的元素个数
     
     for (i = length; i > 0; i--){// 这是核心代码了,可以理解为把array数组中的元素存放到合适的位置
         tmp[tmpArray[array[i-1]]-1] = array[i-1];
         tmpArray[array[i-1]]--; // 解决一个桶内有多个元素
     }   
 
     for (i = 0; i < length; i++) array[i] = tmp[i];// 把有序元素放回到array数组中
 
     free(tmpArray);// 是否空间

 }
 int main(void)
 {
 //  int array[] = {12, 1, 32, 201, 9987, 5, 10, 10090, 123, 453};
     int array[] = {2, 1, 3, 0, 9, 5, 1, 7, 4};
     int length = (sizeof(array)) / (sizeof(array[1]));
     print_array(array, length);
     countSort(array, length);
     print_array(array, length);
 
     return 0;
 }
 
  

        运行结果:

        排序算法之 计数排序 及其时间复杂度和空间复杂度__算法


时间复杂度

        时间复杂度可以很好的看出了就是:O( n );


空间复杂度         空间复杂度也可以很好的看出来:O( n );
总结         计数排序的时间复杂度和空间复杂度都是非常有效的,但是该算法对输入的元素有限制要求,所以并不是所有的排序都使用该算法;最好的是0~9之间的数值差不会很大的数据元素间比较;有人会说这个没多大用,但是在后面的基数排序中会看到,这可以算是基数排序中的一个基础;

        转载请注明作者和原文出处,原文地址:http://blog.csdn.net/yuzhihui_no1/article/details/44561487         若有不正确之处,望大家指正,共同学习。谢谢。。。

以上是云栖社区小编为您精心准备的的内容,在云栖社区的博客、问答、公众号、人物、课程等栏目也有 的相关内容,欢迎继续使用右上角搜索按钮进行搜索数据结构 , 面试 , 排序算法 , 基数排序 计数排序 ,以便于您获取更多的相关知识。

一道面试题(关于千万量级数据结构排序)

...,201322233,464; 王五,201322233,464; 要求:使空间复杂度和时间复杂度尽可能低,希望可以达到时间复杂度为O(n)。按目前数据量预计计算机内存足够。可以用伪代码或说明思路 刚注册,没有分可悬赏,但应该是个...

算法之排序算法的算法思想和使用场景总结_C 语言

...非常重要。 本文介绍了常见的排序算法,从算法思想,复杂度和使用场景等方面做了总结。 2. 几个概念 (1)排序稳定:如果两个数相同,对他们进行的排序结果为他们的相对顺序不变。例如A={1,2,1,2,1}这里排序之后是A = {1,1,1,2,...

《算法之道》精华 经典算法部分

...地排序,需要占用额外空间n>=30时性能比插入排序更好。复杂度固定为O(nlog(n))快排分治,复杂的部分在于分解,而归并复杂在于合并原地排序最坏情况为O(n^2),但只要不是每次都是最坏,复杂度就不是n^2,具有韧性任何基于比较...

《Redis设计与实现》简读 笔记

...DS)相比C字符串增加记录字符串长度的,获取字符串长度复杂度为O(1) 相比C字符串增加记录已分配内存空间,可以避免缓冲区溢出 空间预分配和空间惰性释放 二进制安全,不是以空字符(/0)来判断字符串是否结束 遵循C字...

JavaScript 排序算法汇总

...过磁盘和内存的数据传输才能进行,占用额外内存。 复杂度 时间复杂度: 一个算法执行所耗费的时间。 空间复杂度: 运行完一个程序所需内存的大小。 排序算法图片总结 名词解释: n : 数据规模 k : 桶的个数 ...

前三篇
后三篇
弹性可伸缩的计算服务,助您降低 IT 成本,提升运维效率

40+云计算产品,6个月免费体验

稳定可靠、可弹性伸缩的在线数据库服务,全球最受欢迎的开源数据库之一

云服务器9.9元/月,大学必备