数据结构中的各种排序

1 ．直接插入排序

假设待排序的记录存放在数组 R[0….n-1] 中，排序过程的某一中间时刻， R 被划分成两个子区间 R[0…i-1] 和 R[i….n-1] ，其中：前一个子区间是已排好序的有序区；后一个子区间则是当前未排序的部分。直接插入排序的基本操作是将当前无序区的第 1 个记录 R[i] 插入到有序区 R[0….i-1] 中适当的位置，使 R[0…i] 变为新的有序区。

2． 希尔排序

先取定一个小于 n 的整数 d 作为第一个增量，把表的全部记录分成 d 组，所有距离为 d1 的倍数的记录放在同一组中，在各组内进行直接插入排序；然后取第二个增量 d2<d1 ，重复上述的分组和排序，直至增量 d ＝ 1 ，即所有记录放在同一组中进行直接插入排序为止。

3． 冒泡排序

通过无序区中相邻记录关键字间的比较和位置的交换，使关键字最小的记录逐渐向上升。整个算法是从最下面的记录开始，对每两个个相邻的关键字进行比较，且使关键字小的记录换至关键字较大的位置，使得经过一趟冒泡排序后，关键字最小的记录到达最上端，接着再在剩下的记录中找关键字次小的记录，并把它换至第二个位置上。依此类推，一直到所有记录都有序为止。

4． 快速排序

在待排序的 n 个记录中任取一个记录（通常取第一个记录），把该记录放入最终位置后，数据序列被此记录分割成两部分。所有比它大的记录放置在后一部分，所有比它小的记录放置在前一部分，并把该记录排在这两部分之间，这个过程称作一趟快速排序。之后对所有的两部分分别重复上述过程，直至每部分内只有一个记录为止。简而言之，每趟使表的第一个元素入终位，将表一分为二，对子表按递归方式继续这种划分，直至划分的子表长为 1 。

5． 选择排序

基本思想：第 i 趟排序开始时，当前有序区和无序区分别为 R[0….i-1] 和 R[i…n-1], 该趟排序则是从无序区中选出关键字最小的记录 R[k], 它与无序区的第一个记录 R[i] 交换 , 使 R[0…i] 和 R[i+1…n] 分别变为新的有序区和无序区。因为每趟排序使有序区中增加一个记录，且有序区的记录均不大于无序区中记录的关键字，即第 i 趟排序之后 R[0…i] 的所有关键字等于 R[i+1..n-1] 中的所有关键字 , 所以进行 n-1 趟之后有 R[0..n-2] 的所有关键字小于等于其后所有关键字 , 也就是说 , 经过 n-1 趟排序后 , 整个表 R[0..n-1] 递增有序 .

6． 堆排序

堆排序是在排序过程中，将顺序表中存储的数据看成是一棵完全而叉树，利用完全二叉树中双亲结点和孩子结点之间的内在联系来选择关键字最小记录。具体做法是：把待排序的表的关键字存放在数组 R[1…n] 之中，将 R 看成一棵二叉树，每个结点表示一个记录，原表的第一个记录 R[1] 作为二叉树的根，以下各记录 R[2..n] 依次逐层从左到右顺序排序，构成一棵完全二叉树，任意结点 R[i] 的左孩子是 R[2i+1] ，右孩子是 R[2i+2] ，双亲是 R[i/2] 。

 

7． 归并排序

归并排序是多次将两个或两个以上的有序表合并成一个新的有序表以两个有序表的合并为例：每次从两个有序表中取出一个记录进行关键字的比较，将较小的放入一个临时数组，最后将各段中余下的部分直接复制到临时数组。这样临时数组就是一个有序表。

8 ．基数排序

  以 r 为基数的最低位优先基数排序的过程是：假设线形表由结点序列 a0 ， a1 ， …a(n-1) 构成每个结点 aj 的关键字由 d 元组（ ）。在排序过程中使用 r 个队列 Q0 ， Q1 ， …..Qr-1 。排序过程如下：

    对 i=0 ， 1 ， ….. ， d-1 ，依次做一次“分配” ” 收集 ” （其实就是一次稳定的排序过程）。

    分配：开始时，把 Q0 ， Q1 ， …Qr-1 各个队列置成空队列，然后依次考察线性表中的每一个结点 aj （ j=0 ， 1… ， n-1 ），如果 aj 的关键字 ，就把 aj 放进 Qk 队列中。

收集：把 Q0 ， Q1 ， …. ， Qr-1 各个队列中的结点依次首尾相接，得到新的结点序列，从而组成新的线性表。

 

  调试分析

1.       本程序经过多次调试才得以通过执行，从插入排序到基数排序，每一个都经过亲自调试

2.       本人觉得本题中最难的是基数排序，在本程序中，我使用递归等方法才做出

3.       对本程序的时空分析如下

各排序的对比，交换次数如下表：（以下数据为比较次数与数据移动次数之和）

	少量数据	大量数据	顺序数据	逆序数据
插入排序	20	556	9	65
希尔排序	47	1245	42	58
冒泡排序	56	1732	45	110
快速排序	157	203	63	67
选择排序	72	1474	90	80
堆排序	65	617	68	39
归并排序	19	94	19	40
基数排序	40	200	20	22

由上表可知，在忽略辅助空间的情况考虑，无论运行少量数据和大量数据，归并排序占优，而当数据有序时，插入排序占优，主要因为实现该排序时的算法用了一个辅助数组，大大减少了数据的移动次数，数据完全逆序时，堆排序效率最高。

a) 从平均时间性能而言，快速排序最佳，其所需时间最省，但快速排序在最坏情况     下的时间性能为 O(n*n) 不如堆排序和归并排序 O(n*logn) 。而后两者相比较的结果是，在 n 较大时， 归并排序所需的时间较堆排序省，但它所需的辅助存储量最多。

                    i.            单排序中以直接排序最简单，当序列的记录基本有序或ｎ较小时，它是最佳的排序方法。

                    ii.            数排序的时间复杂度较小。因此最适用于 n 值很大的时候而关键字较小的序列。若关键字也很大，而序列中的大多数记录的最高位关键字均不同，则亦可先按最高位关键字不同将序列分成若干小的子序列，而后进行直接插入排序。

                    iii.            从方法的稳定性来比较，基数排序是稳定的内排方法，所有时间复杂度为

O （ n*n ）的简单排序也是稳定的，然而，快速排序，堆排序和希尔排序等时间性 能   较好的排序方法都是不稳定的，一般来说，排序过程中的比较是在相临的两个记录关键字间进行的排序方法都是稳定的。由于大多数情况下排序是按记录的主关键字进行的，则所用的排序方法是否稳定无关紧要。若排序按记录的次关键字进行，则应根据问题所需慎重选择排序方法及其描叙算法。

综上所叙，在这些排序方法中没有哪一中是绝对最优的，有的适用于 n 较大的情况，有的适用于 n 较小的情况，因此，在实用时需要根据不同的情况适当选用，甚至可以将多种方法综合起来使用。

算法的时空分析和改进设想

 

详细内容请看http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.2.2.1.htm