箱排序实用价值不大，仅适用于作为基数排序的一个中间步骤。 桶排序
箱排序的变种。为了区别于上述的箱排序，姑且称它为桶排序(实际上箱排序和桶排序是同义词)。 1、桶排序基本思想
桶排序的思想是把[0，1)划分为n个大小相同的子区间，每一子区间是一个桶。然后将n个记录分配到各个桶中。因为关键字序列是均匀分布在[0，1)上的，所以一般不会有很多个记录落入同一个桶中。由于同一桶中的记录其关键字不尽相同，所以必须采用关键字比较的排序方法(通常用插入排序)对各个桶进行排序，然后依次将各非空桶中的记录连接(收集)起来即可。 注意：
这种排序思想基于以下假设：假设输入的n个关键字序列是随机分布在区间[0，1)之上。若关键字序列的取值范围不是该区间，只要其取值均非负，我们总能将所有关键字除以某一合适的数，将关键字映射到该区间上。但要保证映射后的关键字是均匀分布在[0，1)上的。
基数排序
基数排序的基本思想是：从低位到高位依次对Kj(j=d-1，d-2，…，0)进行箱排序。在d趟箱排序中，所需的箱子数就是基数rd，这就是\基数排序\名称的由来。
假设原来有一串数值如下所示： 73, 22, 93, 43, 55, 14, 28, 65, 39, 81
首先根据个位数的数值，在走访数值时将它们分配至编号0到9的桶子中： 0 1 81 2 22 3 73 93 43 4 14 5 55 65 6 7 8 28 9 39
接下来将这些桶子中的数值重新串接起来，成为以下的数列： 81, 22, 73, 93, 43, 14, 55, 65, 28, 39
接着再进行一次分配，这次是根据十位数来分配： 0 1 14 2 22 28 3 39 4 43 5 55 6 65 7 73 8 81
9 93
接下来将这些桶子中的数值重新串接起来，成为以下的数列： 14, 22, 28, 39, 43, 55, 65, 73, 81, 93
这时候整个数列已经排序完毕；如果排序的对象有三位数以上，则持续进行以上的动作直至最高位数为止。 LSD的基数排序适用于位数小的数列，如果位数多的话，使用MSD的效率会比较好，MSD的方式恰与LSD相反，是由高位数为基底开始进行分配，其他的演算方式则都相同。 实作 * C
#include
int data[10] = {73, 22, 93, 43, 55, 14, 28, 65, 39, 81}; int temp[10][10] = ; int order[10] = ; int i, j, k, n, lsd; k = 0; n = 1;
printf(\排序前: \for(i = 0; i < 10; i++) printf(\putchar('\\n'); while(n <= 10) { for(i = 0; i < 10; i++) { lsd = ((data / n) % 10); temp[lsd][order[lsd]] = data; order[lsd]++; }
printf(\重新排列: \for(i = 0; i < 10; i++) { if(order != 0)
for(j = 0; j < order; j++) { data[k] = temp[j]; printf(\k++; }
order = 0; } n *= 10; k = 0; }
putchar('\\n'); printf(\排序后: \for(i = 0; i < 10; i++) printf(\
return 0; } * Java
public class RadixSort {
public static void sort(int[] number, int d) { int k = 0; int n = 1;
int[][] temp = new int[number.length][number.length]; int[] order = new int[number.length]; while(n <= d) {
for(int i = 0; i < number.length; i++) { int lsd = ((number / n) % 10); temp[lsd][order[lsd]] = number; order[lsd]++; }
for(int i = 0; i < number.length; i++) { if(order != 0)
for(int j = 0; j < order; j++) { number[k] = temp[j]; k++; }
order = 0; } n *= 10; k = 0; } }
public static void main(String[] args) { int[] data =
{73, 22, 93, 43, 55, 14, 28, 65, 39, 81, 33, 100}; RadixSort.sort(data, 100); for(int i = 0; i < data.length; i++) { System.out.print(data + \} } }
按平均时间将排序分为四类：
（1）平方阶(O(n2))排序
一般称为简单排序，例如直接插入、直接选择和冒泡排序；
（2）线性对数阶(O(nlgn))排序
如快速、堆和归并排序；
（3）O(n1+￡)阶排序
￡是介于0和1之间的常数，即0<￡<1，如希尔排序；
（4）线性阶(O(n))排序 如桶、箱和基数排序。
各种排序方法比较
简单排序中直接插入最好，快速排序最快，当文件为正序时，直接插入和冒泡均最佳。
影响排序效果的因素
因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法应综合考虑下列因素： ①待排序的记录数目n； ②记录的大小(规模)；
③关键字的结构及其初始状态； ④对稳定性的要求； ⑤语言工具的条件； ⑥存储结构；
⑦时间和辅助空间复杂度等。
不同条件下，排序方法的选择
(1)若n较小(如n≤50)，可采用直接插入或直接选择排序。
当记录规模较小时，直接插入排序较好；否则因为直接选择移动的记录数少于直接插人，应选直接选择排序为宜。
(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜； (3)若n较大，则应采用时间复杂度为O(nlgn)的排序方法：快速排序、堆排序或归并排序。
快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序所需的辅助空间少于快速排序，并且不会出现快速排序可能出现的最坏情况。这两种排序都是不稳定的。
若要求排序稳定，则可选用归并排序。但本章介绍的从单个记录起进行两两归并的 排序算法并不值得提倡，通常可以将它和直接插入排序结合在一起使用。先利用直接插入排序求得较长的有序子文件，然后再两两归并之。因为直接插入排序是稳定的，所以改进后的归并排序仍是稳定的。
4)在基于比较的排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程。
当文件的n个关键字随机分布时，任何借助于\比较\的排序算法，至少需要O(nlgn)的时间。
箱排序和基数排序只需一步就会引起m种可能的转移，即把一个记录装入m个箱子之一，因此在一般情况下，箱排序和基数排序可能在O(n)时间内完成对n个记录的排序。但是，箱排序和基数排序只适用于像字符串和整数这类有明显结构特征的关键字，而当关键字的取值范围属于某个无穷集合(例如实数型关键
字)时，无法使用箱排序和基数排序，这时只有借助于\比较\的方法来排序。
若n很大，记录的关键字位数较少且可以分解时，采用基数排序较好。虽然桶排序对关键字的结构无要求，但它也只有在关键字是随机分布时才能使平均时间达到线性阶，否则为平方阶。同时要注意，箱、桶、基数这三种分配排序均假定了关键字若为数字时，则其值均是非负的，否则将其映射到箱(桶)号时，又要增加相应的时间。
(5)有的语言(如Fortran，Cobol或Basic等)没有提供指针及递归，导致实现归并、快速(它们用递归实现较简单)和基数(使用了指针)等排序算法变得复杂。此时可考虑用其它排序。
(6)本章给出的排序算法，输人数据均是存储在一个向量中。当记录的规模较大时，为避免耗费大量的时间去移动记录，可以用链表作为存储结构。譬如插入排序、归并排序、基数排序都易于在链表上实现，使之减少记录的移动次数。但有的排序方法，如快速排序和堆排序，在链表上却难于实现，在这种情况下，可以提取关键字建立索引表，然后对索引表进行排序。然而更为简单的方法是：引人一个整型向量t作为辅助表，排序前令t=i(0≤i 指示了记录之间的顺序关系： R[t[0]].key≤R[t[1]].key≤…≤R[t[n-1]].key 若要求最终结果是： R[0].key≤R[1].key≤…≤R[n-1].key 则可以在排序结束后，再按辅助表所规定的次序重排各记录，完成这种重排的时间是O(n)。 265,301,751,127,937,863,742,694,76,438 这十个数字进行： 直接插入，希尔（SHELL），冒泡，直接选择，归并排序，记数排序，要求写出第一趟排序结果，例如快排第一趟为： 76 127 265 751 937 863 742 694 301 438，/*265作为基*/； 做出其他的 直接插入:265 301751 127 937 863 742 694 76 438 希尔:265 742 69476 438 863 901 751 129 937 以5为距离 冒泡: 265 301127 751 863 742 694 76 438 937 直接选择:76 301751 265 937 863 742 694 127 438