第二章排序算法

1、排序算法排序算法 利用计算机获取信息后，需要进行利用计算机获取信息后，需要进行处理，处理后便于人们应用。信息处理处理，处理后便于人们应用。信息处理的方法有多种，通常有数据的排序、查的方法有多种，通常有数据的排序、查找、插入、删除和归并等操作。本节重找、插入、删除和归并等操作。本节重点介绍数据排序的几种方法。点介绍数据排序的几种方法。 基本思想：基本思想： 每一趟从待排序数据元素中选出最小（或最大）的每一趟从待排序数据元素中选出最小（或最大）的一个元素，放在待排序数列最前面，直到全部待排数据一个元素，放在待排序数列最前面，直到全部待排数据排完。排完。 过程（略）过程（略） type arr=ar

2、ray1.3000 of longint; 算法：算法：procedure selectsort(var r:arr); begin for i:=1 to n-1 do for j:=i+1 to n do if rirj then 数据元素交换；数据元素交换； begin t:=ri;ri:=rj;fj:=t;end; end；O(n*n)1、选择排序、选择排序 基本思想：基本思想： 每一趟依次比较相邻数据，从待中选出最小（或最每一趟依次比较相邻数据，从待中选出最小（或最大）的一个元素，放在待排序数列最后面，直到全部待大）的一个元素，放在待排序数列最后面，直到全部待排数据排完。排数据排完。

3、 过程（略）过程（略） 算法：算法：procedure maosort(var r:arr); begin for i:=1 to n-1 do for j:=1 to n-i do if rj0 do begin write(i);dec(ai); end; end;3、计数排序、计数排序 基本思想：基本思想： 假设待排数据在数组假设待排数据在数组r中，增加一个哨兵节点中，增加一个哨兵节点r0。使使r0.r1有序，从有序，从i=2开始，依次把后面的数据插入到该有开始，依次把后面的数据插入到该有序序列区间，使最后得到的序列依然有序。序序列区间，使最后得到的序列依然有序。 过程（略）过程（略）

4、算法：算法：procedure insertsort(var r:arr); begin r0:=-maxint; for i:=2 to n do begin j:=i-1;x:=ri; while x rj do begin rj+1:=rj; dec(j); end； rj+1:=x; end; end;4、插入排序、插入排序 算法：算法：var a:array1.10000of longint; n,i:longint; procedure asd(l,r:longint); var t,m,i,j:longint; begin i:= l ;j:=r; m:=a (i +j )div

5、 2; repeat while ma j do dec( j); if ij; if jl then asd( l, j); if ir then asd( i,r);end;5、快速排序、快速排序基本思想：基本思想： 每一趟排序将每一趟排序将数据元素分成独立数据元素分成独立的两个部分，其中的两个部分，其中一部分记录比另外一部分记录比另外一部分的记录都小一部分的记录都小（或大），则可分（或大），则可分别对这两部分记录别对这两部分记录继续进行排序，直继续进行排序，直到整个序列有序。到整个序列有序。（分治思想）（分治思想）过程（略）过程（略）时间复杂度：时间复杂度：O（nlog2n）就平均时间而

6、言，就平均时间而言，快排是最好的一种快排是最好的一种内部排序方法。内部排序方法。 算法：算法：procedure mergesort(l,r:integer); var I,j,m,k:integer; begin if l=r then exit; m:=(l+r)div 2; mergesort(l,m);mergersort(m+1,r); i:=l;j:=m+1;k:=l; while (i=m)and(j=r) do begin if ai=aj then begin tk:=ai;inc(i);inc(k); end else begin tk:=aj;inc(j);inc(k);

7、 end； end; while i=m do begin tk:=ai;inc(i);inc(k);end; while j=r do begin tk:=aj;inc(j);inc(k);end; for i:=l to r do ai:=ri; end;6、归并排序、归并排序基本思想：基本思想： 将两个或以上将两个或以上有序数列合并成一有序数列合并成一个有序数列，称为个有序数列，称为归并排序。归并排序。过程（略）过程（略）时间复杂度：时间复杂度：O（nlog2n） type point=node; node=record data:integer; next:point; end; va

