数据结构_排序①插入排序

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

插入排序:

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完 。
时间复杂度: O(N^2)
空间复杂度: O(1)
稳定性: 稳定
适合场景: 接近有序的序列, 时间复杂度趋近于O(N)对于有序的序列, 时间复杂度O(N)

void InsertSort(int* a , int n){
    assert(a);
    int i;
    for(i = 0;i < n-1 ;++i){
        //单个元素的排序
        //找到已经排好序的最好有一个元素的位置
        int end = i;
        //把end + 1 位置的元素插入到合适的位置
        int tmp = a[end + 1];
        while(end >= 0 && a[end] > tmp){
            a[end + 1 ] = a[end];
            --end;
        }
        //找到合适的位置
        a[end + 1] = tmp;
    }
}

L_KingMing

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

文章评论(0)