信息学竞赛常用算法与策略：排序

查字典合肥奥数网讯：信息学竞赛常用算法与策略：排序。

排序就是将杂乱无章的数据元素，通过一定的方法按关键字顺序排列的过程。

4.1 简单排序

1.选择排序

选择排序的基本思想是：

对待排序的记录序列进行n-1遍的处理，第1遍处理是将L[1..n]中最小者与L[1]交换位置，第2遍处理是将L[2..n]中最小者与L[2]交换位置，......，第i遍处理是将L[i..n]中最小者与L[i]交换位置。这样，经过i遍处理之后，前i个记录的位置就已经按从小到大的顺序排列好了。

例1:输入序列数据按非减顺序输出.

程序如下:

program xzpx;

const n=7;

var a:array[1..n] of integer;

i,j,k,t:integer;

begin

write('Enter date:');

for i:= 1 to n do read(a[i]);

writeln;

for i:=1 to n-1 do

begin

k:=i;

for j:=i+1 to n do

if a[j]<a[k] then k:=j;

if k<>i then

begin t:=a[i];a[i]:=a[k];a[k]:=t;end;

end;

write('output data:');

for i:= 1 to n do write(a[i]:6);

writeln;

end.

2.插入排序

插入排序的基本思想:经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置p，原来p后的元素一一向右移动一个位置,使得L[1..i]又是排好序的序列。

例2:输入序列数据按非减顺序输出.

程序1:

program crpx;

const n=7;

var a:array[1..n] of integer;

i,j,k,t:integer;

begin

write('Enter date:');

for i:= 1 to n do read(a[i]);

writeln;

for i:=2 to n do

begin

k:=a[i];j:=i-1;

while (k<a[j]) and (j>0) do

begin a[j+1]:=a[j];j:=j-1 end;

a[j+1]:=k;

end;

write('output data:');

for i:= 1 to n do write(a[i]:6);

writeln;

end.

3.冒泡排序

冒泡排序又称交换排序其基本思想是:对待排序的记录的关键字进行两两比较,如发现两个

记录是反序的,则进行交换,直到无反序的记录为止。

例:输入序列数据按非减顺序输出。

程序1:

program mppx;

const n=7;

var a:array[1..n] of integer;

i,j,k,t:integer;

begin

write('Enter date:');

for i:= 1 to n do read(a[i]);

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];a[j]:=t end;

write('output data:');

for i:= 1 to n do write(a[i]:6);

writeln;

end.

程序2：

program mppx;

const n=7;

var a:array[1..n] of integer;

i,j,k,t:integer;

bool:boolean;

begin

write('Enter date:');

for i:= 1 to n do read(a[i]);

i:=1;bool:=true;

while (i<n) and bool do

begin

bool:=false;

for j:=n downto i+1 do

if a[j-1]<a[j] then

begin t:=a[j-1];a[j-1]:=a[j];a[j]:=t;bool:=true end;

i:=i+1;

end;

write('output data:');

for i:= 1 to n do write(a[i]:6);

writeln;

end.

程序3：

program mppx;

const n=7;

var a:array[1..n] of integer;

i,j,k,t:integer;

begin

write('Enter date:');

for i:= 1 to n do read(a[i]);

writeln;

k:=n;

while k>0 do

begin

j:=k-1;k:=0;

for i:=1 to j do

if a[i]>a[i+1] then

begin t:=a[i];a[i]:=a[i+1];a[i+1]:=t;k:=i;end;

end;

write('output data:');

for i:= 1 to n do write(a[i]:6);

writeln;

end.

4.2快速排序

快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.

例:输入一组数据小到大排序.

程序1:

program kspv;

const n=7;

type

arr=array[1..n] of integer;

var

a:arr;

i:integer;

procedure quicksort(var b:arr; s,t:integer);

var i,j,x,t1:integer;

begin

i:=s;j:=t;x:=b[i];

repeat

while (b[j]>=x) and (j>i) do j:=j-1;

if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;

while (b[i]<=x) and (i<j) do i:=i+1;

if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end

until i=j;

b[i]:=x;

i:=i+1;j:=j-1;

if s<j then quicksort(b,s,j);

if i<t then quicksort(b,i,t);

end;

begin

write('input data:');

for i:=1 to n do read(a[i]);

