直接插入排序法演算法思想

1. 關於數據結構排序演算法的問題

選擇排序

插入排序：每次比較後最多移掉一個逆序，因此與冒泡排序的效率相同。但它在速度上還是要高點，這是因為在冒泡排序下是進行值交換，而在插入排序下是值移動，所以直接插入排序將要優於冒泡排序。直接插入法也是一種對數據的有序性非常敏感的一種演算法。在有序情況下只需要經過n-1次比較，在最壞情況下，將需要n(n-1)/2次比較。

選擇排序：簡單的選擇排序，它的比較次數一定：n(n-1)/2。也因此無論在序列何種情況下，它都不會有優秀的表現（從上100K的正序和反序數
據可以發現它耗時相差不多，相差的只是數據移動時間），可見對數據的有序性不敏感。它雖然比較次數多，但它的數據交換量卻很少。所以我們將發現它在一般情
況下將快於冒泡排序。

冒泡排序：在最優情況下只需要經過n-1次比較即可得出結果，（這個最優情況那就是序列己是正序，從100K的正序結果可以看出結果正是如此），但在最壞情況下，即倒序（或一個較小值在最後），下沉演算法將需要n(n-1)/2次比較。所以一般情況下，特別是在逆序時，它很不理想。它是對數據有序性非常敏感的排序演算法。
堆排序：由於它在直接選擇排序的基礎上利用了比較結果形成。效率提高很大。它完成排序的總比較次數為O(nlog2n)。它是對數據的有序性不敏感的一種演算法。但堆排序將需要做兩個步驟：－是建堆，二是排序（調整堆）。所以一般在小規模的序列中不合適，但對於較大的序列，將表現出優越的性能。

基數排序：在程序中採用的是以數值的十進制位分解，然後對空間採用一次性分配，因此它需要較多的輔助空間(10*n+10), （但我們可以進行其它分解，如以一個位元組分解，空間採用鏈表將只需輔助空間n+256）。基數排序的時間是線性的(即O(n))。由此可見，基數排序非常吸引人，但它也不是就地排序，若節點數據量大時宜改為索引排序。但基數排序有個前提，要關鍵字能象整型、字元串這樣能分解，若是浮點型那就不行了。

2. 排序法都有哪些

一、插入排序(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]

1. ProcereInsertSort(VarR:FileType);
   
2. //對R[1..N]按遞增序進行插入排序,R[0]是監視哨//
   
3. Begin
   
4. forI:=2ToNDo//依次插入R[2],...,R[n]//
   
5. begin
   
6. R[0]:=R;J:=I-1;
   
7. WhileR[0]<R[J]Do//查找R的插入位置//
   
8. begin
   
9. R[J+1]:=R[J];//將大於R的元素後移//
   
10. J:=J-1
    
11. end
    
12. R[J+1]:=R[0];//插入R//
    
13. end
    
14. End;//InsertSort//

復制代碼二、選擇排序
1.基本思想：
每一趟從待排序的數據元素中選出最小（或最大）的一個元素，順序放在已排好序的數列的最後，直到全部待排序的數據元素排完。
2.排序過程：
【示例】：
初始關鍵字[4938659776132749]
第一趟排序後13［38659776492749]
第二趟排序後1327［659776493849]
第三趟排序後132738[9776496549]
第四趟排序後13273849[49976576]
第五趟排序後1327384949[979776]
第六趟排序後132738494976[7697]
第七趟排序後13273849497676[97]
最後排序結果1327384949767697

1. ProcereSelectSort(VarR:FileType);//對R[1..N]進行直接選擇排序//
   
2. Begin
   
3. forI:=1ToN-1Do//做N-1趟選擇排序//
   
4. begin
   
5. K:=I;
   
6. ForJ:=I+1ToNDo//在當前無序區R[I..N]中選最小的元素R[K]//
   
7. begin
   
8. IfR[J]<R[K]ThenK:=J
   
9. end;
   
10. IfK<>IThen//交換R和R[K]//
    
11. beginTemp:=R;R:=R[K];R[K]:=Temp;end;
    
