排序算法:排序算法五例

、插入排序(InsertionSort)
1.基本思想:
每次将个待排序数据元素插入到前面已经排好序数列中适当位置使数列依然有序；直到待排序数据元素全部插入完为止
2.排序过程:　
【举例】:
[关键字][49]38659776132749
J=2(38)[3849]659776132749
J=3(65)[384965]9776132749
J=4(97)[38496597]76132749
J=5(76)[3849657697]132749
J=6(13)[133849657697]2749
J=7(27)[13273849657697]49
J=8(49)[1327384949657697]


ProcedureInsertSort(VarR:FileType);
//对R[1..N]按递增序进行插入排序,R[0]是监视哨//
Begin
forI:=2ToNDo//依次插入R[2],...,R[n]//
begin
R[0]:=R[I];J:=I-1;
WhileR[0]<R[J]Do//查找R[I]插入位置//
begin
R[J+1]:=R[J];//将大于R[I]元素后移//
J:=J-1
end
R[J+1]:=R[0];//插入R[I]//
end
End;//InsertSort//


2、选择排序
1.基本思想:
　　每趟从待排序数据元素中选出最小(或最大)个元素顺序放在已排好序数列最后直到全部待排序数据元素排完
2.排序过程:
【举例】:
关键字[4938659776132749]
第趟排序后13［38659776492749]
第 2趟排序后1327［659776493849]
第 3趟排序后132738[9776496549]
第 4趟排序后13273849[49976576]
第 5趟排序后1327384949[979776]
第 6趟排序后132738494976[7697]
第 7趟排序后13273849497676[97]
最后排序结果1327384949767697

ProcedureSelectSort(VarR:FileType);//对R[1..N]进行直接选择排序//
Begin
forI:=1ToN-1Do//做N-1趟选择排序//
begin
K:=I;
ForJ:=I+1ToNDo//在当前无序区R[I..N]中选最小元素R[K]//
begin
IfR[J]<R[K]ThenK:=J
end;
IfK<>IThen//交换R[I]和R[K]//
beginTemp:=R[I];R[I]:=R[K];R[K]:=Temp;end;
end
End;//SelectSort//


3、冒泡排序(BubbleSort)
1.基本思想:
　　两两比较待排序数据元素大小发现两个数据元素次序相反时即进行交换直到没有反序数据元素为止
2.排序过程:
　　设想被排序R［1..N］垂直竖立将每个数据元素看作有重量气泡根据轻气泡不能在重气泡的下原则从下往上扫描R凡扫描到违反本原则轻气泡就使其向上\"漂浮\"如此反复进行直至最后任何两个气泡都是轻者在上重者在下为止
【举例】:
4913131313131313
3849272727272727
6538493838383838
9765384949494949
7697654949494949
1376976565656565
2727769776767676
4949497697979797



