排 序 算 法

一、插入排序(Insertion Sort)

1. 基本思想：

   每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。

2. 排序过程：　

【示例】：

[初始关键字] [49] 38 65 97 76 13 27 49

    J=2(38) [38 49] 65 97 76 13 27 49

    J=3(65) [38 49 65] 97 76 13 27 49

    J=4(97) [38 49 65 97] 76 13 27 49

    J=5(76) [38 49 65 76 97] 13 27 49

    J=6(13) [13 38 49 65 76 97] 27 49

    J=7(27) [13 27 38 49 65 76 97] 49

    J=8(49) [13 27 38 49 49 65 76 97]

Procedure InsertSort(Var R : FileType);

//对R[1..N]按递增序进行插入排序, R[0]是监视哨//

  Begin

    for I := 2 To N Do //依次插入R[2],...,R[n]//

    begin

      R[0] := R[I]; J := I - 1;

      While R[0] < R[J] Do //查找R[I]的插入位置//

       begin

        R[J+1] := R[J]; //将大于R[I]的元素后移//

        J := J - 1

       end

      R[J + 1] := R[0] ; //插入R[I] //

    end

  End; //InsertSort //

二、选择排序

1. 基本思想：

　　每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

2. 排序过程：

【示例】：

  初始关键字 [49 38 65 97 76 13 27 49]

第一趟排序后 13 ［38 65 97 76 49 27 49]

第二趟排序后 13 27 ［65 97 76 49 38 49]

第三趟排序后 13 27 38 [97 76 49 65 49]

第四趟排序后 13 27 38 49 [49 97 65 76]

第五趟排序后 13 27 38 49 49 [97 97 76]

第六趟排序后 13 27 38 49 49 76 [76 97]

第七趟排序后 13 27 38 49 49 76 76 [ 97]

最后排序结果 13 27 38 49 49 76 76 97

Procedure SelectSort(Var R : FileType); //对R[1..N]进行直接选择排序 //

  Begin

    for I := 1 To N - 1 Do //做N - 1趟选择排序//

     begin

      K := I;

      For J := I + 1 To N Do //在当前无序区R[I..N]中选最小的元素R[K]//

       begin

        If R[J] < R[K] Then K := J

       end;

      If K <> I Then //交换R[I]和R[K] //

        begin Temp := R[I]; R[I] := R[K]; R[K] := Temp; end;

     end

  End. //SelectSort //

三、冒泡排序(BubbleSort)

1. 基本思想：

　　两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。

2. 排序过程：

　　设想被排序的数组R［1..N］垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上"漂浮"，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。

【示例】：

49 13 13 13 13 13 13 13

38 49 27 27 27 27 27 27

65 38 49 38 38 38 38 38

97 65 38 49 49 49 49 49

76 97 65 49 49 49 49 49

13 76 97 65 65 65 65 65

27 27 76 97 76 76 76 76

49 49 49 76 97 97 97 97

Procedure BubbleSort(Var R : FileType) //从下往上扫描的起泡排序//

Begin

  For I := 1 To N-1 Do //做N-1趟排序//

   begin

     NoSwap := True; //置未排序的标志//

     For J := N - 1 DownTo 1 Do //从底部往上扫描//

      begin

       If R[J+1]< R[J] Then //交换元素//

        begin

         Temp := R[J+1]; R[J+1 := R[J]; R[J] := Temp;

         NoSwap := False

        end;

      end;

     If NoSwap Then Return //本趟排序中未发生交换，则终止算法//

    end

End. //BubbleSort//

四、计数排序

计数排序的思想是若待排序的记录的关键字在一个明显的有限范围内（整数）时，可设计一个数组，出现与数组下标值一样的数，该下标的数组元素值加１,最后扫描整个数组，根据统计的信息给出一个有序数列。

五、快速排序（Quick Sort）

1. 基本思想：

　　在当前无序区R[1..H]中任取一个数据元素作为比较的"基准"(不妨记为X)，用此基准将当前无序区划分为左右两个较小的无序区：R[1..I-1]和R[I+1..H]，且左边的无序子区中数据元素均小于等于基准元素，右边的无序子区中数据元素均大于等于基准元素，而基准X则位于最终排序的位置上，即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)，当R[1..I-1]和R[I+1..H]均非空时，分别对它们进行上述的划分过程，直至所有无序子区中的数据元素均已排序为止。

2. 排序过程：

【示例】：

