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

排序 - 插入排序 - 希爾排序

2013-11-15 15:41:38  來源: 數據結構 

  希爾排序(Shell Sort)是插入排序的一種因DLShell於年提出而得名

  希爾排序基本思想

  基本思想

  先取一個小於n的整數d 作為第一個增量把文件的全部記錄分成d 個組所有距離為d l 的倍數的記錄放在同一個組中

  先在各組內進行直接插人排序;然後取第二個增量d

  2

  該方法實質上是一種分組插入方法。

  給定實例的shell排序的排序過程

  假設待排序文件有10個記錄,其關鍵字分別是:

  49,38,65,97,76,13,27,49,55,04。

  增量序列的取值依次為:

  5,3,1

  排序過程如【 動畫模擬演示 】。

  Shell排序的算法實現

  1. 不設監視哨的算法描述

  void ShellPass(SeqList R,int d)

  {//希爾排序中的一趟排序,d為當前增量

  for(i=d+1;i<=n;i++) //將R[d+1..n]分別插入各組當前的有序區

  if(R[i].key

  R[0]=R[i];j=i-d; //R[0]只是暫存單元,不是哨兵

  do {//查找R[i]的插入位置

  R[j+d];=R[j]; //後移記錄

  j=j-d; //查找前一記錄

  }while(j>0&&R[0].key

  R[j+d]=R[0]; //插入R[i]到正確的位置上

  } //endif

  } //ShellPass

  void ShellSort(SeqList R)

  {

  int increment=n; //增量初值,不妨設n>0

  do {

  increment=increment/3+1; //求下一增量

  ShellPass(R,increment); //一趟增量為increment的Shell插入排序

  }while(increment>1)

  } //ShellSort

  注意:

  當增量d=1時,ShellPass和InsertSort基本一致,只是由於沒有哨兵而在內循環中增加了一個循環判定條件"j>0",以防下標越

  界。

  2.設監視哨的shell排序算法

  具體算法【參考書目[12] 】

  算法分析

  1.增量序列的選擇

  Shell排序的執行時間依賴於增量序列。

  好的增量序列的共同特征:

  ① 最後一個增量必須為1;

  ② 應該盡量避免序列中的值(尤其是相鄰的值)互為倍數的情況。

  有人通過大量的實驗,給出了目前較好的結果:當n較大時,比較和移動的次數約在n l.25 到1.6n 1.25 之間。

  2.Shell排序的時間性能優於直接插入排序

  希爾排序的時間性能優於直接插入排序的原因:

  ①當文件初態基本有序時直接插入排序所需的比較和移動次數均較少。

  ②當n值較小時,n和n 2 的差別也較小,即直接插入排序的最好時間復雜度O(n)和最壞時間復雜度0(n 2 )差別不大。

  ③在希爾排序開始時增量較大,分組較多,每組的記錄數目少,故各組內直接插入較快,後來增量d i 逐漸縮小,分組數逐漸

  減少,而各組的記錄數目逐漸增多,但由於已經按d i-1 作為距離排過序,使文件較接近於有序狀態,所以新的一趟排序過程也較快

  因此,希爾排序在效率上較直接插人排序有較大的改進。

  3.穩定性

  希爾排序是不穩定的。參見上述實例,該例中兩個相同關鍵字49在排序前後的相對次序發生了變化。


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