8、r p,head:array0.9 of point; a:array1.1000 of integer; i,j,k,m,n,t:integer; q:point;s:string; begin randomize; readln(n); for i:=1 to n do ai:=random(90)+1; for i:=5 downto 1 do begin for j:=0 to 9 do begin new(headj); headj.next:=nil; pj:=headj; end;7、基数排序、基数排序 for j:=1 to n do begin str(aj,s); for

9、k:=1 to 5-length(s) do s:=0+s; m:=ord(si)-48; new(q); q.data:=aj; q.next:=nil; pm.next:=q; pm:=q; end; t:=0; for j:=0 to 9 do begin q:=headj; while q.nextnil do begin q:=q.next; inc(t); at:=q.data; end; end; end; for i:=1 to n do write(ai, ); end. 算法：算法：program heap; var a:array1.20 of integer; n,i,

10、temp:integer; procedure build_heap(i,m:integer); begin while 2*i=m do begin i:=2*i; if (im)and(aiai div 2 then begin temp:=ai;ai:=ai div 2;ai div 2:=temp; end else exit; end; end; begin readln(n); for i:=1 to n do ai:=random(90)+10; for i:=n div 2 downto 1 do build_heap(i,n); for i:=n downto 2 do be

11、gin temp:=a1;a1:=ai;ai:=temp; build_heap(1,i-1); end; for i:=1 to n do write(ai, );7、堆排序、堆排序基本思想：基本思想： 堆是一棵完全二叉树，堆是一棵完全二叉树，树中节点与数组中存放该树中节点与数组中存放该节点值的那个元素对应。节点值的那个元素对应。堆有大根堆和小根堆。堆堆有大根堆和小根堆。堆排利用了数据结构堆的特排利用了数据结构堆的特性，其关键在于建堆和调性，其关键在于建堆和调整堆。整堆。时间复杂度：时间复杂度：O（nlog2n） 1、明明随机数；、明明随机数；(random.in random.out) 【

12、问题描述】明明做一项问卷调查。为了试验客观性，它先【问题描述】明明做一项问卷调查。为了试验客观性，它先用计算机生成用计算机生成n个个1.1000之间的随机数，对于其中重复的数，只之间的随机数，对于其中重复的数，只保留一个，不同数对应不同学生学号。然后把这些数从小到大排保留一个，不同数对应不同学生学号。然后把这些数从小到大排序，按排好顺序去找学生做调查。请你为明明完成序，按排好顺序去找学生做调查。请你为明明完成“去重去重”与与“排序排序”工作。工作。(n=100) 【输入】【输入】10 20 40 32 67 40 20 89 300 400 15 【输出】【输出】8 15 20 32 40 6

13、7 89 300 400 2、车厢重组；、车厢重组；(carry.in carry.out) 【问题描述】在一个旧式火车站边有一座桥，可以绕河中心【问题描述】在一个旧式火车站边有一座桥，可以绕河中心水平旋转水平旋转180。该桥只能容纳两节火车车厢，如果旋转。该桥只能容纳两节火车车厢，如果旋转180可以把可以把相邻两节车厢位置调换，可以用这种方法来重新排列车厢循序。相邻两节车厢位置调换，可以用这种方法来重新排列车厢循序。编一个程序，当输入初始车厢顺序，计算最少多少步能把车厢从编一个程序，当输入初始车厢顺序，计算最少多少步能把车厢从小到大排好序。小到大排好序。 【输入】【输入】4 4 3 2 1

14、【输出】【输出】6 上机练习上机练习 3、众数；、众数；(masses.in masses.out) 【问题描述】由文件给出【问题描述】由文件给出n个个1-3000之间的无序正整数，其之间的无序正整数，其中中1=n=1000。同一个正整数可能会出现多次，出现次数最多。同一个正整数可能会出现多次，出现次数最多的整数称为众数。求众数及众数出现的次数。的整数称为众数。求众数及众数出现的次数。 【输入】【输入】12 2 4 2 3 2 5 3 7 2 3 4 3 【输出】【输出】2 4 3 4 4、第、第k小整数；小整数；(knumber.in knumber.out) 【问题描述】现有【问题描述】现

15、有n个正整数，个正整数，n=10000，要求出这，要求出这n个正个正整数中第整数中第k个最小整数，相同大小的数只记一次，个最小整数，相同大小的数只记一次，k=1000，正，正整数均小于整数均小于30000。 【输入】【输入】10 3 1 3 3 7 2 5 1 2 4 6 【输出】【输出】3 5、军事机密；、军事机密；(secret.in secret.out) 【问题描述】我军方截获信息由【问题描述】我军方截获信息由n(n=30000) 个数字组个数字组成，因为是敌国的高端秘密，所以一时不能破获。最原始的成，因为是敌国的高端秘密，所以一时不能破获。最原始的想法就是对这想法就是对这n个数进行从

16、小到大的排序，每个数都对应一个数进行从小到大的排序，每个数都对应一个序号，然后对第个序号，然后对第i个是什么数感兴趣，现要求编程完成。个是什么数感兴趣，现要求编程完成。 【输入】【输入】5 n 121 1 126 123 7 3 k 2 4 3 k个个i，要求输出对应，要求输出对应i序号的数序号的数 【输出】【输出】7 123 121 6、奖学金；、奖学金；(scholar.in scholar.out) 【问题描述】学校给前【问题描述】学校给前5名同学发奖学金。期末，每个名同学发奖学金。期末，每个学生有学生有3门课：语文、数学、信息。先按总分从高到低排序；门课：语文、数学、信息。先按总分从高

17、到低排序；如果总分相等，再按信息成绩排序；如果再都相等，那么学如果总分相等，再按信息成绩排序；如果再都相等，那么学号小的排前面。号小的排前面。 【输入】【输入】n 人数人数 学号、姓名、学号、姓名、3科成绩、总分科成绩、总分 【输出】排序后的【输出】排序后的 学号、姓名、学号、姓名、3科成绩、总分科成绩、总分【奖学金】数据输入样式：【奖学金】数据输入样式： 804aaa90 67 8003bbb87 66 9101ccc78 89 9105ddd88 99 7702eee67 89 6406fff78 89 9808ggg80 89 8907hhh88 98 787、统计数字；、统计数字；(c

18、ount.in count.out) 【问题描述】某次科研调查时得到了【问题描述】某次科研调查时得到了n个自然数，每个自然数，每个数均不超过个数均不超过1500000000（1.5*109）。已知不相同的）。已知不相同的数不超过数不超过10000个，现需要统计这些自然数各自出现的个，现需要统计这些自然数各自出现的次数，并按照自然数从小到大的顺序输出结果。次数，并按照自然数从小到大的顺序输出结果。 【输入】【输入】8 2 4 2 4 5 100 2 100 【输出】【输出】2 3 4 2 5 1 8 1 100 2 8、输油管道问题；、输油管道问题；(pipe.in pipe.out) 【问题描

19、述】某石油公司建一条由东到西的主输油【问题描述】某石油公司建一条由东到西的主输油管道。该管道穿越管道。该管道穿越n口油井的油田，每个油田有一条南口油井的油田，每个油田有一条南北走向管道和主管道相连。如果给定北走向管道和主管道相连。如果给定n口油井的位置，口油井的位置，即他们的即他们的x、y坐标，应如何确定主管道的最优位置，即坐标，应如何确定主管道的最优位置，即使得各个油井到主管道长度和最小。（使得各个油井到主管道长度和最小。（=1n=10000） 【输入】【输入】5 1 2 、 2 2、1 3、3 -2、3 3 【输出】【输出】6 9、士兵站队问题；、士兵站队问题；(sol.in sol.ou

20、t) 【问题描述】在一个划分网格的操场上，【问题描述】在一个划分网格的操场上，n个士兵散乱个士兵散乱地站在网格点上。网格点用整数坐标地站在网格点上。网格点用整数坐标x、y表示。士兵们可表示。士兵们可以按网格边上、下、左、右移动一步，但在同一时刻只能以按网格边上、下、左、右移动一步，但在同一时刻只能有一名士兵移动。按照军官命令，士兵们需要整齐列成一有一名士兵移动。按照军官命令，士兵们需要整齐列成一个水平队列，即（个水平队列，即（x，y）、（）、（x+1,y).(x+n-1,y)。如何。如何选择选择x和和y的值才能使士兵们以最少的总移动步数排成一行。的值才能使士兵们以最少的总移动步数排成一行。（1

