排序

插入排序

nkul · 7月8日 · 2020年 · 214次已读

排序过程

从第二个元素开始排序。当排序到第i个时,前i-1个为有序的!

对于第i个元素,处理方法为:依次和前面的对比,如果前面的较大则往后移动一位!

基本的排序算法

void insert_sort_base(int nums[],int n){
    for(int i=1;inums[i]){
            //临时变量存储当前值
            int tmp = nums[i];
            int j = i-1;
            //从i-1开始遍历,停止条件为遍历到0,或者遍历位置元素小于或者等于tmp
            for(;j>=0 && nums[j]>tmp;j--){
                nums[j+1] = nums[j];
            }
            //注意此时j所在的元素是小于或者等于tmp的,因此真正替换的为j+1的位置
            nums[j+1] = tmp;
        }
    }
}

改进的插入排序

对第i个元素进行排序时,因为前i-1个元素已经有序。对于在有序数组中插入一个tmp可以使用二分法。

void insert_sort_half(int nums[],int n){
    int mid,i,j,low,high;
    for(i=1;itmp) high = mid-1;
            //else语句这,其中一个条件是nums[mid]=tmp,但是为了保证稳定性,要找的位置在mid的右边
            else low = mid+1;
        }
        //通过二分法退出条件可得low=high-1;
        //第low个元素是大于tmp的(可以假设恰好等于tmp,此时的操作是low = mid+1,故第low个元素大于tmp)
        for(j = i-1;j>=low;j--){
            nums[j+1] = nums[j];
        }
        nums[low] = tmp;
    }
}

希尔排序

希尔排序是基于插入排序引入的,希尔排序是让局部有序,然后整体插入排序!

给定数组[49,38,65,97,76,13,27,49,55,04]

1、选定一个跨度d,初始为长度一半,即d=5
2、每隔五个数作为一组,则原数组分为[49,13][38,27][65,49][97,55][76,04]
3、子数组内部排序
4、取d=d/2,重复上述操作,知道d=1,退化到插入排序

逐渐让小数组有序,进而扩大数组跨度使之慢慢的有序!

void insert_sort_shell(int nums[],int n){
    int d,i,j;
    for(d=n/2;d>=1;d=d/2){
        //基本的插入排序是从下标为1个开始的(0是第一个),因此希尔排序,是从0+d开始
        for(i=d;i=0 && nums[j]>tmp;j-=d){
                    nums[j+d] = nums[j];
                }
                nums[j+d] = tmp;
            }
        }
    }
}

插入排序性质分析

  • 内部排序
  • 除了希尔排序(希尔排序是不稳定的),插入排序都是稳定的
  • 时间复杂度:
    • 最好:数组本身顺序,o(n)
    • 最坏:数组本身逆序,o(n^2)
  • 空间复杂度:o(1)
  • 除了希尔排序,插入排序同样适用于链表结构


0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!