但基数排序有个前提，要关键字能象整型、字符串这样能分解，若是浮点型那就不行了。
按平均时间将排序分为类： (1) 平方阶(O(n))排序
各类简单排序，例如直接插入、直接选择和冒泡排序； (2) 线性对数阶(O(nlog2n))排序
如快速排序、堆排序和归并排序； (3) O(n1+))排序
§
2
§是介于0和1之间的常数。希尔排序便是一种； (4) 线性阶(O(n))排序
本程序中的基数排序，此外还有桶、箱排序。
排序方法的选择
因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法很重要
(1)若n较小，可采用直接插入或直接选择排序。
当记录规模较小时，直接插入排序较好，它会比选择更少的比较次数； 但当记录规模较大时，因为直接选择移动的记录数少于直接插人，所以宜用选直接选择排序。 这两种都是稳定排序算法。
(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机
的快速排序为宜(这里的随机是指基准取值的随机，原因见上的快速排序分析)；这里快速排序算法将不稳定。
(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。
快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；
堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是不稳定的。
归并排序是稳定的排序算法，但它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。
(4)特殊的箱排序、基数排序
它们都是一种稳定的排序算法，但有一定的局限性： 1、关键字可分解。
2、记录的关键字位数较少，如果密集更好
3、如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。
在数据的处理中，数据的排序是相当重要的。它可以使数据更有条理，方便数据的其 它处理。在学习生活中，也经常用到数据的排序，如：考完试后个人成绩的排名、运动会上班级总分的排名、常规评比分数的排序。这些排序当然不是人工完成的， 它们大多数是用excel软件来代劳的。那么excel软件的排序的本质方法是什么呢？这就是我所要研究学习的内容。
通过查阅图书、教材，搜索资料、教程，我了解到：排序的本质其实就是比较。对于任何一种排序方法来说，比较都是其最 重要的一个组成部分。但它也是最简单的部分，因为排序方法的好坏、快慢取决于比较的方法、比较的顺序和比较的次数，而与比较本身关系不大。那么，排序具体 有那些方法呢？下面介绍几种我研究学习了的算法。 一、冒泡排序
已知一组无序数据a[1]、a[2]、??a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a [1]大于a[2]则交换两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比较a[3]与a [4]，依此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处 理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，依此类推。共处理n-1轮后a [1]、a[2]、??a[n]就以升序排列了。 优点：稳定，比较次数已知；
缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。 二、选择排序
已知一组无序数据a[1]、a[2]、??a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a [1]大于a[2]则交换两者的值，否则不变。再比较a[1]与a[3]的值，若a[1]大于a[3]则交换两者的值，否则不变。再比较a[1]与a [4]，依此类推，最后比较a[1]与a[n]的值。这样处理一轮后，a[1]的值一定是这组数据中最小的。再将a[2]与a[3]~a[n]以相同方法 比较一轮，则a[2]的值一定是a[2]~a[n]中最小的。再将a[3]与a[4]~a[n]以相同方法比较一轮，依此类推。共处理n-1轮后a [1]、a[2]、??a[n]就以升序排列了。
优点：稳定，比较次数与冒泡排序一样，数据移动次数比冒泡排序少； 缺点：相对之下还是慢。 三、插入排序
已知一组升序排列数据a[1]、a[2]、??a[n]，一组无序数据b[1]、
b[2]、??b[m]，需将二者 合并成一个升序数列。首先比较b[1]与a[1]的值，若b[1]大于a[1]，则跳过，比较b[1]与a[2]的值，若b[1]仍然大于a[2]，则继 续跳过，直到b[1]小于a数组中某一数据a[x]，则将a[x]~a[n]分别向后移动一位，将b[1]插入到原来a[x]的位置这就完成了b[1]的 插入。b[2]~b[m]用相同方法插入。（若无数组a，可将b[1]当作n=1的数组a） 优点：稳定，快；
缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。 四、缩小增量排序
由希尔在1959年提出，又称希尔排序。
已知一组无序数据a[1]、a[2]、??a[n]，需将其按升序排列。发现当n不大是，插入排序的效果很好。首先 取一增量d(d 缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。 五、快速排序 快速排序是冒泡排序的改进版，是目前已知的最快的排序方法。 已知一组无序数据a[1]、a[2]、??a[n]，需将其按升序排列。首先任取数据a[x]作为基准。比较a [x]与其它数据并排序，使a[x]排在数据的第k位，并且使a[1]~a[k-1]中的每一个数据 经过一段时间的学习和编程，我已对上述几种排序方法熟练掌握或有所了解。在此基础上，经过我的思考和实践，我研究出了一种新的排序算法：分段插入排序。 分段插入排序 已知一组升序排列数据a[1]、a[2]、??a[n]，一组无序数据b[1]、b[2]、??b[m]，需将二者 合并成一个升序数列。先将数组a分成x等份（x< 优点：快，比较次数少； 缺点：不适用于较少数据的排序，s的临界值无法确切获知，只能凭经验取。 我设计的算法或许优于某些算法，但它也有它的优点、缺点和适用范围。不仅排序算法如此，任何算法都一样。没有任何一个人干说自己的算法是最好的。设计新算法的过程其实就是增加其优点，减少其缺点和拓宽其适用范围的过程。我最崇尚的一句话就是：“没有最好，只有更好。”