1、排序算法五例 一、插入排序(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
2、) 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 I Then /交换 RI和 RK /begin Temp := RI; RI := RK; RK := Temp; end;endEnd; /SelectSort /三、冒泡排序(BubbleSort)1.
3、 基本思想：两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。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
4、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 X /begin RJ := RI; /相当于交换 RI和 RJ/J := J - 1endUnt
5、il I = J;RI := X /基准 X 已被最终定位/End; /Parttion /Procedure QuickSort(Var R :FileType; S,T: Integer); /对 RS.T快速排序/BeginIf S length；i+)if(p-elemi.key elemi-1.key) /*小于时，需将 elemi插入有序表*/ p-elem0.key=p-elemi.key； /*为统一算法设置监测*/for(j=i-1；p-elem0.key elemj.key；j-)p-elemj+1.key=p-elemj.key； /*记录后移*/p-elemj+1.ke
6、y=p-elem0.key； /*插入到正确位置*/【效率分析】空间效率：仅用了一个辅助单元。时间效率：向有序表中逐个插入记录的操作，进行了 n-1 趟，每趟操作分为比较关键码和移动记录，而比较的次数和移动记录的次数取决于待排序列按关键码的初始排列。最好情况下：即待排序列已按关键码有序，每趟操作只需 1 次比较 2 次移动。总比较次数=n-1 次总移动次数=2(n-1)次最坏情况下：即第 j 趟操作，插入记录需要同前面的 j 个记录进行 j 次关键码比较，移动记录的次数为 j+2 次。平均情况下：即第 j 趟操作，插入记录大约同前面的 j/2 个记录进行关键码比较，移动记录的次数为 j/2+2
7、 次。由此，直接插入排序的时间复杂度为 O(n2)。是一个稳定的排序方法。10.2.2 折半插入排序直接插入排序的基本操作是向有序表中插入一个记录，插入位置的确定通过对有序表中记录按关键码逐个比较得到的。平均情况下总比较次数约为 n2/4。既然是在有序表中确定插入位置，可以不断二分有序表来确定插入位置，即一次比较，通过待插入记录与有序表居中的记录按关键码比较，将有序表一分为二，下次比较在其中一个有序子表中进行，将子表又一分为二。这样继续下去，直到要比较的子表中只有一个记录时，比较一次便确定了插入位置。二分判定有序表插入位置方法： low=1；high=j-1；r0=rj ； / 有序表长度为
8、j-1，第 j 个记录为待插入记录/设置有序表区间，待插入记录送辅助单元 若 lowhigh，得到插入位置，转 lowhigh，m=(low+high)/2 ； / 取表的中点，并将表一分为二，确定待插入区间*/ 若 r0.keylength；i+) s-elem0=s-elemi； /* 保存待插入元素 */low=i；high=i-1； /* 设置初始区间 */while(lowelem0.keys-elemmid.key)low=mid+1； /* 插入位置在高半区中 */else high=mid-1； /* 插入位置在低半区中 */* while */for(j=i-1；j=high
9、+1；j-) /* high+1 为插入位置 */s-elemj+1=s-elemj； /* 后移元素，留出插入空位 */s-elemhigh+1=s-elem0； /* 将元素插入 */* for */* InsertSort */【时间效率】确定插入位置所进行的折半查找，关键码的比较次数至多为 ，次，移动记录的次数和直接插入排序相同，故时间复杂度仍为 O(n2)。是一个稳定的排序方法。10.2.3 表插入排序直接插入排序、折半插入排序均要大量移动记录，时间开销大。若要不移动记录完成排序，需要改变存储结构，进行表插入排序。所谓表插入排序，就是通过链接指针，按关键码的大小，实现从小到大的链接过
10、程，为此需增设一个指针项。操作方法与直接插入排序类似，所不同的是直接插入排序要移动记录，而表插入排序是修改链接指针。用静态链表来说明。#define SIZE 200typedef structElemType elem； /*元素类型*/int next； /*指针项 */NodeType； /*表结点类型*/typedef structNodeType rSIZE； /*静态链表*/int length； /*表长度*/L_TBL； /*静态链表类型*/假设数据元素已存储在链表中，且 0 号单元作为头结点，不移动记录而只是改变链指针域，将记录按关键码建为一个有序链表。首先，设置空的循环链表
11、，即头结点指针域置 0，并在头结点数据域中存放比所有记录关键码都大的整数。接下来，逐个结点向链表中插入即可。【例 10.2】表插入排序示例MAXINT 49 38 65 97 76 13 27 490 - - - - - - - -MAXINT 49 38 65 97 76 13 27 491 0 - - - - - - -MAXINT 49 38 65 97 76 13 27 492 0 1 - - - - - -MAXINT 49 38 65 97 76 13 27 492 3 1 0 - - - - -MAXINT 49 38 65 97 76 13 27 492 3 1 4 0 - -
12、 - -MAXINT 49 38 65 97 76 13 27 492 3 1 5 0 4 - - -MAXINT 49 38 65 97 76 13 27 496 3 1 5 0 4 2 - -MAXINT 49 38 65 97 76 13 27 496 3 1 5 0 4 7 2 -MAXINT 49 38 65 97 76 13 27 496 8 1 5 0 4 7 2 3图 10.1表插入排序得到一个有序的链表，查找则只能进行顺序查找，而不能进行随机查找，如折半查找。为此，还需要对记录进行重排。重排记录方法：按链表顺序扫描各结点，将第 i 个结点中的数据元素调整到数组的第 i 个分量数据域。因为第 i 个结点可能是数组的第 j 个分量，数据元素调整仅需将两个数组分量中数据
