熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

排序之基本概念

2013-11-15 15:46:18  來源: 數據結構 

 基本概念

  關鍵字項及關鍵字(Key)記錄由若干個數據項(或域)組成其中有一項可用來標識一個記錄稱為關鍵字項該數據項的值稱為關鍵字
 
  排序(Sorting)又稱分類假設含 n 個記錄的序列為{RRRn}其相應的關鍵字序列為{KKKn} 需確定n的一種排列pppn使其相應的關鍵字滿足如下的非遞減(或非遞增)關系 Kp≤Kp≤…≤Kpn 即使初始的的序列成為一個按關鍵字有序的序列{RpRpRpn}這樣一種操作稱為排序
 
  如果待排序的文件中存在有多個關鍵字相同的記錄經過排序後這些具有相同關鍵字的記錄之間的相對次序保持不變則稱這些排序方法是穩定的反之則稱這種排序方法是不穩定的
   排序算法的穩定性是針對所有輸入實例而言的即在所有可能的輸入實例中只要有一個實例使得算法不滿足穩定性要求則該排序算法就是不穩定的
 
  排序方法

①內部排序
  內部排序(Internal Sorting)在排序過程中若整個文件都是放在內存中處理排序時不涉及數據的內外存交換則稱之為內排序
  按所用的策略不同內部排序方法可以分為五類插入排序選擇排序交換排序歸並排序分配排序
②外部排序
  外部排序(External Sorting)若排序過程中要進行數據的內外存交換則稱之為外部排序

排序過程的基本操作

①比較兩個關鍵字的大小
②改變指向記錄的指針或移動記錄本身

  評價排序算法好壞的標准執行時間和所需的輔助空間另外算法本身的復雜程度也是要考慮的一個因素
 
  就地排序(InPlace Sort)若排序算法所需的輔助空間並不依賴於總是的規模n也就是說輔助空間是O()則稱之為就地排序

  順序表類型說明


幾種基本的排序方法


From:http://tw.wingwit.com/Article/program/sjjg/201311/23933.html
    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.