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

數據結構復習總結第八章排序

2013-11-15 15:39:33  來源: 數據結構 

  第八章排序

  基本概念

  文件有一組記錄組成記錄有若干數據項組成唯一標識記錄的數據項稱關鍵字;

  排序是將文件按關鍵字的遞增(減)順序排列;

  排序文件中有相同的關鍵字時若排序後相對次序保持不變的稱穩定排序否則稱不穩定排序;

  在排序過程中文件放在內存中處理不涉及數據的內外存交換的稱內部排序反之稱外部排序;

  排序算法的基本操作)比較關鍵字的大小;)改變指向記錄的指針或移動記錄本身

  評價排序方法的標准)執行時間;)所需輔助空間輔助空間為O()稱就地排序;另要注意算法的復雜程度

  若關鍵字類型沒有比較運算符可事先定義宏或函數表示比較運算

  插入排序

  直接插入排序

  實現過程

  void insertsort(seqlist R)

  {

  int i j;

  for(i=;i<=n;i++)

  if(R[i]key< R[i]key{

  R[]=R[i];j=i;

  do{R[j+]=R[j];j;}

  while(R[]key

  R[j+1]=R[0];

  }

  }

  算法中引入監視哨R[0]的作用是:1)保存R[i]的副本;2)簡化邊界條件,防止循環下標越界。TW.WiNgwit.com

  關鍵字比較次數最大為(n+2)(n-1)/2;記錄移動次數最大為(n+4)(n-1)/2;

  算法的最好時間是O(n);最壞時間是O(n^2);平均時間是O(n^2);是一種就地的穩定的排序;

  8.2.2希爾排序

  實現過程:是將直接插入排序的間隔變為d。d的取值要注意:1)最後一次必為1;2)避免d值互為倍數;

  關鍵字比較次數最大為n^1.25;記錄移動次數最大為1.6n^1.25;

  算法的平均時間是O(n^1.25);是一種就地的不穩定的排序;

  8.3交換排序

  8.3.1冒泡排序

  實現過程:從下到上相鄰兩個比較,按小在上原則掃描一次,確定最小值,重復n-1次。

  關鍵字比較次數最小為n-1、最大為n(n-1)/2;記錄移動次數最小為0,最大為3n(n-1)/2;

  算法的最好時間是O(n);最壞時間是O(n^2);平均時間是O(n^2);是一種就地的穩定的排序;

  8.3.2快速排序

  實現過程:將第一個值作為基准,設置i,j指針交替從兩頭與基准比較,有交換後,交換j,i。i=j時確定基准,並以其為界限將序列分為兩段。重復以上步驟。

  關鍵字比較次數最好為nlog2n+nC(1)、最壞為n(n-1)/2;

  算法的最好時間是O(nlog2n);最壞時間是O(n^2);平均時間是O(nlog2n);輔助空間為O(log2n);是一種不穩定排序;

  8.4選擇排序

  8.4.1直接選擇排序

  實現過程:選擇序列中最小的插入第一位,在剩余的序列中重復上一步,共重復n-1次。

  關鍵字比較次數為n(n-1)/2;記錄移動次數最小為0,最大為3(n-1);

  算法的最好時間是O(n^2);最壞時間是O(n^2);平均時間是O(n^2);是一種就地的不穩定的排序;

  8.4.2堆排序

  實現過程:把序列按層次填入完全二叉樹,調整位置使雙親大於或小於孩子,建立初始大根或小根堆,調整樹根與最後一個葉子的位置,排除該葉子重新調整位置。

  算法的最好時間是O(nlog2n);最壞時間是O(nlog2n);平均時間是O(nlog2n);是一種就地的不穩定排序;

  8.5歸並排序

  實現過程:將初始序列分為2個一組,最後單數輪空,對每一組排序後作為一個單元,對2個單元排序,直到結束。

  算法的最好時間是O(nlog2n);最壞時間是O(nlog2n);平均時間是O(nlog2n);輔助空間為O(n);是一種穩定排序;

  8.6分配排序

  8.6.1箱排序

  實現過程:按關鍵字的取值范圍確定箱子的個數,將序列按關鍵字放入箱中,輸出非空箱的關鍵字。

  在桶內分配和收集,及對各桶進行插入排序的時間為O(n),算法的期望時間是O(n),最壞時間是O(n^2)。

  8.6.2基數排序

  實現過程:按基數設置箱子,對關鍵字從低位到高位依次進行箱排序。

  算法的最好時間是O(d*n+d*rd);最壞時間是O(d*n+d*rd);平均時間是O(d*n+d*rd);輔助空間O(n+rd);是一種穩定排序;

  8.7各種內部排序方法的比較和選擇

  按平均時間復雜度分為:

  1) 平方階排序:直接插入、直接選擇、冒泡排序;

  2) 線性對數階:快速排序、堆排序、歸並排序;

  3) 指數階:希爾排序;

  4) 線性階:箱排序、基數排序。

  選擇合適排序方法的因素:1)待排序的記錄數;2)記錄的大小;3)關鍵字的結構和初始狀態;4)對穩定性的要求;5)語言工具的條件;6)存儲結構;7)時間和輔助空間復雜度。

  結論:

  1) 若規模較小可采用直接插入或直接選擇排序;

  2) 若文件初始狀態基本有序可采用直接插入、冒泡或隨機快速排序;

  3) 若規模較大可采用快速排序、堆排序或歸並排序;

  4) 任何借助於比較的排序,至少需要O(nlog2n)的時間,箱排序和基數排序只適用於有明顯結構特征的關鍵字;

  5) 有的語言沒有提供指針及遞歸,使歸並、快速、基數排序算法復雜;

  6) 記錄規模較大時為避免大量移動記錄可用鏈表作為存儲結構,如插入、歸並、基數排序,但快速、堆排序在鏈表上難以實現,可提取關鍵字建立索引表,然後對索引表排序。

  附二:

  第八章排序

  *************************************************************************************

  記錄中可用某一項來標識一個記錄,則稱為關鍵字項,該數據項的值稱為關鍵字。

  排序是使文件中的記錄按關鍵字遞增(或遞減)次序排列起來。·基本操作:比較關鍵字大小;改變指向記錄的指針或移動記錄。

  ·存儲結構:順序結構、鏈表結構、索引結構。

  經過排序後這些具有相同關鍵字的記錄之間的相對次序保持不變,則稱這種排序方法是穩定的,否則排序算法是不穩定的。

  排序過程中不涉及數據的內、外存交換則稱之為"內部排序"(內排序),反之,若存在數據的內外存交換,則稱之為外排序。

  內部排序方法可分五類:插入排序、選擇排序、交換排序、歸並排序和分配排序。

  評價排序算法好壞的標准主要有兩條:執行時間和所需的輔助空間,另外算法的復雜程序也是要考慮的一個因素。

  *************************************************************************************

  插入排序:·直接插入排序: ·逐個向前插入到合適位置。

  ·哨兵(監視哨)有兩個作用: ·作為臨變量存放R[i]

  ·是在查找循環中用來監視下標變量j是否越界。

  ·直接插入排序是就地的穩定排序。時間復雜度為O(n^2),比較次數為(n+2)(n-1)/2;移動次數為(n+4)(n-1)/2;

  ·希爾排序: ·等間隔的數據比較並按要求順序排列,最後間隔為1。

  ·希爾排序是就地的不穩定排序。時間復雜度為O(n^1.25),比較次數為(n^1.25);移動次數為(1.6n^1.25);

  交換排序:·冒泡排序:·自下向上確定最輕的一個。·自上向下確定最重的一個。·自下向上確定最輕的一個,後自上向下確定最重的一個。

  ·冒泡排序是就地的穩定排序。時間復雜度為O(n^2),比較次數為n(n-1)/2;移動次數為3n(n-1)/2;

  ·快速排序:·以第一個元素為參考基准,設定、動兩個指針,發生交換後指針交換位置,直到指針重合。重復直到排序完成。

  ·快速排序是非就地的不穩定排序。時間復雜度為O(nlog2n),比較次數為n(n-1)/2;

  選擇排序:·直接選擇排序: ·選擇最小的放在比較區前。

  ·直接選擇排序就地的不穩定排序。時間復雜度為O(n^2)。比較次數為n(n-1)/2;

  ·堆排序 ·建堆:按層次將數據填入完全二叉樹,從int(n/2)處向前逐個調整位置。

  ·然後將樹根與最後一個葉子交換值並斷開與樹的連接並重建堆,直到全斷開。

  ·堆排序是就地不穩定的排序,時間復雜度為O(nlog2n),不適宜於記錄數較少的文件。。

  歸並排序: ·先兩個一組排序,形成(n+1)/2組,再將兩組並一組,直到剩下一組為止。

  ·歸並排序是非就地穩定排序,時間復雜度是O(nlog2n),

  分配排序:·箱排序: ·按關鍵字的取值范圍確定箱子數,按關鍵字投入箱子,鏈接所有非空箱。

  ·箱排序的平均時間復雜度是線性的O(n).

  ·基數排序:·從低位到高位依次對關鍵字進行箱排序。

  ·基數排序是非就穩定的排序,時間復雜度是O(d*n+d*rd)。

  各種排序方法的比較和選擇: ·.待排序的記錄數目n;n較大的要用時間復雜度為O(nlog2n)的排序方法;

  ·記錄的大小(規模);記錄大最好用鏈表作為存儲結構,而快速排序和堆排序在鏈表上難於實現;

  ·關鍵字的結構及其初始狀態;

  ·對穩定性的要求;

  ·語言工具的條件;

  ·存儲結構;

  ·時間和輔助空間復雜度。


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