標籤:程序插入排序

希爾排序(Shell Sort)是插入排序的一種。是針對直接插入排序演算法的改進。該方法又稱縮小增量排序,因DL.Shell於1959年提出而得名。

1基本思想

先取一個小於n的整數d1作為第一個增量,把文件的全部記錄分成d1個組。所有距離為d1的倍數的記錄放在同一個組中。先在各組內進行直接插入排序;然後,取第二個增量d2<d1重複上述的分組和排序,直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有記錄放在同一組中進行直接插入排序為止。
該方法實質上是一種分組插入方法。
比較相隔較遠距離(稱為增量)的數,使得數移動時能跨過多個元素,則進行一次比較就可能消除多個元素交換。D.L.shell於1959年在以他名字命名的排序演算法中實現了這一思想。演算法先將要排序的一組數按某個增量d分成若干組,每組中記錄的下標相差d.對每組中全部元素進行排序,然後再用一個較小的增量對它進行,在每組中再進行排序。當增量減到1時,整個要排序的數被分成一組,排序完成。
一般的初次取序列的一半為增量,以後每次減半,直到增量為1。
給定實例的shell排序的排序過程
假設待排序文件有10個記錄,其關鍵字分別是:
49,38,65,97,76,13,27,49,55,04。
增量序列的取值依次為:
5,2,1

2介紹

Shell排序
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[i-d].key){
R[0]=R[i];j=i-d; //R[0]只是暫存單元,不是哨兵
do {//查找R的插入位置
R[j+d]=R[j]; //后移記錄
j=j-d; //查找前一記錄
}while(j>0&&R[0].key<R[j].key);
R[j+d]=R[0]; //插入R到正確的位置上
} //endif

3演算法分析

時間性能
1.增量序列的選擇
Shell排序的執行時間依賴於增量序列。
好的增量序列的共同特徵:
① 最後一個增量必須為1;
② 應該盡量避免序列中的值(尤其是相鄰的值)互為倍數的情況。
有人通過大量的實驗,給出了較好的結果:當n較大時,比較和移動的次數約在nl.25到1.6n1.25之間。
2.Shell排序的時間性能優於直接插入排序
希爾排序的時間性能優於直接插入排序的原因:
①當文件初態基本有序時直接插入排序所需的比較和移動次數均較少。
②當n值較小時,n和n2的差別也較小,即直接插入排序的最好時間複雜度O(n)和最壞時間複雜度0(n2)差別不大。
③在希爾排序開始時增量較大,分組較多,每組的記錄數目少,故各組內直接插入較快,後來增量di逐漸縮小,分組數逐漸減少,而各組的記錄數目逐漸增多,但由於已經按di-1作為距離排過序,使文件較接近於有序狀態,所以新的一趟排序過程也較快。
因此,希爾排序在效率上較直接插人排序有較大的改進。

4穩定性

javascript
var arr = [49, 38, 65, 97, 76, 13, 27, 49, 55, 04],
len = arr.length;
for(var fraction=Math.floor(len/2); fraction>0; fraction=Math.floor(fraction/2)) {
for( var i = fraction; i<len; i++ ) {
for(var j = i-fraction; j>=0 && arr[j]>arr[fraction+j]; j-=fraction ) {
var temp = arr[j];
arr[j] = arr[fraction+j];
arr[fraction+j] = temp;
}
}
}
console.log(arr);
JAVA
public class Test {
public static int[] a = { 10, 32, 1, 9, 5, 7, 12, 0, 4, 3 };
public static void main(String args[]) {
int i; //循環計數變數
int Index = a.length;//數據索引變數
System.out.print("排序前: ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a[i]);
System.out.println("");
ShellSort(Index - 1); //選擇排序
// 排序后結果
System.out.print("排序后: ");
for (i = 0; i < Index - 1; i++)
System.out.printf("%3s ", a[i]);
System.out.println("");
}
public static void ShellSort(int Index) {
int i, j, k; // 循環計數變數
int Temp; // 暫存變數
boolean Change; // 數據是否改變
int DataLength; // 分割集合的間隔長度
int Pointer; // 進行處理的位置
DataLength = (int) Index / 2; // 初始集合間隔長度
while (DataLength != 0) // 數列仍可進行分割
{
// 對各個集合進行處理
for (j = DataLength; j < Index; j++) {
Change = false;
Temp = a[j]; // 暫存Data[j]的值,待交換值時用
Pointer = j - DataLength; // 計算進行處理的位置
// 進行集合內數值的比較與交換值
while (Temp < a[Pointer] && Pointer >= 0 && Pointer <= Index) {
a[Pointer + DataLength] = a[Pointer];
// 計算下一個欲進行處理的位置
Pointer = Pointer - DataLength;
Change = true;
if (Pointer < 0 || Pointer > Index)
break;
}
// 與最後的數值交換
a[Pointer + DataLength] = Temp;
if (Change) {
// 列印排序結果
System.out.print("排序中: ");
for (k = 0; k < Index; k++)
System.out.printf("%3s ", a[k]);
System.out.println("");
}
}
DataLength = DataLength / 2; // 計算下次分割的間隔長度
}
}
}
C實現
k=n/2;
while(k>0)
{ for(i=k;i<n;i++)
{t=a[i];
j=i-k;
while(j>=0&&t<a[j])
{
a[j+k]=a[j];
j=j-k;
}
a[j+k]=t;
}
k/=2;
}
希爾排序C的四種實現:
void shellsort(int *a,int n)
{
int k = n/2;
while(k>0)
{
for(int i = k;i< n;i++)
{
int t = a[i];
#if 0
//演算法1
int j = i - k;
while(j >= 0 && t < a[j])
{
a[j + k] = a[j];
a[j] = t;
j = j - k;
}
#endif
#if 0
//演算法2
int j;
for(j = i - k;j>=0 && t < a[j];j -= k)
a[j + k] = a[j];
a[j + k] = t;
#endif
#if 0
//演算法3
int j;
for(j = i;j >= k && t < a[j - k];j -= k)
a[j] = a[j - k];
a[j] = t;
#endif
//演算法4
int j = i;
while(j >= k && t < a[j - k])
{
a[j] = a[j-k];
j = j-k;
}
a[j] = t;
}
k /= 2;
}
}
int main()
{
int a[N]= {8,10,3,5,7,4,6,1,9,2};
shellsort(a,sizeof(a)/sizeof(a[0]));
for(int k = 0;k < N;k++)
printf("a[%d] = %d\n",k,a[k]);
return 0;
}
AS3
//需要排序的數組
var arr:Array=[7,5,8,4,0,9];
var small:int;//最小下標
var temp:int;
for (var i:int=0; i<arr.length; i++) {
small=i;
for (var j:int=i+1; j<arr.length+1; j++) {
if (arr[j]<arr[small]) {
small=j;
}
}
if (small!=i) {
temp=arr[i];
arr[i]=arr[small];
arr[small]=temp;
}
trace(arr[i]);
}
Python
def shell(arr):
l = len(arr)
h = 1
while h < l//3:
h = 3*h + 1
while h >= 1:
for i in range(h,l):
j = i
while j >= h and arr[j]<arr[j-h]:
arr[j],arr[j-h] = arr[j-h],arr[j]
j -= h
h = h//3
return arr
上一篇[遞歸調用]    下一篇 [選擇排序]

相關評論

同義詞:暫無同義詞