插入排序—希尔排序

96 阅读 0 评论 64 点赞

我是靠谱客的博主仁爱毛豆，这篇文章主要介绍插入排序—希尔排序，现在分享给大家，希望可以做个参考。

排序思路

希尔排序是一种分组插入排序。先取定一个小于n的整数d1作为第一个增量，把表全部元素分成d1个组，所有相互之间距离为d1的倍数的元素放在一个组内。在各组之间进行插入排序；然后再取第二个增量d2(d2<d1)重复分组和排序的过程，直至所取的增量dt=1(dt<d(t-1)<……<d2<d1)。

举例：对于数组int a[10]={9,8,7,6,5,4,3,2,1,0};

d1=10/2=5

{9,4},{8,3},{7,2},{6,1},{5,0}

代码实现

取d1=n/2, $d_{i+1}=left lfloor d_{i}/2 right rfloor$

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>

using namespace std;

void shellSort(int a[],int n)
{
    int gap,tmp,j,i;//gap代变每次取的增量
    gap=n/2;
    while(gap>0)//gap最小为1
    {
        //就是直接插入方法，只是这里gap作为间距
        for(i=gap; i<n; i++)
        {
            tmp=a[i];
            j=i-gap;
            while(j>=0&&tmp<a[j]){
                a[j+gap]=a[j];
                j=j-gap;
            }
            a[j+gap]=tmp;

        }
        gap=gap/2;
    }


}

int main()
{
    int a[]={9,8,7,6,5,4,3,2,1,0};
    shellSort(a,10);
    for(int i=0;i<10;i++){
        cout << a[i]<<",";

    }
    cout<< endl;
    return 0;
}