简单排序3-插入排序

Insertion sort

image

类似扑克牌的思路。

应用于基本有序的情况

从第一个元素开始，前半部都是有序的,后半部是无序的

1. 把最新的一个数据插入到一个有序的排列里面
   有序的排列n,从最后一个开始，向前交换，类似冒泡算法

        for(j=n; j>0; j--)
        {
            if(array[j] < array[j-1])
                swap(array, j , j-1);
            else
                break;
        }

2. 从第一个循环到最后一个无序的数据

    for(i=1;i<arraysize;i++)
    {
        for(j=i; j>0; j--)
        {
            if(array[j] < array[j-1])
                swap(array, j , j-1);
            else
                break;
        }

优化

不用交换，用变量保存要插入的值。

    for(i=1;i<arraysize;i++)
    {
       temp = array[i];
        for(j=i; j>0; j--)
        {
 
            if(temp < array[j-1])
                array[j] = array[j-1];
            else
            {
                break;
            }    
        }
        array[j] = temp;
    }

时间复杂度 O(n2),

最好情况O(n)