希尔排序

概述

希尔排序是插入排序的改良版，适合于基本有序的排序表和数据量不大的排序表，时间复杂度在O(n^1.3^)和O(n^2^)之间。

实现步骤

1.由列表长度算出步长dk
dk=n/2=2
2.将i指针指向dk+1=3处，将数据备份到0号位
3.指针j指向i-dk=1处，比较j位数据和0位数据大小，如果A[j]>A[0]，A[j]右移一位
4.在j>0前提下，以dk步长向前移动j指针，并重复步骤3
5.循环结束后，j+dk处空出，将0号位数据放入

代码(C语言)

    #include "pch.h"  
    #include <iostream>  

    using namespace std;  

    void shell_sort(int A[],int n) {  
        int dk,i,j;  
        for (dk = n / 2; dk >= 1; dk /= 2) {  
            for (i = dk + 1; i <= n; i++) {  
                A[0] = A[i];  
                for (j = i - dk; j > 0  && A[j] > A[0]; j-=dk) {  
                    A[j + dk] = A[j];  
                }  
                A[j+dk] = A[0];  
            }  
        }  



    }  

    int main()  
    {  
        int A[] = { 999,3,2,1,4 };//定义数组A，0号位999占位  
        shell_sort(A,4);//对数组A排序  

        //循环输出A数组  
        int i;  
        for ( i = 1; i < 5; i++) {  
            cout << A[i] << endl;  
        }  

        system("pause");  
    }