writeln;

quicksort(a,1,n);

write('output data:');

for i:=1 to n do write(a[i]:6);

writeln;

end.

程序2:

program kspv;

const n=7;

type

arr=array[1..n] of integer;

var

a:arr;

i:integer;

procedure quicksort(var b:arr; s,t:integer);

var i,j,x:integer;

begin

i:=s;j:=t;x:=b[i];

repeat

while (b[j]>=x) and (j>i) do j:=j-1;

if j>i then begin b[i]:=b[j];i:=i+1;end;

while (b[i]<=x) and (i<j) do i:=i+1;

if i<j then begin b[j]:=b[i];j:=j-1; end

until i=j;

b[i]:=x;

i:=i+1;j:=j-1;

if s<j then quicksort(b,s,j);

if i<t then quicksort(b,i,t);

end;

begin

write('input data:');

for i:=1 to n do read(a[i]);

writeln;

quicksort(a,1,n);

write('output data:');

for i:=1 to n do write(a[i]:6);

writeln;

end.

4.3希尔排序

基本思想：将整个无序序列分割成若干小的子序列分别进行插入排序或冒泡排序。

序列分割方法：将相隔某个增量h的元素构成一个子序列。在排序过程中，逐次减小这个增量，最后当h减到1时，进行一次插入排序或冒泡排序，排序就完成。增量序列一般采用：d1=n div 2 ,di=di-1 div 2 ；i=2,3,4.....其中n为待排序序列的长度。

程序1:(子序列是插入排序)

program xepx;

const n=7;

type

arr=array[1..n] of integer;

var

a:arr;

i,j,t,d:integer;

bool:boolean;

begin

write('input data:');

for i:=1 to n do read(a[i]);

writeln;

d:=n;

while d>1 do

begin

d:=d div 2;

for j:=d+1 to n do

begin

t:=a[j];i:=j-d;

while (i>0) and (a[i]>t) do

begin a[i+d]:=a[i];i:=i-d;end;

a[i+d]:=t;

end;

end;

write('output data:');

for i:=1 to n do write(a[i]:6);

writeln;

end.

程序2:(子序列是冒泡排序)

program xepx;

const n=7;

type

arr=array[1..n] of integer;

var

a:arr;

i,temp,d:integer;

bool:boolean;

begin

write('input data:');

for i:=1 to n do read(a[i]);

writeln;

d:=n

while d>1 do

begin

d:=d div 2;

repeat

bool:=true;

for i:=1 to n-d do

if a[i]>a[i+d] then

begin temp:=a[i];a[i]:=a[i+d];a[i+d]:=temp; bool:=false end;

until bool;

end;

write('output data:');

for i:=1 to n do write(a[i]:6);

writeln;

end.

4.4 堆排序与二叉树排序

1.堆排序

堆：设有数据元素的集合（R1,R2,R3,...Rn)它们是一棵顺序二叉树的结点且有

Ri<=R2i 和Ri<=R2i+1(或>=)

堆的性质：堆的根结点上的元素是堆中的最小元素，且堆的每一条路径上的元素都是有序的。

堆排序的思想是：

1）建初始堆（将结点[n/2],[ n/2]-1,...3,2,1分别调成堆）

2）当未排序完时

输出堆顶元素，删除堆顶元素，将剩余的元素重新建堆。

程序如下：

program duipx;

const n=8;

type arr=array[1..n] of integer;

var a:arr;i:integer;

procedure sift(var a:arr;l,m:integer);

var i,j, t:integer;

begin

i:=l;j:=2*i;t:=a[i];

while j<=m do

begin

if (j<m) and (a[j]>a[j+1]) then j:=j+1;

if t>a[j] then

begin a[i]:=a[j];i:=j;j:=2*i; end

else exit;

a[i]:=t;

end;

end;

begin

for i:=1 to n do read(a[i]);

for i:=(n div 2) downto 1 do

sift(a,i,n);

for i:=n downto 2 do

begin

write(a[1]:4);

a[1]:=a[i];

sift(a,1,i-1);

end;

writeln(a[1]:4);

end.

2.二叉树排序

排序二叉树：每一个参加排列的数据对应二叉树的一个结点，且任一结点如果有左（右）子树，则左（右）子树各结点的数据必须小（大）于该结点的数据。中序遍历排序二叉树即得排序结果。程序如下：

