希尔排序

  基本思想为在直接插入排序的思想下设置一个最小增量dk,刚开始dk设置为n/2。进行插入排序,随后再让dk=dk/2,再进行 插入排序,直到dk为1时完成最后一次插入排序,此时数组完成排序。

动图演示

希尔排序

C代码

#include<stdio.h>
//    进行插入排序
//    初始时从dk开始增长,每次比较步长为dk
void Insrtsort(int *a, int n,int dk) {
    for (int i = dk; i < n; ++i) {
        int j = i - dk;
        if (a[i] < a[j]) {    //    比较前后数字大小
            int tmp = a[i];        //    作为临时存储    
            a[i] = a[j];
            while (a[j] > tmp) {    //    寻找tmp的插入位置
                a[j+dk] = a[j];
                j -= dk;
            }
            a[j+dk] = tmp;        //    插入tmp
        }
    }
}

void ShellSort(int *a, int n) {
    int dk = n / 2;        //    设置初始dk
    while (dk >= 1) {
        Insrtsort(a, n, dk);
        dk /= 2;
    }
}

int main() {
    int a[] = { 5,12,35,42,11,2,9,41,26,18,4 };
    int n = sizeof(a) / sizeof(int);
    ShellSort(a, n);
    printf("排序好的数组为:");
    for (int j = 0; j < n; j++) {
        printf("%d ", a [j]);
    }
    return 0;
}

分析:

  最坏时间复杂度为O(n^2);最优时间复杂度为O(n);平均时间复杂度为O(n^1.3)。辅助空间O(1)。稳定性:不稳定。希尔 排序的时间复杂度与选取的增量有关,选取合适的增量可减少时间复杂度。

Copyright © liyang.com 2019 all right reserved,powered by Gitbook该文件修订时间: 2019-07-01 15:22:50

results matching ""

    No results matching ""