希爾排序
介紹
希爾排序(Shell Sort)是針對直接插入排序算法的改進,又稱縮小增量排序,因 DL.Shell 于 1959 年提出而得名。
它通過比較相距一定間隔的元素來進行,各趟比較所用的距離随着算法的進行而減小,直到隻比較相鄰元素的最後一趟排序為止。
思想
對于n個待排序的數列,取一個小于n的整數gap(gap被稱為步長)将待排序元素分成若幹個組子序列,所有距離為gap的倍數的記錄放在同一個組中;然後,對各組内的元素進行直接插入排序。 這一趟排序完成之後,每一個組的元素都是有序的。然後減小gap的值,并重複執行上述的分組和排序。重複這樣的操作,當gap=1時,整個數列就是有序的
示例
代碼
// 對希爾排序中的單個組進行排序
//a:待排序的數組,n:數組總的長度,i:組的起始位置,gap:組的步長
void group_sort(int a[], int n, int i,int gap)
{
int j;
for (j = i + gap; j < n; j += gap)
{
// 如果a[j] < a[j-gap],則尋找a[j]位置,并将後面資料的位置都後移。
if (a[j] < a[j - gap])
{
int tmp = a[j];
int k = j - gap;
while (k >= 0 && a[k] > tmp)
{
a[k + gap] = a[k];
k -= gap;
}
a[k + gap] = tmp;
}
}
}
//a:待排序的數組,n:數組的長度
void shell_sort2(int a[], int n)
{
int i,gap;
// gap為步長,每次減為原來的一半。
for (gap = n / 2; gap > 0; gap /= 2)
{
// 共gap個組,對每一組都執行直接插入排序
for (i = 0 ;i < gap; i++)
group_sort(a, n, i, gap);
}
}