排序算法五例 - search readpudncom

1、排序算法五例排序算法五例一、插入排序(ionSt)1.基本思想：每次將一個待排序的數據元素，插入到前面已經排好序的數列中的適當位置，使數列依然有序；直到待排序數據元素全部插入完為止。2.排序過程：【示例】：[初始關鍵字][49]38659776132749J=2(38)[3849]659776132749J=3(65)[384965]9776132749J=4(97)[38496597]76132749J=5(76)[384965769

2、7]132749J=6(13)[133849657697]2749J=7(27)[13273849657697]49J=8(49)[1327384949657697]ProcedureSt(VarR:FileType)對R[1..N]按遞增序進行插入排序R[0]是監(jiān)視哨BeginfI:=2ToNDo依次插入R[2]...R[n]beginR[0]:=R[I]J:=I1WhileR[0]R[J]Do查找R[I]的插入位置beginR[J1

3、]:=R[J]將大于R[I]的元素后移J:=J1endR[J1]:=R[0]插入R[I]endEndSt二、選擇排序1.基本思想：每一趟從待排序的數據元素中選出最?。ɑ蜃畲螅┑囊粋€元素，順序放在已排好序的數列的最后，直到全部待排序的數據元素排完。2.排序過程：【示例】：初始關鍵字[4938659776132749]FI:=1ToN1Do做N1趟排序beginNoSwap:=True置未排序的標志FJ:=N1DownTo1Do從底部往上掃

4、描beginIfR[J1]R[J]Then交換元素beginTemp:=R[J1]R[J1:=R[J]R[J]:=TempNoSwap:=FalseendendIfNoSwapThenReturn本趟排序中未發(fā)生交換，則終止算法endEndBubbleSt四、快速排序（QuickSt）1.基本思想：在當前無序區(qū)R[1..H]中任取一個數據元素作為比較的“基準“(不妨記為X)，用此基準將當前無序區(qū)劃分為左右兩個較小的無序區(qū)：R[1..I1

5、]和R[I1..H]，且左邊的無序子區(qū)中數據元素均小于等于基準元素，右邊的無序子區(qū)中數據元素均大于等于基準元素，而基準X則位于最終排序的位置上，即R[1..I1]≤X.Key≤R[I1..H](1≤I≤H)，當R[1..I1]和R[I1..H]均非空時，分別對它們進行上述的劃分過程，直至所有無序子區(qū)中的數據元素均已排序為止。2.排序過程：【示例】：初始關鍵字[4938659776132749］第一次交換后［273865977613494

6、9］第二次交換后［2738499776136549］J向左掃描，位置不變，第三次交換后［2738139776496549］I向右掃描，位置不變，第四次交換后［2738134976976549］J向左掃描［2738134976976549］（一次劃分過程）初始關鍵字［4938659776132749］一趟排序之后［273813］49［76976549］二趟排序之后［13］27［38］49［4965］76［97］三趟排序之后13273849