排序算法
计算机处理数据包括排序、检索（查找）、修改和删除操作。我们研究排序算法有几点充分理由。首先,是因为它实际应用非常频繁，计算机厂家…… 这个你要听吗? 不废话了。为了说明方便.定义如下数组: a:array[1…10] of integer;temp: 中间变量首先从要排序的数中选择最大的数,将它放在第一个位置,然后从剩下的数中选择最大的数放在第二个位置,如此继续,直到最后从剩下的两个数中选择最大的数放在倒数第二个位置,剩下的一个数放在最后位置,完成排序。下表是六个元素的排序的过程。
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 ② ①
算法实现
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;
改进
以上排序方案每次交换两个元素需要执行三个语句,过多的交换必定要花费许多时间.改进方案是在内循环的比较中找出最大值元素的下标,在内循环结束时才考虑是否要调换.
代码如下
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;
冒泡排序
依次比较相邻的两个数,把大的放前面,小的放后面.即首先比较第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
算法实现
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;
改进
上例中,可以发现,第二趟结束已经排好序.但是计算机此时并不知道已经排好序.所以,还需进行一次比较,如果没有发生任何数据交换,则知道已经排好序,可以不干了.因此第
三趟比较还需进行,第四趟、第五趟比较则不必要.
我们设置一个布尔变量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;
再次改进
如果说是有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.
希尔排序
希尔排序法是1959年由D.L.Shell提出来的,又称减少增量的排序。下表是以八个元素排序示范的例子.在该例中,开始时相隔4个成分,分别按组进行排序,这时每组2个成分,共4组;
然后相隔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;
插入排序
基本思想
对不起,我没书.所以是我自己讲.我很菜．不要介意插入排序的思想就是读一个，排一个． //也许是这样,起码我是这么认为的：）将第１个数放入数组的第１个元素中，以后读入的数与已存入数组的数进行比较，确定它在从大到小的排列中应处的位置．将该位置以及以后的元素向后推移一个位置，将读入的新数填入空出的位置中．
算法实现
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;
合并排序
基本思想
合并排序的算法就是二分法。
分解：将n个元素分解成各含 一半元素的子序列。
解决：用合并排序法对两个子序列递归地排序。
合并：合并两个已排序的子序列排序结果。
在对子序列排列时，当其长度为1时递归结束，因为单个元素被认为是已排好序的.合并排序的.合并排序的关键步骤在于合并目前产生的两个已排好序的子序列:
A[p…q] 和 A[q+1…r];
将它们合并成一个已排好序的子序列A[p…r]. 我们引入一个辅助过程merge(A,p,q,r)来完成这一项合并工作,其中A是数组,p,q,r是下标.
算法实现
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[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]就已排好序。
这个解决流程是符合分治法的基本步骤的。因此，快速排序法是分治法的经典应用实例之一。
排序算法是一种基本并且常用的算法。由于实际工作中处理的数量巨大，所以排序算法 对算法本身的速度要求很高。而一般我们所谓的算法的性能主要是指算法的复杂度，一般用
O方法来表示。在后面我将 给出详细的说明。
对 于排序的算法我想先做一点简单的介绍，也是给这篇文章理一个提纲。 我将按照算法的复杂度，从简单到难来分析算法。第一部分是简单排序算法，后面你将看到他们的共同
点是算法复杂度为O(N*N)（因为没有使用word,所 以无法打出上标和下标）。第二部分是高级排序算法，复杂度为O(Log2(N))。这里我们只介绍一种算法。另外还有几种算法因为
涉及树与堆的概念，所以 这里不于讨论。 第三部分类似动脑筋。这里的两种算法并不是最好的（甚至有最慢的），但是算法本身比较奇特，值得参考（编程的角度）。同时也可
以让我们从另外的角度来认识 这个问题。现在，让我们开始吧：
简单排序算法
由于程序比较简单，所以没有加什么注释。所有的程序都给出了完整的运行代码，并在我的VC环境
下运行通过。因为没有涉及MFC和WINDOWS的内容，所以在BORLAND C++的平台上应该也不会有什么
问题的。在代码的后面给出了运行过程示意，希望对理解有帮助。