ProcedureBubbleSort(VarR:FileType)//从下往上扫描起泡排序//
Begin
ForI:=1ToN-1Do//做N-1趟排序//
begin
NoSwap:=True;//置未排序标志//
ForJ:=N-1DownTo1Do//从底部往上扫描//
begin
IfR[J+1]<R[J]Then//交换元素//
begin
Temp:=R[J+1];R[J+1:=R[J];R[J]:=Temp;
NoSwap:=False
end;
end;
IfNoSwapThenReturn//本趟排序中未发生交换则终止算法//
end
End;//BubbleSort//

4、快速排序(QuickSort)
1.基本思想:
　　在当前无序区R[1..H]中任取个数据元素作为比较\"基准\"(不妨记为X)用此基准将当前无序区划分为左右两个较小无序区:R[1..I-1]和R[I+1..H]且左边无序子区中数据元素均小于等于基准元素右边无序子区中数据元素均大于等于基准元素而基准X则位于最终排序位置上即R[1..I-1]≤X.Key≤R[I+1..H](1≤I≤H)当R[1..I-1]和R[I+1..H]均非空时分别对它们进行上述划分过程直至所有无序子区中数据元素均已排序为止
2.排序过程:
【举例】:
关键字[4938659776132749］
第次交换后［2738659776134949］
第 2次交换后［2738499776136549］
J向左扫描位置不变第 3次交换后［2738139776496549］
I向右扫描位置不变第 4次交换后［2738134976976549］
J向左扫描［2738134976976549］
(次划分过程)

关键字［4938659776132749］
趟排序的后［273813］49［76976549］
2趟排序的后［13］27［38］49［4965］76［97］
3趟排序的后1327384949［65］7697
最后排序结果1327384949657697
各趟排序的后状态

ProcedureParttion(VarR:FileType;L,H:Integer;VarI:Integer);
//对无序区R[1,H]做划分I给以出本次划分后已被定位基准元素位置//
Begin
I:=1;J:=H;X:=R[I];//化X为基准//
Repeat
While(R[J]>=X)And(I<J)Do
begin
J:=J-1//从右向左扫描查找第1个小于X元素//
IfI<JThen//已找到R[J]〈X//
begin
R[I]:=R[J];//相当于交换R[I]和R[J]//
I:=I+1
end;
While(R[I]<=X)And(I<J)Do
I:=I+1//从左向右扫描查找第1个大于X元素///
end;
IfI<JThen//已找到R[I]>X//
beginR[J]:=R[I];//相当于交换R[I]和R[J]//
J:=J-1
end
UntilI=J;
R[I]:=X//基准X已被最终定位//
End;//Parttion//

ProcedureQuickSort(VarR:FileType;S,T:Integer);//对R[S..T]快速排序//
Begin
IfS<TThen//当R[S..T]为空或只有个元素是无需排序//
begin
Partion(R,S,T,I);//对R[S..T]做划分//
QuickSort(R,S,I-1);//递归处理左区间R[S,I-1]//
QuickSort(R,I+1,T);//递归处理右区间R[I+1..T]//
end;
End;//QuickSort//




5、堆排序(HeapSort)
1.基本思想:
堆排序是树形选择排序在排序过程中将R[1..N]看成是颗完全 2叉树顺序存储结构利用完全 2叉树中双亲结点和孩子结点的间内在关系来选择最小元素
2.堆定义:N个元素序列K1,K2,K3,...,Kn.称为堆当且仅当该序列满足特性:
Ki≤K2iKi≤K2i+1(1≤I≤[N/2])

堆实质上是满足如下性质完全 2叉树:树中任非叶子结点关键字均大于等于其孩子结点关键字例如序列10,15,56,25,30,70就是个堆它对应完全 2叉树如上图所示这种堆中根结点(称为堆顶)关键字最小我们把它称为小根堆反的若完全 2叉树中任非叶子结点关键字均大于等于其孩子关键字则称的为大根堆
3.排序过程:
堆排序正是利用小根堆(或大根堆)来选取当前无序区中关键字小(或最大)记录实现排序我们不妨利用大根堆来排序每趟排序基本操作是:将当前无序区调整为个大根堆选取关键字最大堆顶记录将它和无序区中最后个记录交换这样正好和直接选择排序相反有序区是在原记录区尾部形成并逐步向前扩大到整个记录区
【举例】:对关键字序列4213912324160588建堆
\">

\">

\">

\">

\">

ProcedureSt(VarR:FileType;I,M:Integer);
//在R[I..M]中R[I]使得以它为完全 2叉树构成堆事先已知其左、右子树(2I+1<=M时)均是堆//
Begin
X:=R[I];J:=2*I;//若J<=M,R[J]是R[I]左孩子//
WhileJ<=MDo//若当前被调整结点R[I]有左孩子R[J]//
begin
If(J<M)AndR[J].Key<R[J+1].KeyThen
J:=J+1//令J指向关键字较大右孩子//
//J指向R[I]左、右孩子中关键字较大者//
IfX.Key<R[J].KeyThen//孩子结点关键字较大//
begin
R[I]:=R[J];//将R[J]换到双亲位置上//
I:=J;J:=2*I//继续以R[J]为当前被调整结点往下层调整//
end;
Else
Exit//调整完毕退出循环//
end
R[I]:=X;//将最初被调整结点放入正确位置//
End;//St//

ProcedureHeapSort(VarR:FileType);//对R[1..N]进行堆排序//
　Begin
　　ForI:=NDivDownto1Do//建立堆//
　　　St(R,I,N)
　　ForI:=NDownto2do//进行N-1趟排序//
　　　begin
　　　　T:=R[1];R[1]:=R[I];R[I]:=T;//将当前堆顶记录和堆中最后个记录交换//
　　　　St(R,1,I-1)//将R[1..I-1]重成堆//
　　　end
End;//HeapSort//


6、几种排序算法比较和选择
1.选取排序思路方法需要考虑原因:
(1)待排序元素数目n；
(2)元素本身信息量大小；
(3)关键字结构及其分布情况；
(4)语言工具条件辅助空间大小等
2.小结:
(1)若n较小(n<=50)则可以采用直接插入排序或直接选择排序由于直接插入排序所需记录移动操作较直接选择排序多因而当记录本身信息量较大时用直接选择排序较好
(2)若文件状态已按关键字基本有序则选用直接插入或冒泡排序为宜
(3)若n较大则应采用时间复杂度为O(nlog2n)排序思路方法:快速排序、堆排序或归并排序快速排序是目前基于比较内部排序法中被认为是最好思路方法
(4)在基于比较排序思路方法中每次比较两个关键字大小的后仅仅出现两种可能转移因此可以用棵 2叉树来描述比较判定过程由此可以证明:当文件n个关键字随机分布时任何借助于\"比较\"排序算法至少需要O(nlog2n)时间
(5)当记录本身信息量较大时为避免耗费大量时间移动记录可以用链表作为存储结构



=span_ad>

延伸阅读

• 2011-9-21-- 二分排序算法,优秀算法系列--排序算法（二）
• 2011-9-12-- 排序算法,优秀算法系列--排序算法（一）
• 2010-12-9-- 冒泡排序算法,PHP 冒泡排序算法的实现代码
• 2010-12-9-- 冒泡算法,asp.net 冒泡算法的理解
• 2011-8-1-- paxos,Paxos算法
• 2011-7-26-- 快速排序算法,【原创】由快速排序引申而来--如何学习算法
• 2010-12-9-- 冒泡排序,asp 实现的冒泡排序程序
• 2011-6-20-- 排序算法总结,常用计算机排序算法简单总结
• 2011-5-19-- php快速排序,放出一个php快速排序的c扩展
• 2010-12-9-- 冒泡排序,asp.net下实现输入数字的冒泡排序