数据结构_排序②希尔排序

2019-08-15 0 条评论 86 次阅读 1 人点赞

希尔排序

先选定一个整数,把待排序文件中所有元素分成多个组,所有距离为gap的元素及两者间的元素分在同一组内,并对每一组内的元素进行排序。然后,取,重复上述分组和排序的工作。当到达=1时,所有元素在统一组内排好序
//时间复杂度: O(N^1.3 ~ N^2)
//空间复杂度: O(1);
稳定性: 不稳定

void Shell(int* a , int n){
    int gap = n;
    int i;
//    for(; gap >= 1; gap -= num){//预排序的次数
//        for (num = 0; num < gap ; ++num) {//待排序的组别
    while(gap >1){
        //gap > 1 -->预排序过程
        //gap = 1 -->排序过程
        gap = gap / 3 + 1;// + 1保证最后一次gap为1的插入排序
        for(i = 0 ; i < n - gap ; i ++){
            int end = i;
            int tmp = a[end + gap];
            while(end >= 0 && a[end] > tmp){
                a[end + gap] = a[end];
                end -= gap;
            }
            a[end + gap] = tmp;
        }
    }
}

L_KingMing

这个人太懒什么东西都没留下

文章评论(0)