初始关键字 [49 38 65 97 76 13 27 49］

第一次交换后 ［27 38 65 97 76 13 49 49］

第二次交换后 ［27 38 49 97 76 13 65 49］

J向左扫描，位置不变，第三次交换后 ［27 38 13 97 76 49 65 49］

I向右扫描，位置不变，第四次交换后 ［27 38 13 49 76 97 65 49］

J向左扫描 ［27 38 13 49 76 97 65 49］

（一次划分过程）

初始关键字 ［49 38 65 97 76 13 27 49］

一趟排序之后 ［27 38 13］ 49 ［76 97 65 49］

二趟排序之后 ［13］ 27 ［38］ 49 ［49 65］76 ［97］

三趟排序之后 13 27 38 49 49 ［65］76 97

最后的排序结果 13 27 38 49 49 65 76 97

各趟排序之后的状态

Procedure Parttion(Var R : FileType; L, H : Integer; Var I : Integer);

//对无序区R[1,H]做划分，I给以出本次划分后已被定位的基准元素的位置 //

Begin

  I := 1; J := H; X := R[I] ; //初始化，X为基准//

  Repeat

    While (R[J] >= X) And (I < J) Do

      begin

       J := J - 1 //从右向左扫描，查找第1个小于 X的元素//

       If I < J Then //已找到R[J] 〈X//

         begin

          R[I] := R[J]; //相当于交换R[I]和R[J]//

          I := I + 1

         end;

       While (R[I] <= X) And (I < J) Do

          I := I + 1 //从左向右扫描，查找第1个大于 X的元素///

      end;

     If I < J Then //已找到R[I] > X //

       begin         R[J] := R[I]; //相当于交换R[I]和R[J]//

        J := J - 1

       end

  Until I = J;

  R[I] := X //基准X已被最终定位//

End; //Parttion //

Procedure QuickSort(Var R :FileType; S,T: Integer); //对R[S..T]快速排序//

Begin

  If S < T Then //当R[S..T]为空或只有一个元素是无需排序//

    begin

      Partion(R, S, T, I); //对R[S..T]做划分//

      QuickSort(R, S, I-1); //递归处理左区间R[S,I-1]//

      QuickSort(R, I+1,T); //递归处理右区间R[I+1..T] //

    end;

End. //QuickSort//

六、几种排序算法的比较和选择

1. 选取排序方法需要考虑的因素：

(1) 待排序的元素数目n；

(2) 元素本身信息量的大小；

(3) 关键字的结构及其分布情况；

(4) 语言工具的条件，辅助空间的大小等。

2. 小结：

(1) 若n较小(n <= 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。

(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。

(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。

(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于"比较"的排序算法，至少需要O(nlog2n)的时间。

(5) 当记录本身信息量较大时，为避免耗费大量时间移动记录，可以用链表作为存储结构。

通过实验我们可将结果列入下表。

以下是VC6.0(Release)＋win2000pro+128MDDR+P4(1.6G)

因为在多任务操作系统下，系统将进行进程序调度，影响实验结果。以下是经过稍微修正过的值。如果要取得更准确的值，我们得多次实验求其平均值。

排序算法实验比较(单位：秒)

算法与结果联合分析

冒泡排序：在最优情况下只需要经过n- 1次比较即可得出结果，（这个最优情况那就是序列己是正序，从100K的正序结果可以看出结果正是如此），但在最坏情况下，即倒序（或一个较小值在最 后），下沉算法将需要n(n-1)/2次比较。所以一般情况下，特别是在逆序时，它很不理想。它是对数据有序性非常敏感的排序算法。

冒泡排序２：它是冒泡排序的改良（一次下沉再一次上浮），最优情况和最坏情况与冒泡排序差不多，但是一般情况下它要好过冒泡排序，它一次下沉，再一次上浮，这样避免了因一个数的逆序，而造成巨大的比较。如（2,3,4,…,n- 1,n,1），用冒泡排序需要n(n-1)/2次比较，而此排序只要3轮,共比较(n-1)+(n-2)+(n-3)次，第一轮1将上移一位，第二轮1将 移到首位，第三轮将发现无数据交换，序列有序而结束。但它同样是一个对数据有序性非常敏感的排序算法，只适合于数据基本有序的排序。

快速排序：它同样是冒泡排序的改进，它通过一次交换能消除多个逆序，这样可以减少逆序时所消耗的扫描和数据交换次数。在最优情况下，它的排序时间复杂度为Ｏ(nlog2n)。 即每次划分序列时，能均匀分成两个子串。但最差情况下它的时间复杂度将是Ｏ(n^2)。即每次划分子串时，一串为空，另一串为m-1（程序中的100K正 序和逆序就正是这样，如果程序中采用每次取序列中部数据作为划分点，那将在正序和逆时达到最优）。从100K中正序的结果上看“快速排序”会比“冒泡排 序”更慢，这主要是“冒泡排序”中采用了提前结束排序的方法。有的书上这解释“快速排序”，在理论上讲，如果每次能均匀划分序列，它将是最快的排序算法， 因此称它作快速排序。虽然很难均匀划分序列，但就平均性能而言，它仍是基于关键字比较的内部排序算法中速度最快者。

直接选择排序：简单的选择排序，它的比较次数一定：n(n- 1)/2。也因此无论在序列何种情况下，它都不会有优秀的表现（从上100K的正序和反序数据可以发现它耗时相差不多，相差的只是数据移动时间），可见对 数据的有序性不敏感。它虽然比较次数多，但它的数据交换量却很少。所以我们将发现它在一般情况下将快于冒泡排序。

堆排序：由于它在直接选择排序的基础上利用了比较结果形成。效率提高很大。它完成排序的总比较次数为Ｏ(nlog2n)。它是对数据的有序性不敏感的一种算法。但堆排序将需要做两个步骤：－是建堆，二是排序（调整堆）。所以一般在小规模的序列中不合适，但对于较大的序列，将表现出优越的性能。

直接插入排序：简 单的插入排序，每次比较后最多移掉一个逆序，因此与冒泡排序的效率相同。但它在速度上还是要高点，这是因为在冒泡排序下是进行值交换，而在插入排序下是值 移动，所以直接插入排序将要优于冒泡排序。直接插入法也是一种对数据的有序性非常敏感的一种算法。在有序情况下只需要经过n-1次比较，在最坏情况下，将需要n(n-1)/2次比较。

希尔排序：增量的选择将影响希尔排序的效率。但是无论怎样选择增量，最后一定要使增量为１，进行一次直接插入排序。但它相对于直接插入排序，由于在子表中每进行一次比较，就可能移去整个经性表中的多个逆序，从而改善了整个排序性能。希尔排序算是一种基于插入排序的算法，所以对数据有序敏感。

归并排序：归并排序是一种非就地排序，将需要与待排序序列一样多的辅助空间。在使用它对两个己有序的序列归并，将有无比的优势。其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。对数据的有序性不敏感。若数据节点数据量大，那将不适合。但可改造成索引操作，效果将非常出色。

基数排序：在程序中采用的是以数值的十进制位分解，然后对空间采用一次性分配，因此它需要较多的辅助空间(10*n+10), （但我们可以进行其它分解，如以一个字节分解，空间采用链表将只需辅助空间n+256）。基数排序的时间是线性的(即O(n))。由此可见，基数排序非常吸引人，但它也不是就地排序，若节点数据量大时宜改为索引排序。但基数排序有个前提，要关键字能象整型、字符串这样能分解，若是浮点型那就不行了。

按平均时间将排序分为类：

(1) 平方阶(O(n2))排序

　　各类简单排序，例如直接插入、直接选择和冒泡排序；

(2) 线性对数阶(O(nlog2n))排序

　　如快速排序、堆排序和归并排序；

(3) O(n1+§))排序

　　§是介于0和1之间的常数。希尔排序便是一种；

(4) 线性阶(O(n))排序

　　本程序中的基数排序，此外还有桶、箱排序。

排序方法的选择

因为不同的排序方法适应不同的应用环境和要求，所以选择合适的排序方法很重要

(1)若n较小，可采用直接插入或直接选择排序。

当记录规模较小时，直接插入排序较好，它会比选择更少的比较次数；

但当记录规模较大时，因为直接选择移动的记录数少于直接插人，所以宜用选直接选择排序。

这两种都是稳定排序算法。

(2)若文件初始状态基本有序(指正序)，则应选用直接插人、冒泡或随机的快速排序为宜(这里的随机是指基准取值的随机，原因见上的快速排序分析)；这里快速排序算法将不稳定。

(3)若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序序。

快速排序是目前基于比较的内部排序中被认为是最好的方法，当待排序的关键字是随机分布时，快速排序的平均时间最短；

堆排序虽不会出现快速排序可能出现的最坏情况。但它需要建堆的过程。这两种排序都是不稳定的。

　 归并排序是稳定的排序算法，但它有一定数量的数据移动，所以我们可能过与插入排序组合，先获得一定长度的序列，然后再合并，在效率上将有所提高。

(4)特殊的箱排序、基数排序

它们都是一种稳定的排序算法，但有一定的局限性：

　　1、关键字可分解。

　　2、记录的关键字位数较少，如果密集更好

　　3、如果是数字时，最好是无符号的，否则将增加相应的映射复杂度，可先将其正负分开排序。

各种排序算法比较