如果我们不采用比较的方式来实现排序,可以采用其他方式实现排序么?是的,可以。
1.桶排序
例如,我们有一个数组,里面的元素如下:
索引:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
元素:0 3 3 0 1 1 0 3 0 2 0 1 1 2 0
根据上面给出的数据,我们可以统计数组中每个不同的数出现的次数
数字:0 1 2 3
次数:6 4 2 3
输出时,我们根据上面的数组,每个数字出现几次,我们就输出几次,得到:
0 0 0 0 0 0 1 1 1 1 2 2 3 3 3
现在有一个问题,上面的方法叫做排序么?根本就不是。可能大家有点疑惑,上面的数字明显就是按照顺序输出的啊,怎么不是排序?问题在于,我们排序时,大部分情况下都是对一个记录进行排序,每条记录有个关键字,我们只是通过关键字来对记录进行排序,也就是说,排序的东西仅仅是我们信息的一部分。上面的做法,我们只是把关键字输出了,但是每个关键字对应的那条记录的信息我们怎么对应起来?
Ok,我们来做一下改进,依然是对数据进行统计,不过我们记录统计信息时是把具有相同关键的字的记录用链表串起来。就像把数据放到一个个的桶里,每个桶上贴一个标签,标签就相当于数组中每个不同的数。如下面所示,记录的括号里表示关键字的值。
0记录1(0)记录2(0)记录3(0)记录4(0)记录5(0)记录6(0)
1记录7(1)记录8(1)记录9(1)记录10(1)
2记录11(2)记录12(2)
3记录13(3)记录13(3)记录13(3)
因此输出时,我们就可以按序输出,同时可以知道每条记录的信息了。
注意:大家可能看到我上面的叙述和哈希表里的单独链的实现方式好像类似,其实不是一回事,哈希表的第一步是求哈希码的值,第二步是处理冲突问题,单独链是解决冲突的方式之一。我后面有空,会写关于哈希表的东西的。而我们这里仅仅是根据记录里的关键字的值来进行统计。也就是,根本就不需要什么哈希函数进行哈希码值进行计算。
现在来看看时间复杂度,可以看到,统计一次,可以在线性时间内完成,放到桶里也可以在常数操作内实现,总是时间复杂度O(n),是线性的。
2.索引计数排序
例如,我们有一个数组arr,里面的元素如下:
索引:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
元素:0 3 3 0 1 1 0 3 0 2 0 1 1 2 0
根据上面给出的数据,
第一步,我们可以统计数组中每个不同的数出现的次数,放到数组count里,操作count[arr[i]+1]++,注意我们放的时候,是放到对应的后一个数字的位置里,例如数字2对应的次数是4,其实是说有4个1。
数字:0 1 2 3 4
次数:0 6 4 2 3
第二步,我们计算累积值,同样是针对count数组,执行count[i+1]+=count[i]。例如,数字2对应的累计是10,表示小于2的数字个数是10。因此,现在累积值得含义是,遇到对应的索引值(也就是说,原始数组里的元素的值),应该开始放的位置。
数字:0 1 2 3 4
累计:0 6 10 12 15
第三步,我们从原始数组里,根据累计,知道应该把那个数字放到哪个对应的位置,即根据元素知道知道元素对应的累积值,知道了这个元素开始放的位置。当然了,具体操作是先放到一个辅助的数组里aux里去。具体操作是aux[count[arr[i]]++]=arr[i];
索引:0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
元素:0 3 3 0 1 1 0 3 0 2 0 1 1 2 0
我们具体来看,原始数组第一个位置的值是0,那么根据累积数组count[0]=0,即我们应该把它放到辅助数组的第一个位置,aux[0]=0,同时现在count[0]应该增1.第二个元素是1,我们看累积数组count[1]=6,那么我们应该1放到aux的索引6的位置,即aux[6]=1,最后count[1]应该增1为7,第二次遇到元素是6时,就放到aux索引7的位置。
第四步,我们把辅助数组里的内容copy到原始数组。
arr[i]=aux[i];
可以看到,计数排序也是线性时间内完成的。O(n)。
3.基址排序
我这里主要说一下思路。基址排序一般会用计数排序的内容。例如,我们有下面的一些字符串记录记录,为了清楚,我用空格隔开了,例如dab,我写成d a b:
d a b
a d d
c a b
f a d
f e e
b a d
d a d
b e e
f e d
b e d
e b b
a c e
基址排序的基本思想就是按位比较,具体到字符串,我们可以说是按字符比较,比如,对于dab和add字符串,根据他们的字符串首字母d和a,我们知道a<d的,那么add应该排到dab的前面,比较就可以停止了,根本没有必要再比较后面的内容。如果相同的话,继续取它们对应的下一个字符进行比较。
例如,上面的字符串数据,我们使用计数排序对它们的首字母进行排序后的结果如下:
a d d
a c e
b a d
b e e
b e d
c a b
d a b
d a d
e b b
f a d
f e e
f e d
现在,根据第一位字母相同的进行分组,继续对剩下的字符使用相同的计数排序,最后就可以得到完全排好序的字符串记录。
小结:我们采用桶排序,计数排序和基址排序,可以在线性时间内完成排序。其实基址排序还有很多深入的内容可以进一步说明的,我以后有空再写。现在为止,我已经对排序的10个基本的算法进行了说明。
分享到:
相关推荐
几种常见的排序算法代码,附有其效率及分析
选择排序算法、冒泡排序算法和插入排序算法的时间复杂度为O(n2),写法简单,逻辑易懂,但算力性价比不高,不适用于数据量较大时使用。 合并排序算法和快速排序算法采用了采用分治法、递归的方法,将时间复杂度降为...
该程序包含7大排序算法: # sort.bubbleSort() #冒泡排序 # sort.shellSort() #希尔排序 # sort.insertionSort() #插入排序 # sort.Selectionsort1() #选择排序 # sort.heapSort() #堆排序 # sort.countSort() ...
js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js排序算法动态显示js...
常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结
排序算法排序算法排序算法排序算法排序算法排序算法排序算法
最快的排序算法 C语言最简单的排序算法冒泡排序并返回排序前索引序号,排序算法数据结构
排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档排序算法归档
排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大,所以排序算法 对算法本身的速度要求很高。 而一般我们所谓的算法的性能主要是指算法的复杂度,一般用O方法来表示。在后面我将 给出详细的说明...
希尔排序,冒泡排序、快速排序递归排序,快速排序非递归排序,快速排序改进算法
十大经典排序算法 排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中 进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序 记录,在...
b) 对于这三类数据,比较上述排序算法中的关键字的比较次数和移动次数; c) 对于这三类数据,比较上述排序算法的执行时间,精确到微秒; d) 对于2和3的结果进行分析,验证上述各种算法的时间复杂度; e) 编写MAIN...
2、单处理机上快速排序算法 3、快速排序算法的性能 4、快速排序算法并行化 5、描述了使用2m个处理器完成对n个输入数据排序的并行算法。 6、在最优的情况下并行算法形成一个高度为logn的排序树 7、完成快速排序的...
Verilog/C++实现排序算法:Verilog/C++实现排序算法:冒泡排序、选择排序、并行全比较排序、串行全比较排序。
最快的排序算法 谁才是最强的排序算法:快速排序-归并排序-堆排序,排序算法数据结构
题目一: 内排序算法比较 1) 对以下6种常用的内部排序算法进行比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。 2) 待排序记录的文件个数不小于1000( 其数据用伪随机数产生),至少用5组...
文档包含:排序算法:选择排序排序算法,插入排序排序算法,对半插入排序排序算法,冒泡排序排序算法,堆排序排序算法。
十种排序算法介绍十种排序算法介绍十种排序算法介绍
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
陕西科技大学学校的排序算法实验,最近小咲写的: 一、实验目的 1. 熟练运用冒泡排序、选择排序、插入排序、希尔排序、快速排序、合并排序、堆排序等七种常见的内排序算法 2. 使用不同的数据结合计算各种算法的运行...