计算机处理数据包括排序、检索（查找）、修改和删除操作。我们研究排序算法有几点充分理由。首先,是因为它实际应用非常频繁，计算机厂家…… //这个你要听吗? 不废话了。
//为了说明方便.定义如下数组: a:array[1..10] of integer;temp: 中间变量 排序: 从大到小
l 选择排序
1.基本的 选择排序
<1>基本思想
首先从要排序的数中选择最大的数,将它放在第一个位置,然后从剩下的数中选择最大的数放在第二个位置,如此继续,直到最后从剩下的两个数中选择最大的数放在倒数第二个位置,剩下的一个数放在最后位置,完成排序.
下表是六个元素的排序的过程
4 5 7 1 2 3
┗━━┛
5 4 7 1 2 3
┗━━━━┛
7 4 5 1 2 3
┗━━━━━━┛
7 4 5 1 2 3
┗━━━━━━━━━━┛ 第一趟结束
⑦ 4 5 1 2 3
┗━┛
7 5 4 1 2 3
┗━━━┛
7 5 4 1 2 3
┗━━━━━┛
7 5 4 1 2 3
┗━━━━━━━┛ 第二趟结束
7 ⑤ 4 1 2 3
┗━┛
7 5 4 1 2 3
┗━━━┛
7 5 4 1 2 3
┗━━━━━┛ 第三趟结束
7 5 ④ 1 2 3
┗━┛
7 5 4 2 1 3 第四趟结束
┗━━━┛
7 5 4 ③ 1 2
┗━┛ 第五趟结束
7 5 4 3 ② ①
<2>算法实现
for i:=1 to 9 do
for j:=i+1 to 10 do
if a[i]<a[j]
begin
temp:=a[i];
a[i]:=a[j];
a[j]:=temp;
end;
2.改进
以上排序方案每次交换两个元素需要执行三个语句,过多的交换必定要花费许多时间.改进方案是在内循环的比较中找出最大值元素的下标,在内循环结束时才考虑是否要调换.
代码如下
for i:=1 to 9 do
begin
k:=i;
for j:=i+1 to 20 do
if a[j]>a[k]
then k:=j;
if i<k {不可能大于}
then begin
temp:=a[i];
a[i]:=a[k];
a[k]:=temp;
end;
end;
l 冒泡排序
1.基本的冒泡排序
<1> 基本思想
依次比较相邻的两个数,把大的放前面,小的放后面.即首先比较第1个数和第2个数,大数放前,小数放后.然后比较第2个数和第3个数......直到比较最后两个数.第一趟结束,最小的一定沉到最后.重复上过程,仍从第1个数开始,到最后第2个数.然后......
由于在排序过程中总是大数往前,小数往后,相当气泡上升,所以叫冒泡排序.
下面是6个元素的排序的过程
4 5 7 1 2 3
┗━━┛
5 4 7 1 2 3
┗━━┛
5 7 4 1 2 3
┗━━┛
5 7 4 1 2 3
┗━━┛
5 7 4 2 1 3
┗━━┛ 第一趟结束
5 7 4 2 3 ①
┗━━┛
7 5 4 2 3 1
┗━━┛
7 5 4 2 3 1
┗━━┛
7 5 4 2 3 1
┗━━┛ 第二趟结束
7 5 4 3 ② 1
┗━━┛
7 5 4 3 2 1
┗━━┛
7 5 4 3 2 1
┗━━┛ 第三趟结束
7 5 4 ③ 2 1
┗━━┛
7 5 4 3 2 1
┗━━┛ 第四趟结束
7 5 ④ 3 2 1
┗━━┛ 第五趟结束
⑦ ⑤ 4 3 2 1
<2> 算法实现
for i:=1 to 9 do
for j:=1 to 10-i do
if a[j]<a[j+1]
then begin
temp:=a[j];
a[j]:=a[j+1];
a[j+1]:=temp;
end;
2 改进
上例中,可以发现,第二趟结束已经排好序.但是计算机此时并不知道已经排好序.所以,还需进行一次比较,如果没有发生任何数据交换,则知道已经排好序,可以不干了.因此第三趟比较还需进行,第四趟、第五趟比较则不必要.
我们设置一个布尔变量bo 来记录是否有进行交换.值为false 进行了比较 true 则没有
代码如下
i:=1;
repeat
bo:=true;
for j:=1 to 10-i
if a[j]<a[j+1] then
begin
temp:=a[j];
a[j]:=a[j+1];
a[j+1]:=temp;
bo:=false;
end;
inc(i);
until bo;
3.再次改进
如果说是有20个元素．数据序列是8,3,4,9,7再后跟着１５个大于９且已经排好序的数据．在第三趟后算法终止．总共做了19+18+17=54次比较使得绝大多数已排好序的数据在一遍扫描后足以发现他们是排好序的情况下仍然被检查３遍．
我们改进如下
flag:=10;
while flag>0 do
begin
k:=flag-1;
flag:=0;
for i:=1 to k do
if a[i]<a[i+1] then
begin
temp:=a[i];
a[i]:=a[i+1];
a[i+1]:=temp;
flag:=i;
end;
end;
改进的冒泡算法对上述数据进行的比较次数是19+4+2=24.
l 希尔排序
<1> 基本思想
希尔排序法是1959年由D.L.Shell提出来的,又称减少增量的排序。下表是以八个元素排序示范的例子.在该例中,开始时相隔4个成分,分别按组进行排序,这时每组2个成分,共4组; 然后相隔2个成分,在按组排序......最后,对所有相邻成分进行排序.
可参阅<<计算机程序设计技巧??第三卷排序查找
<2> 算法实现
j:=10;
i:=1;
while j>1 do
begin
j:=j div 2;
repeat
alldone:=true;
for index:=1 to 10-j do
begin
i:=index+j;
if a[index]<a[i] then
begin
temp:=a[index];
a[index]:=a[i];
a[i]:=temp;
alldone:=false;
end;
end;
until alldone
end;
//说句实话,这个很少有人用.:( 当然我也不会,书上抄的
l 插入排序
<1> 基本思想
//对不起,我没书.所以是我自己讲.我很菜．不要介意
插入排序的思想就是读一个，排一个． //也许是这样,起码我是这么认为的：）
将第１个数放入数组的第１个元素中，以后读入的数与已存入数组的数进行比较，确定它在从大到小的排列中应处的位置．将该位置以及以后的元素向后推移一个位置，将读入的新数填入空出的位置中．
<2> 算法实现 ｛加了读入语句｝
procedure insert(x,num:integer);
var
i,pos:integer;
search:boolean;
begin
pos:=1;
search:=true;
while search and (pos<=num ) do
if x>a[pos]
then search:=fasle
else inc(pos);
for i:=num downto pos do
a[i+1]:=a[i];
a[pos]:=x;
num:=num+1;
end;
num:=0 {当前数组的长度｝
for i:=1 to 10 do
begin
read(x);
intert(x,num)
end;
l 合并排序
<1> 基本思想
合并排序的算法就是二分法。
分解：将n个元素分解成各含 一半元素的子序列。
解决：用合并排序法对两个子序列递归地排序。
合并：合并两个已排序的子序列排序结果。
在对子序列排列时，当其长度为1时递归结束，因为单个元素被认为是已排好序的.合并排序的.合并排序的关键步骤在于合并目前产生的两个已排好序的子序列:
A[p..q] 和 A[q+1…r];
将它们合并成一个已排好序的子序列A[p..r]. 我们引入一个辅助过程merge(A,p,q,r)来完成这一项合并工作,其中A是数组,p,q,r是下标.
<2> 算法实现
procedure merge( p,q,r:integer);
var
i,j,t:integer;
it:array[1..10] of integer;
begin
t:=p; i:=p; j:=q+1;
while t<=r do
begin
if (i<=q) and ((j>j) or (a[i]<=a[j]))
then begin
it[t]:=a[i]; inc(i);
end
else begin
it[t]:=a[j]; inc(j);
end;
inc(t);
end;
for i:=p to r do a[i]:=t[i];
end;
procedure merge_sort(p,r:integer);
var q:integer;
begin
if p<>r then begin
q:=(p+r-1) div 2 ;
merge_sort(p,q);
merge_sort(q+1,r);
merge(p,q,r);
end;
end;
begin
merge_sort(1,10);
end.
l 快速排序
<1> 基本思想
快速排序的基本思想是基于分治策略的。对于输入的子序列L[p..r]，如果规模足够小则直接进行排序，否则分三步处理：
分解(Divide)：将输入的序列L[p..r]划分成两个非空子序列L[p..q]和L[q+1..r]，使L[p..q]中任一元素的值不大于L[q+1..r]中任一元素的值。
递归求解(Conquer)：通过递归调用快速排序算法分别对L[p..q]和L[q+1..r]进行排序。
合并(Merge)：由于对分解出的两个子序列的排序是就地进行的，所以在L[p..q]和L[q+1..r]都排好序后不需要执行任何计算L[p..r]就已排好序。
这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。
设为首页
加入收藏
总编信箱
投稿或申请专栏请先 [登 陆]
