内排序（四）——謝爾(Shell)排序

核心思想

謝爾(Shell)排序，也叫縮小增量排序法，其核心思想如下：

首先确定一個元素的間隔數gap。

将參加排序的元素按照gap分隔成若幹個子序列( 即分别把那些位置相隔為gap的元素看作一個子序列)，然後對各個子序列采用某一種排序方法進行排序；此後減小gap值，重複上述過程，直到gap<1。

常用的一種減小gap的方法如下：

基于上述減小gap的方法，謝爾排序法的完整過程圖解如下：

gap為4時，初始資料分為4個序列，49、76、35；97、65；38、13；50、27；分别對這個4個序列内進行排序得到第一趟排序，然後gap除以2，得到新的序列…

希爾排序，是插入排序的一種更高效的改進版本。希爾排序是非穩定排序算法。

希爾排序是基于插入排序的以下兩點性質而提出改進方法的：

1、插入排序在對幾乎已經排好序的資料操作時，效率高，即可以達到線性排序的效率

2、但插入排序一般來說是低效的，因為插入排序每次隻能将資料移動一位

算法實作

謝爾排序的C語言實作如下，其中子序列内采用冒泡排序方法：

#include <stdio.h>
//列印數組
void print_arr(int arr[],int len)
{
    int i;
    for(i=0;i<len;i++)
    {
        printf("%5d",arr[i]);
    }
    printf("\n");
}
/**
**gap初始值為len/2,一趟排序之後gap=gap/2;
**/
void shell_sort(int arr[],int len)
{
    int i, j, flag, gap=len,trip=1;
    int temp;
    while(gap>1){
        gap=gap/2;
        printf("the %d trip:\n",trip);
        do{
            flag=0;
            for(i=0;i<len-gap;i++){
                j=i+gap;
                if(arr[i]>arr[j]){
                    temp=arr[i];
                    arr[i]=arr[j];
                    arr[j]=temp;
                    flag=1;
                }
            }
        }while(flag!=0);
        print_arr(arr,len);
        trip=trip+1;
    }
}

int main() {
    int arr[] = { 49,97,38,50,76,65,13,27,25};
    int len = (int) sizeof(arr) / sizeof(*arr);
    shell_sort(arr, len);
    printf("\n\n\nthe result is:\n");
    print_arr(arr,len);
    return 0;
}      

程式運作結果如下：

算法分析