21、=n=10000） (-10000=x,y=10000) 【输入】【输入】5 1 2 2 2 1 3 3 -2 3 3 【输出】【输出】8 Y Y轴方向上的考虑轴方向上的考虑 设目标坐标为设目标坐标为M M，即，即n n个士兵最终需要移动到的个士兵最终需要移动到的Y Y轴的坐标值为轴的坐标值为M M n n个士兵的个士兵的Y Y轴坐标分别为：轴坐标分别为： Y0Y0，Y1Y1，Y2 Yn-1Y2 Yn-1 则最优步数则最优步数S=|Y0-M|+|Y1-M|+|Y2-M|+ +|Yn-1-M|S=|Y0-M|+|Y1-M|+|Y2-M|+ +|Yn-1-M| 结论：结论：M M取中间点的值使得取

22、中间点的值使得S S为最少（最优）为最少（最优） 证明：从最上和最下的两个士兵开始递推证明：从最上和最下的两个士兵开始递推最优位置，最优位置归结到最后，处于中间位最优位置，最优位置归结到最后，处于中间位置的士兵的置的士兵的Y Y轴坐标值就是轴坐标值就是“最终位置最终位置”的的Y Y轴坐标。轴坐标。 可能有两种情况可能有两种情况 士兵总数为双数情况：取中间两点间的任意一个位置士兵总数为双数情况：取中间两点间的任意一个位置 士兵总数为单数情况：取中间点的所在位置士兵总数为单数情况：取中间点的所在位置 解决办法：对所有的解决办法：对所有的Y Y轴坐标进行排序（轴坐标进行排序（O O（nlognnlo

