插入排序

  基本思想:和交换排序不同的是它不用进行交换操作,而是用一个临时变量存储当前值 。当前面的元素比后面大时,先把后面的元素存入临时变量,前面元素的值放到后面元素位置,再到最 后把其值插入到合适的数组位置。 

动图演示

插入排序

C代码

#include<stdio.h>
void InsertSort(int  *a, int n) {
    int tmp = 0;
    for (int i = 1; i < n; i++) {
        int j = i - 1;
        if (a[i] < a[j]) {
            tmp = a[i];
            a[i] = a[j];
            while (tmp < a[j-1]) {
                a[j] = a[j-1];
                j--;
                if(j==0) break;
            }
            a[j] = tmp;
        }
    }
}
int main() {
    int a[] = { 11,7,9,22,10,18,4,43,5,1,32};
    int n = sizeof(a)/sizeof(int);
    InsertSort(a, n);
    printf("排序好的数组为:");
    for (int i = 0; i < n; i++) {
        printf(" %d", a[i]);
    }
    printf("\n");
    return 0;
}    

分析:

  最坏时间复杂度为数组为逆序时,为O(n^2)。最优时间复杂度为数组正序时,为O(n)。 平均时间复杂度为O(n^2)。辅助空间O(1)。稳定性:稳定。

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

results matching ""

    No results matching ""