信息奥训班义(三)排序.docVIP

-  PAGE 9 - 排 序 法 选择排序selection sort 基本思想：每一步从待排序的数据中选择最小（此处以正序为例，若为反序则正好相反）的数据，顺序放在已排好序的子序列的最后，直到全部数据排序完毕。 对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理是将L[2..n]中最小者与L[2]交换位置，，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。 初始状态 [ 12 8 10 14 6 2 ] 第一步排序 2 [ 8 10 14 6 12 ] 第二步排序 2 6 [ 10 14 8 12 ] 第三步排序 2 6 8 [ 14 10 12 ] 第四步排序 2 6 8 10 [ 14 12 ] 第五步排序 2 6 8 10 12 14 直接选择排序的程序如下： Procedure sort_select; Var I,j,k,t:integer; Begin For i:=1 to n-1 do Begin K:=I; For j:=i+1 to n do If a[k]a[j] then k:=j; If kI then Begin t:=a[i]; A[i]:=a[k]; A[k]:=t; End; End; End; 算法评价： 数据比较次数 无论数据序列初始状态如何，在第i步排序中选出最小数据，需做n-i次比较。因此，总的比较次数为n(n-1)/2=O(n2); （2）数据的移动次数： 当初始数据序列为正序时，移动次数为0.数据序列初态为反序时，每步排序均要执行交换操作，总的移动次数取最大值3(n-1)。直接选择排序的平均时间复杂度为O(n2); 稳定性分析： 直接选择排序是不稳定的。 冒泡排序 基本思想： 冒泡排序是将待排序的数据看成一个个重量不等的气泡，依据轻气泡不能在重气泡之下的原则，从下往上扫描，凡遇违反本原则的情况，就进行一次交换，使轻气泡“上浮”。如此反复，直到没有轻气泡在下，重气泡在上为止。 ︻ 12 2 2 2 2 2 ︻ 8 12 6 6 6 6 ︻ 10 8 12 8 8 8 ︻ 14 10 8 12 10 10 ︻ 6 14 10 10 12 12 2 6 14 14 14 14 ︼ ︼ ︼ ︼ ︼ 初 第 第 第 第 第 始 一 二 三 四 五 数 步 步 步 步 步 据 排 排 排 排 排 序 序 序 序 序 后 后 后 后 后 冒泡排序的程序如下： Procedure sort_bubble; Var I,j,t:integer; Begin For i:=1 to n-1 do For j:=n downto i+1 do If a[j-1]a[j] then Begin t:=a[j-1]; A[j-1]:=a[j];