23、gn）或进行线性时间选择（）或进行线性时间选择（O O（n n），）， 然然后取后取“中间中间”点的点的Y Y轴坐标值作为最佳位置轴坐标值作为最佳位置M M的值的值, ,最后通过公式求出最后通过公式求出Y Y轴方向上移动的最优步数轴方向上移动的最优步数X X轴方向上的考虑轴方向上的考虑 首先需要对所有士兵的首先需要对所有士兵的X X轴坐标值进行排序轴坐标值进行排序. .然后，按从左至右的顺序依次移动到每个士兵所然后，按从左至右的顺序依次移动到每个士兵所对应的对应的“最终位置最终位置”（最优），所移动的步数总和就是（最优），所移动的步数总和就是X X轴方向上需要移动的步数轴方向上需要移动的步数例

24、，最左的士兵移动到例，最左的士兵移动到“最终位置最终位置”的最左那位，第二个士兵移动到的最左那位，第二个士兵移动到“最终位置最终位置”的第二位的第二位则总的步数为：士兵一移动步数则总的步数为：士兵一移动步数+ +士兵二移动步数士兵二移动步数+ + +士兵士兵n n移动步数移动步数如何确定如何确定X X轴方向上的最佳的轴方向上的最佳的“最终位置最终位置”？共共n n个士兵个士兵 他们相应的他们相应的X X轴坐标为：轴坐标为：X0X0，X1X1，X2 Xn-1X2 Xn-1 设，士兵需要移动到的设，士兵需要移动到的“最终位置最终位置”的的X X轴坐标值为：轴坐标值为：k k，k+1k+1，k+2 k+k+2 k+（n-1n-1） 则所求最优步数则所求最优步数S=|X0-k|+|X1- S=|X0-k|+|X1- （k+1k+1） |+|X2-|+|X2-（k+2k+2）|+ +|Xn-1-|+ +|Xn-1-（k+k+（n-1