首页 > 代码库 > 线性时间排序 Sorting in linear time O(n)
线性时间排序 Sorting in linear time O(n)
Sorting In Linear Time
之前尝试过很多的排序算法, 都是基于比较的排序算法(base on comparing)
Collection of algorithm for sorting (part one)
http://blog.csdn.net/cinmyheart/article/details/39268783
Collection of algorithm for sorting (part two)
http://blog.csdn.net/cinmyheart/article/details/39396651
Collection of algorithm for sorting (part three)
http://blog.csdn.net/cinmyheart/article/details/39413037
------------------------------------------------------------------------------------------------------------------------------------
时间复杂度为O(n)的Counting Sort 计数排序
这里给出两个语言实现的版本
C语言实现:
/********************************************************* Code writer : EOF Code date : 2014.01.11 Code file : counting_sort.c e-mail : jasonleaster@gmail.com Code description: Here is a implementation for counting sort. If you find something wrong with my code, please touch me by e-mail. *********************************************************/ #include <stdio.h> #include <stdlib.h> int counting_sort(int *num,int size) { if(!num) { return -1; } int *p_buffer = (int*)malloc(sizeof(int)*size); //initialization int i = 0; for(i = 0; i < size; i++) { p_buffer[i] = 0; } //counting for(i = 0; i < size; i++) { p_buffer[num[i]] += 1; } //output from bigger element to smaller element int index = 0; for(index = i = size -1;i >= 0; i--) { while(p_buffer[i]-- > 0) { num[(size -1) - index] = i; index--; } } free(p_buffer); return 0; } int main() { int array[] = {1,3,4,3,2,7,4,0}; int size_array = sizeof(array)/sizeof(array[0]); int i = 0; printf("Before sorting:array[] = \n"); for(i = 0; i < size_array; i++) { printf("\t%d",array[i]); } printf("\n"); counting_sort(array,size_array); printf("After sorting:array[] = \n"); for(i = 0; i < size_array; i++) { printf("\t%d",array[i]); } printf("\n"); return 0; }
Python实现:
""" Code writer : EOF Code date : 2014.01.11 Code file : counting_sort.py e-mail : jasonleaster@gmail.com Code description: Here is a implementation for counting sort. If you find something wrong with my code, please touch me by e-mail. """ def counting_sort(array) : size = len(array) buf = [0] * size for i in range(0, size) : buf[array[i]] += 1 for index in range(size -1, 0, -1) : i = index while buf[i] > 0 : array[(size -1) - index] = i index -= 1 buf[i] -= 1 return array array = [1,3,4,3,2,7,4,0] print "Befor sorting" ,array sorted_ary = counting_sort(array) print "After sorting", sorted_ary
radix sorting wait for updating ...
既不是向东,也不是向西,而是指向内心
线性时间排序 Sorting in linear time O(n)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。