原本还想不起整理一下关于排序思想的文章的.但是今天我考c语言的选修课的时候,发现我连很简单的选择排序都不会了.所以,整理一下排序的种类和实现方法,以供参考!!!
概述
排序(sorting)是计算机程序设计中的一种重要运算,它的功能是将一个数据元素(或记录)的任意序，重新排列成一个按关键字有序的序列。
排序方法分为两大类: 内部排序 外部排序
为了便于讨论,在此首先要对排序下一个确切的定义:
假设含n个记录的序列为{R1,R2,…,Rn}其相应的关键字序列为 {K1,K2,…,Kn}需确定1,2,…,n的一排列p1,p2,…,pn,使其相应的关键字满足如下的非递减(或非递增)关系
Kp1<=Kp2<=…<=Kpn使式(10-1)的序列成为 一个按关键字有序的序列{Rp1,Rp2,…,Rpn}这样一种操作称为排序。
内部排序
内部排序:指待排序记录存放在计算机随机存储器中进行的排序过程。
内部排序包括:
1. 插入排序 2. 选择排序 3. 交换排序
4. 基数排序 5. 归并排序 等几种排序.
插入排序
插入排序(Insertion Sort)的基本方法是:
每步将一个待排序的记录,按其排序值的大小插到前面已经排序的文件中适当位置,直到全部插入完为止。
插入排序包括:
1.直接插入 2.折半插入 3.表插入 4.希尔插入 等排序
一. 直接插入排序
直接插入排序的基本思想
直接插入排序(Straight Insertion Sort)是在插入第i个记录时,R1,R2,…,Ri-1已经排好序(严格R1,R2, …,Ri-1).这时采用Ki与Ki-1,Ki-2,…,K1依次进行比较,找出 该插入的位置,然后将Ki插入,原位置的记录向后顺推。
1. [每循环一次插入一个记录]
循环 i以1为步长,从2到n,执行
(1) [准备]
R[0]:=R[i];
j:=i-1
(2) [找插入位置后移]
循环 当R[0].key<R[j].key时,反复执行
R[j+1]:=R[j];
j:=j-1
(3) [插入]
R[j+1]:=R[0]
2. [算法结束]
此算法引用了一个附加的记录空间R[0],每次将要插入记录R[i]的付本记R[0],使得在第(2)步中,当R[i].key<R[1].key 时也能自动控制循环的结束。
直接插入排序示例
设待排序的记录共7个,排序码分别为49,38,65,97,76。从I=2开始经过四步插入完成全部排序工作。
Flash 动画的演示过程： 1.算法 2.练习题
程序
对49,38,65,97,76,13,27.这7个数用直接插入排序法进行排序.
1. C语言 2. PASCAL语言
1. C语言
/*直接插入排序*/
# define N 8
main()
{int i,j,R[N];
/*输入数据*/
printf("请输入7个数:");
for(i=1;i<N;i++)
scanf("%d",&R[i]);
printf("\n");
for(i=2;i<N;i++)
{R[0]=R[i]; /*R[0]是监视哨*/
j=i-1;
while(R[0]<R[j]) /*进行元素动,以便腾出一个位置插入*/
{R[j+1]=R[j];
j- -;
}
R[j+1]=R[0]; /*在j+1位置插入*/
/*输入结果*/
for(i=1;i<N;i++)
printf("%6d",R[i]);
}
运行结果:
请输入7个数:49 38 65 97 76 13 27 按ENTER键
13 27 38 49 65 76 97
2. PASCAL语言
/*直接插入排序*/
program straisort(input,output);
const
n=7;
var
R:array[0..n] of integer;
i,j:integer;
BEGIN
/*输入数据*/
for i:=1 to n do
read(R[i]);
for i:=2 to n do
begin
R[0]:=R[i];
j:=i-1;
while R[0]<R[k] do
begin
R[j+1]:=R[j];
j:=j-1 end;
R[j+1]:=R[0]
end;
/*输入结果*/
for i:=1 to 7 do
write(R[i])
END.
运行结果:
请输入7个数:49 38 65 97 76 13 27 按ENTER键
13 27 38 49 65 76 97
二. 折半插入排序
折半插入排序基本思想:
折半插入排序(Binary Insertion Sort), 就是在插入Ri时(这时R1,R2,…,Ri-1已排序),取R┗i/2┛的排序码K┗i/2┛与Ki进行比较(┗i/2┛表示取不大于i/2的最大整 数),如果Ki<K┗i/2┛,Ri只能插在R1到R┗i/2┛之间,故可以在R1到R┗i/2┛-1之间继续使用折半法,否则可以在R┗i/2┛ +1到Ri-1之间使用折半法,如此反复直到最后能确定插入的位置为止.一般而言,在R1到Rr之间采用折半法,其中间结点为R┗(l+r)/2┛,经过 一次比较,便可排除一半结点,把可能插入的区间缩小了一半,故称折半法.
算法 折半插入排序
1.[每循环一次插入一个R[i]]
循环 i以1 为步长,从2到n,执行
(1) [准备]
R[0]=R[i]; X:=R[i]; l:=1; r:=i-1
(2) [折半法找插入位置]
循环 当l<=r时,反复执行下列语句
i) m:=┗(l+r)/2┛
ii) 若X.key<R[m].key
则 r:=m-1
否则 l:=m+1
(3) [后移]
循环 j以-1为步长,从i-1到1,执行
R[j+1]:=R[j];
R[r+1]=R[0]
(4) [插入]
R[l]:=X
2.[算法结束]
注意:算法中,用l>r来控制折半法结束.这时l 就是R[i]就插入的位置.另外在ii)步中,采用X.key<R[m].key 作条件,从而保证了排序过程是稳定的.
折半插入排序示例
设待排序的记录共8个,排序码分别为28,13,72,85,39,41,6,20. 在前七个记录都已排序的基础上,采用折半插入第八个记录的过程如下:
(A) [6 13 28 39 41 72 85] (20)
l=1 m=4 r=7
20<39, m-1=3=r
(B) [6 13 28] 39 41 72 85 (20)
l=1 m=2 r=3
20>13, m+1=3=l
(C) 6 13 [28] 39 41 72 85 (20)
l=m=r=3
20<28, m-1=2=r
l>r,二分法结束,l=3为插入位置
(D) 6 13 (20) 28 39 41 72 85
程序
对28,13,72,85,39,41,6,20.这8个数用折半法进行排序.
1. C语言 2. PASCAL语言
1. C语言
/*折半插入排序*/
# define N 9
main()
{int i,j,l,r,x,m,R[N];
printf("\n please input:");
for(i=1;i<N;i++)
scanf("%d",&R[i]);
printf("\n");
for(i=2;i<N;i++)
{R[0]=R[i];
x=R[i];
l=1;
r=i-1;
while(l<=r)
{m=(l+r)/2;
if(x<R[m])
r=m-1;
else l=m+1;
}
for(j=i-1;j>=r+1;j- -)
R[j+1]=R[j];
R[r+1]=R[0];
}
for(i=1;i<N;i++)
printf("%6d",R[i]);
}
运行结果:
please input:
28 13 72 85 39 41 6 20 按ENTER键
6 13 20 28 39 41 72 85
2. PASCAL语言
{折半插入排序}
program binsort(input,output);
const
n=8;
var
R:array[1..n] of integer;
i,j,l,r,x,m:integer;
BEGIN
for i:=1 to n do
read(R[i]);
for i:=2 to n do
begin
R[0]=R[i];
x:=R[i];
l:=1;
r:=i-1;
while l<=r do
begin
m:=trunc((l+r)/2);
if x<R[m]
then r:=m-1
else l=m+1
end;
for j:=i-1 downto 1 do
R[j+1]:=R[j];
R[r+1]:=R[0]
end;
for i:=1 to 8 do
write(R[i])
END.
运行结果:
please input:28 13 72 85 39 41 6 20 按ENTER键
6 13 20 28 39 41 72 85
三. 表插入排序
表插入排序的基本思想:
在结点中,设一指针字段,插入Ri 时R1到Ri-1已经用指针排序码值不减次序链结起来,这时采用顺序比较的方法找到Ri应该插入的位置,然后作链表的插入,便得到从R1到Ri的已排序的链表.如此反复,直到把Rn插入链表排序即完成.
算法 表插入排序
1. [准备]
R[0].link:=n;
R[n].link:=0
2. [插入]
循环 i以-1为步长,从n-1到1,执行
(1) p:=R[0].link; q:=0
(2) 循环 当p>0且R[p].key<R[i].key时,反复执行
q:=p; p:=R[p].link
(3) R[q].link:=i; R[i].link:=p
3. [算法结束]
算法中从i=n开始,从后往前作插入,并且在R[i].key=R[p].key时,将R[i]插在R[p]的前面,没有改变R[p]和R[i]原来的相对位置,所以排序是稳定的.
表插入示例
设待排序的记录 共8个,排序码分别为28,13,72,85,39,41,6,20. 执行表插入排序可以用一个数组R 存放待排序的文件 ,记录之间的链接关系用link字段表示,link字段取值为数组元素的下标,头指针就放在R[0].link 字段中.初始状态可用图(a)表示,其中R[i].link=i+1表示初始链接次序,该次序并不影响排序结果,排序过程是从R[8]到R[1]依次将记 录按排序码值一个一个插入,排序中不移动任何结点,排序结果如图(b)所示.表插入排序是从R[0].link所指位置沿link的链向依次比较过程如 下:
key link key link
R[0] 1 R[0] 1
[1] 28 2 [1] 28 2
[2] 13 3 [2] 13 3
[3] 72 4 [3] 72 4
[4] 85 5 [4] 85 5
[5] 39 6 [5] 39 6
[6] 41 7 [6] 41 7
[7] 6 8 [7] 6 8
[8] 20 0 [8] 20 0
(a)初态 (b)终态
四. 希尔排序
希尔排序的基本思想
希尔排序(Shell's Methed) 又称"缩小增量排序",它的基本思想是:先将整个待排记录序列分割成为若干子序列分别进行直接插入排序,待整个序列中的记录"基本有序"时,再对全体记录进行一次直接插入.
作法:先 取定一个整数d1<n,把全部记录分成d1个组,所有距离为d1倍数的记录放在一组中,在各组内进行排序;然后取d2<d1重复上述分组和排 序工作;直到取di=1即所有记录放在一组中排序为上.各组内的排序可以采用直接插入法.由于开始d的取值较大,每组中记录数较少,所以排序比较快,后来 di逐步变小,每组内的记录数逐步变多,但由于已经按di-1作为距离排过序,所以也比较容易排.
算法 希尔排序
1. [准备]
k:=D
2. [排序]
循环 当k>=1时,反复执行下列语句
(1) 循环 i以1为步长,从k+1到n,执行
i) X:=R[i];
j:=i-k
ii) 循环 当j>0且X.key<R[j].key时,反复执行下列语句
R[j+k]:=R[j];
j:=j-k
iii) R[j+k]:=x
(2) k:=┗k/2┛
3.[算法结束]
希尔排序算法的一般来说比直接插入排序要快,是不稳定的排序方法
72 73 71 23 94 16 05 68
用希尔排序法排序,取d1=n/2=4,di+1=┗di/2┛,排序过程如图所示:
[初始关键字]: 72 73 71 23 94 16 05 68
72__________________94
73__________________16
71__________________05
23___________________68
(a) d1=4
一趟排序结果: 72 16 05 23 94 73 71 68
72________05________94________71
16________23________73________68
(b) d2=2
二趟排序结果: 05___16___71___23___72___68___94___73
(c) d3=1
三趟排序结果: 05 16 23 68 71 72 73 94
程序
对72 73 71 23 94 16 05 68这8个数用希尔排序法进行排序
1. C语言 2. PASCAL语言
1. C语言
/*希尔插入排序*/
# define N 9
main()
{int i,j,k,x,D,R[N];
printf("please input:");
for(i=0;i<N;i++)
scanf("%d",&R[i]);
printf("\n");
D=N/2;
k=D;
while(k>=1)
{for(i=k+1;i<N;i++)
{x=R[i];
j=i-k;
}
while(j>0 && x<R[j])
{R[j+k]=R[j];
j=j-k;
}
R[j+k]=x
}
k=k/2;
}
for(i=1;i<N;i++)
printf("%6d",R[i]);
}
运行结果:
please input:72 73 71 23 94 16 05 68 按ENTER键
5 16 23 68 71 72 73 94
2. PASCAL语言
program shellsort(input,output);
const
n=8;
var
R:array[1..n] of integer;
i,j,k,x,D:integer;
BEGIN
for i:=1 to n do
read(R[i]);
D:=trunc(n/2);
k:=D;
while k>=1 do
begin
for i:=k+1 to n do
begin
x:=R[i];
j:=i-k;
while j>0 and x<R[j] do
begin
R[j+k]:=R[j];
j:=j-k
end;
R[j+k]:=x
end;
k:=trunc(k/2)
end;
for i:=1 to 8 do
write(R[i])
END.
运行结果:
please input:72 73 71 23 94 16 05 68 按ENTER键
5 16 23 68 71 72 73 94