program pxtree;

const

a:array[1..8] of integer=(10,18,3,8,12,2,7,3);

type point=^nod;

nod=record

w:integer;

right,left:point ;

end;

var root,first:point;k:boolean;i:integer;

procedure hyt(d:integer;var p:point);

begin

if p=nil then

begin

new(p);

with p^ do begin w:=d;right:=nil;left:=nil end;

if k then begin root:=p; k:=false end;

end

else with p^ do if d>=w then hyt(d,right) else hyt(d,left);

end;

procedure hyt1(p:point);

begin

with p^ do

begin

if left<>nil then hyt1(left);

write(w:4);

if right<>nil then hyt1(right);

end

end;

begin

first:=nil;k:=true;

for i:=1 to 8 do hyt(a[i],first);

hyt1(root);writeln;

end.

4.5 归并排序

归并就是将多个有序的数列合成一个有序的数列。将两个有序序列合并为一个有序序列叫二路归并(merge).归并排序就是n长度为1的子序列,两两归并最后变为有序的序列。

1.二路归并

例1:将有序表L1=(1,5,7),L2=(2，3,4,6,8，9,10)合并一个有序表 L.

program gb;

const m=3;n=7;

type arrl1=array[1..m] of integer;

arrl2=array[1..n] of integer;

arrl=array[1..m+n] of integer;

var a:arrl1;

b:arrl2;

c:arrl;

i,j,k,r:integer;

begin

write('Enter l1(sorted):');

for i:=1 to m do read(a[i]);

write('Enter l2(sorted):');

for i:=1 to n do read(b[i]);

i:=1;j:=1;k:=0;

while (i<=m) and (j<=n) do

begin

k:=k+1;

if a[i]<=b[j] then begin c[k]:=a[i];i:=i+1; end

else begin c[k]:=b[j];j:=j+1;end;

end;

if i<=m then for r:=i to m do c[m+r]:=a[r];

if j<=n then for r:=j to n do c[n+r]:=b[r];

writeln('Output data:');

for i:=1 to m+n do write(c[i]:5);

writeln;

end.

2.归并排序

program gbpx;

const maxn=7;

type arr=array[1..maxn] of integer;

var a,b,c:arr;

i:integer;

procedure merge(r:arr;l,m,n:integer;var r2:arr);

var i,j,k,p:integer;

begin

i:=l;j:=m+1;k:=l-1;

while (i<=m)and (j<=n) do

begin

k:=k+1;

if r[i]<=r[j] then begin r2[k]:=r[i];i:=i+1 end

else begin r2[k]:=r[j];j:=j+1 end

end;

if i<=m then

for p:=i to m do begin k:=k+1;r2[k]:=r[p] end;

if j<=n then

for p:=j to n do begin k:=k+1;r2[k]:=r[p] end;

end;

procedure mergesort( var r,r1:arr;s,t:integer);

var k:integer; c:arr;

begin

if s=t then r1[s]:=r[s] else

begin

k:=(s+t) div 2;

mergesort(r,c,s,k);

mergesort(r,c,k+1,t);

merge(c,s,k,t,r1)

end;

end;

begin

write('Enter data:');

for i:= 1 to maxn do

read(a[i]);

mergesort(a,b,1,maxn);

for i:=1 to maxn do

write(b[i]:9);

writeln;

end.

4.6 线形排序

以上我们讨论的算法均是基于比较的排序算法，在排序算法中有基于数字本身的算法：计数、桶、基数排序。

1.计数排序

基本思想是对于序列中的每一元素x,确定序列中小于x的元素的个数。

例：n个整数序列且每个值在[1,m],排序之。

program jspx;

const m=6;n=8;

var i,j:integer;

a,b:array[1..n] of integer;

c:array[1..m] of integer;

begin

writeln('Enter data:');

for i:=1 to n do read(a[i]);

for i:=1 to m do c[i]:=0;

for i:=1 to n do c[a[i]]:=c[a[i]]+1;

for i:=2 to m do c[i]:=c[i]+c[i-1];

for i:=n downto 1 do

begin

b[c[a[i]]]:=a[i];

c[a[i]]:=c[a[i]]-1;

