方法
好的排序方法可以有效提高排序速度,提高排序效果。
在計算機領域主要使用數據排序方法根據占用記憶體的方式不同分為2大類:內部排序方法與外部排序方法。
內部排序方法
若整個排序過程不需要訪問外存便能完成,則稱此類排序問題為內部排序。
內排序的方法有許多種,按所用策略不同,可歸納為五類:插入排序、選擇排序、交換排序、歸併排序和基數排序。
其中,插入排序主要包括直接插入排序和希爾排序兩種;選擇排序主要包括直接選擇排序和堆排序;交換排序主要包括氣(冒)泡排序和快速排序。
外部排序方法
外部排序基本上由兩個相互獨立的階段組成。首先,按可用記憶體大小,將外存上含n個記錄的檔案分成若干長度為k的子檔案或段(segment),依次讀入記憶體並利用有效的內部排序方法對它們進行排序,並將排序後得到的有序子檔案重新寫入外存。通常稱這些有序子檔案為歸併段或順串;然後,對這些歸併段進行逐趟歸併,使歸併段(有序子檔案)逐漸由小到大,直至得到整個有序檔案為止。