【排序算法】表排序算法原理

表排序

• • • 條件
    • 間接排序
    • • 算法思路
    • 實體排序
    • • 算法思路

條件

表排序的待排元素不是基本資料類型而是結構體或資料塊

間接排序

間接排序是指在排序時并不能移動資料本身而是移動指向資料的指針（該指針不一定就是指針變量，可以是能定位到元素的任何資訊，比如數組下标的序号）

算法思路

對于待排序列’A’，A中每個元素是關鍵字（對應結構體或資料塊的特征資訊）

定義一個指針（待排序列的序号）數組作作為’表’（初始時table[i]=i）

1. 待排元素A代表的的是結構體或資料塊，因為這些結構體或資料塊相對來說較為龐大，是以排序時間接的使用表（代表待排序列位置的指針數組）代替待排序列元素進行排序，而原有待排序列不需要發生改變（即排序發生互動時交換的時表中的指針）
2. 實際上就是使用表(代表待排序列位置的指針數組)來替待排序列的索引（下标），通過表中的指針來通路對應的A中元素，對表進行排序就相當于對待排序列進行排序（表中元素值代表A中對應索引元素應該所處改位置）

排序時（設使用插入排序），将兩個元素進行比較（A[1]與A[0]）比較，将A[1]與A[0]對應的表元素進行位置互換（排序）

• 此時A[0]位置上的表元素從0變為1，代表A[0]位置上的元素實際上放A[1]位置上的元素（1該位置應放置A[1]元素）

不斷排序後，就可以得到表中指針已經按照關鍵字排序完成的數組，待排序列通過該表元素進行通路即是排序後的序列

• 如果僅要求按順序輸出，則輸出：A[ table[0] ], A[ table[1] ], ……, A[ table[N-1] ]

實體排序

間接排序後，得到的并不是真正待排序列A的排序，而是使用表來替代A的索引用以通路，若想要将待排序列A真正排序可以再使用實體排序

算法思路

N個數字的排列由若幹個獨立的環組成

1. 間接排序後表中的序列是已經排列好的，該序列中的元素是由若幹個環組成的，即從待排序列A中指定位置開始，依次通路對應表中的位置，知道再次回到該起點位置

   

2. 然後從下一個不在環中的位置開始再次找到一個環，直到所有的元素都在環中為止

   

由于排列由若幹個獨立的環組成，是以可以将每個環的排列單獨處理，将環起始位置的元素放置到一個臨時位置Temp中，這樣該位置就會空餘出來，就可以将該位置應放元素（該位置表元素值對應A中元素）放置到改位置上，之後依次将位置替換直到環結束（每通路一個空位i後，就令table[i]=i。當發現table[i]==i時，環就結束了。）将臨時空間将該空餘位置填滿就完成了這個環的排序

• 即用temp記錄初值 ，每次換位置時修改table值，用if ( table[i] == i )判斷一個環的結束