end;

writeln('Sorted data:');

for i:= 1 to n do

write(b[i]:6);

end.

2.桶排序

桶排序的思想是若待排序的记录的关键字在一个明显有限范围内(整型)时,可设计有限个有序桶,每个桶装入一个值,顺序输出各桶的值,将得到有序的序列。

例：输入n个0到100之间的整数，由小到大排序输出。

program tpx;

const n=7;

var b:array[0..100] of integer;

k:0..100;

i:integer;

begin

write('Enter date:(0-100)');

for i:=0 to 100 do b[i]:=0;

for i:= 1 to n do

begin

read(k);

b[k]:=b[k]+1;

end;

writeln('Output data:');

for i:=0 to 100 do

while b[i]>0 do begin write(i:6);b[i]:=b[i]-1 end;

writeln;

end.

3.基数排序

基本思想是对n个元素依次按k,k-1,...1位上的数字进行桶排序。

program jspx;

const n=8;

type link=^node;

node=record

data:integer;

next:link;

end;

var i,j,l,m,k:integer;

a:array[1..n] of integer;

s:string;

q,head:array[0..9] of link;

p,p1:link;

begin

writeln('Enter data:');

for i:=1 to n do read(a[i]);

for i:=5 downto 1 do

begin

for j:=0 to 9 do

begin

new(head[j]);

head[j]^.next:=nil;

q[j]:=head[j]

end;

for j:=1 to n do

begin

str(a[j],s);

for k:=1 to 5-length(s) do

s:='0'+ s;

m:=ord(s[i])-48;

new(p);

p^.data:=a[j];

p^.next:=nil;

q[m]^.next:=p;

q[m]:=p;

end;

l:=0;

for j:=0 to 9 do

begin

p:=head[j];

while p^.next<>nil do

begin

l:=l+1;p1:=p;p:=p^.next;dispose(p1);a[l]:=p^.data;

end;

end;

end;

writeln('Sorted data:');

for i:= 1 to n do

write(a[i]:6);

end.

4.7各种排序算法的比较

1.稳定性比较

插入排序、冒泡排序、二叉树排序、二路归并排序及其他线形排序是稳定的

选择排序、希尔排序、快速排序、堆排序是不稳定的

2.时间复杂性比较

插入排序、冒泡排序、选择排序的时间复杂性为O(n2)

其它非线形排序的时间复杂性为O(nlog2n)

线形排序的时间复杂性为O(n);

3.辅助空间的比较

线形排序、二路归并排序的辅助空间为O(n),其它排序的辅助空间为O(1);

4.其它比较

插入、冒泡排序的速度较慢，但参加排序的序列局部或整体有序时，这种排序能达到较快的速度。

反而在这种情况下，快速排序反而慢了。

当n较小时，对稳定性不作要求时宜用选择排序，对稳定性有要求时宜用插入或冒泡排序。

若待排序的记录的关键字在一个明显有限范围内时,且空间允许是用桶排序。

当n较大时，关键字元素比较随机，对稳定性没要求宜用快速排序。

当n较大时，关键字元素可能出现本身是有序的，对稳定性有要求时，空间允许的情况下。

宜用归并排序。

当n较大时，关键字元素可能出现本身是有序的，对稳定性没有要求时宜用堆排序。

关于合肥市青少年信息学竞赛更多的信息，请关注查字典合肥奥数网“青少年信息学竞赛”频道。

信息学竞赛常用算法与策略：回溯

信息学竞赛常用算法与策略：递归

信息学竞赛常用算法与策略：算法的概念

青少年信息学竞赛Pascal语言：程序调试（十一）

更多精彩内容推荐>>

【信息学竞赛常用算法与策略：排序】相关文章：

★ 2015年第13届走美杯六年级获奖名单（一聪考点）

★ 2015年第十三届走美杯数学竞赛现可查分！

★ 第十届希望杯数学竞赛初赛在线估分

★ 如何报名参加杯赛？

★ 2013年走美杯六年级初赛试题及答案

★ 2012年第十届“走美杯”长沙赛区初赛公告

★ 第九届走美杯五年级B试题

★ 第一次学习奥数获得走美三等奖的秘诀

★ 什么是数学建模论文？

★ 2012年走美杯初赛试题及答案（三年级）