好文档 - 专业文书写作范文服务资料分享网站

高中信息技术 全国青少年奥林匹克联赛教案 排序算法

天下 分享 时间: 加入收藏 我要投稿 点赞

全国青少年信息学奥林匹克联赛

排序算法

? 一、插入排序(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

二、选择排序 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

2

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

3

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给以出本次划分后已被定位的基准元素的位置 //

4

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] //

5

高中信息技术 全国青少年奥林匹克联赛教案 排序算法

全国青少年信息学奥林匹克联赛排序算法?一、插入排序(InsertionSort)1.基本思想:每次将一个待排序的数据元素,插入到前面已经排好序的数列中的适当位置,使数列依然有序;直到待排序数据元素全部插入完为止。2.排序过程:【示例】:[初始关键字][49]3865
推荐度:
点击下载文档文档为doc格式
7wth64b2pp1j03v4iv5u208bi7808n00a84
领取福利

微信扫码领取福利

微信扫码分享