排序的箱排序

已知一组无序正整数数据a[1]、a[2]、……a[n]，需将其按升序排列。首先定义一个数早御隐组x[m],且m>=a[1]、a[2]、……a[n]，接着循环n次，每次x[a]++.

优点：快，效率达到O(1)

缺点：数据范围必须为正整数并且比较小

箱排序(Bin Sort)

1、箱排序的基本思想

箱排序也称桶排序(Bucket Sort)，其基本思想是：设置若干个箱子，依次扫描待排序的记录R[0]，R[1]，…，R[n-1]，把关键字等于k的记录全都装入到第k个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。

【例】要将一副混洗的52张扑克牌按点数A<2<…<J<Q<K排序，需设置13个箱子，排序时依次将每张牌按点数放入相应的箱子里，然后依次将这些箱子首尾相接，就得到了按点数递增序排列的一副牌。

2、箱排序中，箱子的个数取决于关键字的取值范围。

若R[0..n-1]中关键字的取值范围是0到m-1的整数，则必须设置m个箱子。因此箱排序要求关键字的类型是有限类型，否则可能要无限个箱子。

3、箱子的类型应设计成链表为宜

一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的，故箱子的类型应设计成链表为宜。

4、为保证排序是稳定的，分配过程中装箱及收集过程中的连接必须按先进先出原则进行。

（1）拆毕 实现方法一

每个箱子设为一个链队列。当一记录装入某箱子时，应做人队 *** 作将其插入该箱子尾部；而收集过程则是对箱子做出队 *** 作，依次将出队的记录放到输出序列中。

（2） 实现方法二

若输入的待排序记录是以链表形式给出时，出队 *** 作可简化为是将整个箱子链表链接到输出链表的尾部。这只需要修改输出链表的尾结点中的指针域，令其指向箱子链表的头，然后修改输出链表的尾指针，令其指向箱子链表的尾即可。

5、算法简析

分配过程的时间是O(n)；收集过程的时间为O(m) （采用链表来存储输入的待排序记录）或O(m+n)。因此，箱排序的时间为O(m+n)。若箱子个数m的数量级为O(n)，则箱排序的时间是线性的，即O(n)。

注意：

箱排序实用价值不大，仅适用于作为基数排序的一个中间步骤。

归并排序

归并排序是多次将两个或两个以上的有序表合并成一个新的有序表陆厅。最简单的归并是直接将两个有序的子表合并成一个有序的表。

归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方. program guibing

type

arr=array[1..100] of integer

var

a,b,c:arr

i:integer

procedure gb(r:arrl,m,n:integervar r2:arr)

var

i,j,k,p:integer

begin

i:=l

j:=m+1

k:=l-1

while (i<=m)and (j<=n) do

begin

k:=k+1

if r[i]<=r[j] then

begin

r2[k]:=r[i]

i:=i+1

end

else

begin

r2[k]:=r[j]

j:=j+1

end

end

if i<=m then

for p:=i to m do

begin

k:=k+1

r2[k]:=r[p]

end

if j<=n then

for p:=j to n do

begin

k:=k+1

r2[k]:=r[p]

end

end

procedure gp( var r,r1:arrs,t:integer)

var

k:integer

c:arr

begin

if s=t then r1[s]:=r[s]

else

begin

k:=(s+t) div 2

gp(r,c,s,k)

gp(r,c,k+1,t)

gb(c,s,k,t,r1)

end

end

begin

readln(n)

for i:= 1 to n do

read(a[i])

gp(a,b,1,n)

for i:=1 to n do

write(b[i],' ')

writeln

end.

桶排序的实验如下：

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别皮明的排序算法或是以递归方式继续使用桶排序进行排序）。

桶排序是鸽巢运拿排序的一种归纳结果。当要被排序的数组内的数值是均匀分配的时候，桶排序使用线性时间（Θ（n））。但桶排序并不是 比较排序，他不受到O(nlogn) 下限的影响。

假定：输入是由一个随机过程产生的[0, 1)区间上均匀分布的实数。将区间[0, 1)划分为n个大小相等的子区间（桶），每桶大小1/n：[0, 1/n)， [1/n, 2/n)， [2/n, 3/n)，…，[k/n, (k+1)/n )，…将n个输入元素分配到这些桶中，对桶中元素进行排序，然后依次连接桶输入0 ≤A[1..n] <1辅助数组B[0..n-1]是一指针数组，指向桶（链表）。

桶排序是一种常用的线性时间复杂度排序算法，它的应用如下：

数据分布范围较小的情况：当待排序数据的数据范围比较小的时候，桶排序可以很好地发挥其优势。比如，对于0~100之间的整数进行排序，可以先创建101个桶，每个桶存放对应数字的出现次数，然后按序遍历桶并输出即可。

处理大量重复元素的情况：对于存在大量重复元素的情况，桶排序的效率也会比其他排序算法高。因为桶排序在统计每个元素出现次数的过程中，相同元素只需计数一次，并存放在同一个桶里，不需要进行额外的比较和交换 *** 作。

作为其他排序算法的优化：桶排序还可以作为其他排序算法的优化，提高其排序效率。比如，在快速排序中，每次选取的枢轴元素可能会导致某些分区的长度远大于另一些分区，这就会影响快排的效率。此时可以使用桶排序对枢轴元素进行预处理，将数据分成若干个区域，再对燃悄告每个区域内的元素进行快排。