12. end
    
13. End;//SelectSort//

復制代碼三、冒泡排序(BubbleSort)
1.基本思想：
兩兩比較待排序數據元素的大小，發現兩個數據元素的次序相反時即進行交換，直到沒有反序的數據元素為止。
2.排序過程：
設想被排序的數組R［1..N］垂直豎立，將每個數據元素看作有重量的氣泡，根據輕氣泡不能在重氣泡之下的原則，從下往上掃描數組R，凡掃描到違反本原則的輕氣泡，就使其向上"漂浮"，如此反復進行，直至最後任何兩個氣泡都是輕者在上，重者在下為止。
【示例】：
4913131313131313
3849272727272727
6538493838383838
9765384949494949
7697654949494949
1376976565656565
2727769776767676
4949497697979797

1. ProcereBubbleSort(VarR:FileType)//從下往上掃描的起泡排序//
   
2. Begin
   
3. ForI:=1ToN-1Do//做N-1趟排序//
   
4. begin
   
5. NoSwap:=True;//置未排序的標志//
   
6. ForJ:=N-1DownTo1Do//從底部往上掃描//
   
7. begin
   
8. IfR[J+1]<R[J]Then//交換元素//
   
9. begin
   
10. Temp:=R[J+1];R[J+1:=R[J];R[J]:=Temp;
    
11. NoSwap:=False
    
12. end;
    
13. end;
    
14. IfNoSwapThenReturn//本趟排序中未發生交換，則終止演算法//
    
15. end
    
16. End;//BubbleSort//

復制代碼四、快速排序（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］
第二次交換後
［2738499776136549］
J向左掃描，位置不變，第三次交換後
［2738139776496549］
I向右掃描，位置不變，第四次交換後
［2738134976976549］
J向左掃描
［2738134976976549］
（一次劃分過程）

初始關鍵字
［4938659776132749］
一趟排序之後
［273813］49［76976549］
二趟排序之後
［13］27［38］49［4965］76［97］
三趟排序之後1327384949［65］7697
最後的排序結果1327384949657697
各趟排序之後的狀態

1. ProcereParttion(VarR:FileType;L,H:Integer;VarI:Integer);
   
2. //對無序區R[1,H]做劃分，I給以出本次劃分後已被定位的基準元素的位置//
   
3. Begin
   
4. I:=1;J:=H;X:=R;//初始化，X為基準//
   
5. Repeat
   
6. While(R[J]>=X)And(I<J)Do
   
7. begin
   
8. J:=J-1//從右向左掃描，查找第1個小於X的元素//
   
9. IfI<JThen//已找到R[J]〈X//
   
10. begin
    
11. R:=R[J];//相當於交換R和R[J]//
    
12. I:=I+1
    
13. end;
    
14. While(R<=X)And(I<J)Do
    
15. I:=I+1//從左向右掃描，查找第1個大於X的元素///
    
16. end;
    
17. IfI<JThen//已找到R>X//
    
18. begin R[J]:=R;//相當於交換R和R[J]//
    
19. J:=J-1
    
20. end
    
21. UntilI=J;
    
22. R:=X//基準X已被最終定位//
    
23. End;//Parttion//

復制代碼

1. ProcereQuickSort(VarR:FileType;S,T:Integer);//對R[S..T]快速排序//
   
2. Begin
   
3. IfS<TThen//當R[S..T]為空或只有一個元素是無需排序//
   
4. begin
   
5. Partion(R,S,T,I);//對R[S..T]做劃分//
   
6. QuickSort(R,S,I-1);//遞歸處理左區間R[S,I-1]//
   
7. QuickSort(R,I+1,T);//遞歸處理右區間R[I+1..T]//
   
8. end;
   
9. End;//QuickSort//

復制代碼五、堆排序(HeapSort)
1.基本思想：
堆排序是一樹形選擇排序，在排序過程中，將R[1..N]看成是一顆完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。
2.堆的定義:N個元素的序列K1,K2,K3,...,Kn.稱為堆，當且僅當該序列滿足特性：
Ki≤K2iKi≤K2i+1(1≤I≤[N/2])


堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉子結點的關鍵字均大於等於其孩子結點的關鍵字。例如序列10,15,56,25,30,70就是一個堆，它對應的完全二叉樹如上圖所示。這種堆中根結點（稱為堆頂）的關鍵字最小，我們把它稱為小根堆。反之，若完全二叉樹中任一非葉子結點的關鍵字均大於等於其孩子的關鍵字，則稱之為大根堆。
3.排序過程：
堆排序正是利用小根堆（或大根堆）來選取當前無序區中關鍵字小（或最大）的記錄實現排序的。我們不妨利用大根堆來排序。每一趟排序的基本操作是：將當前無序區調整為一個大根堆，選取關鍵字最大的堆頂記錄，將它和無序區中的最後一個記錄交換。這樣，正好和直接選擇排序相反，有序區是在原記錄區的尾部形成並逐步向前擴大到整個記錄區。
【示例】：對關鍵字序列42，13，91，23，24，16，05，88建堆

1. ProcereSift(VarR:FileType;I,M:Integer);
   
2. //在數組R[I..M]中調用R，使得以它為完全二叉樹構成堆。事先已知其左、右子樹(2I+1<=M時)均是堆//
   
3. Begin
   
4. X:=R;J:=2*I;//若J<=M,R[J]是R的左孩子//
   
5. WhileJ<=MDo//若當前被調整結點R有左孩子R[J]//
   
6. begin
   
7. If(J<M)AndR[J].Key<R[J+1].KeyThen
   
8. J:=J+1//令J指向關鍵字較大的右孩子//
   
9. //J指向R的左、右孩子中關鍵字較大者//
   
10. IfX.Key<R[J].KeyThen//孩子結點關鍵字較大//
    
11. begin
    
12. R:=R[J];//將R[J]換到雙親位置上//
    
13. I:=J;J:=2*I//繼續以R[J]為當前被調整結點往下層調整//
    
14. end;
    
15. Else
    
16. Exit//調整完畢，退出循環//
    
17. end
    
18. R:=X;//將最初被調整的結點放入正確位置//
    
19. End;//Sift//

復制代碼

1. ProcereHeapSort(VarR:FileType);//對R[1..N]進行堆排序//
   
2. Begin
   
3. ForI:=NDivDownto1Do//建立初始堆//
   
4. Sift(R,I,N)
   
5. ForI:=NDownto2do//進行N-1趟排序//
   
6. begin
   
7. T:=R[1];R[1]:=R;R:=T;//將當前堆頂記錄和堆中最後一個記錄交換//
   
8. Sift(R,1,I-1)//將R[1..I-1]重成堆//
   
9. end
   
10. End;//HeapSort//

復制代碼六、幾種排序演算法的比較和選擇
1.選取排序方法需要考慮的因素：
(1)待排序的元素數目n；
(2)元素本身信息量的大小；
(3)關鍵字的結構及其分布情況；
(4)語言工具的條件，輔助空間的大小等。
2.小結：
(1)若n較小(n<=50)，則可以採用直接插入排序或直接選擇排序。由於直接插入排序所需的記錄移動操作較直接選擇排序多，因而當記錄本身信息量較大時，用直接選擇排序較好。
(2)若文件的初始狀態已按關鍵字基本有序，則選用直接插入或冒泡排序為宜。
(3)若n較大，則應採用時間復雜度為O(nlog2n)的排序方法：快速排序、堆排序或歸並排序。
快速排序是目前基於比較的內部排序法中被認為是最好的方法。
(4)在基於比較排序方法中，每次比較兩個關鍵字的大小之後，僅僅出現兩種可能的轉移，因此可以用一棵二叉樹來描述比較判定過程，由此可以證明：當文件的n個關鍵字隨機分布時，任何藉助於"比較"的排序演算法，至少需要O(nlog2n)的時間。

這句話很重要它告訴我們自己寫的演算法是有改進到最優當然沒有必要一直追求最優
(5)當記錄本身信息量較大時，為避免耗費大量時間移動記錄，可以用鏈表作為存儲結構。