排序算法专题排 序 算 法一、插入排序(Insertion Sort)1. 基本思想： 每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。2. 排序过程： 【示例】：初始关键字 49 38 65 97 76 13 27 49J=2(38) 38 49 65 97 76 13 27 49J=3(65) 38 49 65 97 76 13 27 49J=4(97) 38 49 65 97 76 13 27 49J=5(76) 38 49 65 76 97 13 27 49J=6(13) 13 38 49 65 76 97 27 49J=7(27) 13 27 38 49 65 76 97 49J=8(49) 13 27 38 49 49 65 76 97 Procedure InsertSort(Var R : FileType);/对R1.N按递增序进行插入排序, R0是监视哨/Beginfor I := 2 To N Do /依次插入R2,.,Rn/beginR0 := RI; J := I - 1;While R0 RJ Do /查找RI的插入位置/beginRJ+1 := RJ; /将大于RI的元素后移/J := J - 1endRJ + 1 := R0 ; /插入RI /endEnd; /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 97Procedure SelectSort(Var R : FileType); /对R1.N进行直接选择排序 /Beginfor I := 1 To N - 1 Do /做N - 1趟选择排序/beginK := I;For J := I + 1 To N Do /在当前无序区RI.N中选最小的元素RK/beginIf RJ RK Then K := Jend;If K I Then /交换RI和RK /begin Temp := RI; RI := RK; RK := Temp; end;endEnd. /SelectSort /三、冒泡排序(BubbleSort)1. 基本思想：两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。2. 排序过程：设想被排序的数组R1.N垂直竖立，将每个数据元素看作有重量的气泡，根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上漂浮，如此反复进行，直至最后任何两个气泡都是轻者在上，重者在下为止。【示例】：49 13 13 13 13 13 13 13 38 49 27 27 27 27 27 2765 38 49 38 38 38 38 3897 65 38 49 49 49 49 4976 97 65 49 49 49 49 4913 76 97 65 65 65 65 6527 27 76 97 76 76 76 7649 49 49 76 97 97 97 97 Procedure BubbleSort(Var R : FileType) /从下往上扫描的起泡排序/BeginFor I := 1 To N-1 Do /做N-1趟排序/beginNoSwap := True; /置未排序的标志/For J := N - 1 DownTo 1 Do /从底部往上扫描/beginIf RJ+1= X) And (I J) DobeginJ := J - 1 /从右向左扫描，查找第1个小于 X的元素/If I J Then /已找到RJ X/beginRI := RJ; /相当于交换RI和RJ/I := I + 1end;While (RI = X) And (I J) DoI := I + 1 /从左向右扫描，查找第1个大于 X的元素/end;If I X /begin RJ := RI; /相当于交换RI和RJ/J := J - 1endUntil I = J;RI := X /基准X已被最终定位/End; /Parttion /Procedure QuickSort(Var R :FileType; S,T: Integer); /对RS.T快速排序/BeginIf S T Then /当RS.T为空或只有一个元素是无需排序/beginPartion(R, S, T, I); /对RS.T做划分/QuickSort(R, S, I-1); /递归处理左区间RS,I-1/QuickSort(R, I+1,T); /递归处理右区间RI+1.T /end;End. /QuickSort/六、几种排序算法的比较和选择 1. 选取排序方法需要考虑的因素：(1) 待排序的元素数目n；(2) 元素本身信息量的大小；(3) 关键字的结构及其分布情况；(4) 语言工具的条件，辅助空间的大小等。2. 小结：(1) 若n较小(n = 50)，则可以采用直接插入排序或直接选择排序。由于直接插入排序所需的记录移动操作较直接选择排序多，因而当记录本身信息量较大时，用直接选择排序较好。(2) 若文件的初始状态已按关键字基本有序，则选用直接插入或冒泡排序为宜。(3) 若n较大，则应采用时间复杂度为O(nlog2n)的排序方法：快速排序、堆排序或归并排序。 快速排序是目前基于比较的内部排序法中被认为是最好的方法。(4) 在基于比较排序方法中，每次比较两个关键字的大小之后，仅仅出现两种可能的转移，因此可以用一棵二叉树来描述比较判定过程，由此可以证明：当文件的n个关键字随机分布时，任何借助于比较