插入排序

综述

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法.
它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入.

算法描述

一般来说,插入排序都采用in-place在数组上实现.具体算法描述如下:
1.从第一个元素开始,该元素可以认为已经被排序;
2.取出下一个元素,在已经排序的元素序列中从后向前扫描;
3.如果该元素(已排序)大于新元素,将该元素移到下一位置;
4.重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
5.将新元素插入到该位置后;
6.重复步骤2~5.

示意图

插入排序动态图 插入排序静态图

性质

排序类别:交换排序
是否是稳定排序:稳定
是否是原地排序:是
时间复杂度:最好为O(N), 最坏为O(N^2), 所以时间复杂度为O(N^2)
空间复杂度:O(1)

解释

直接插入排序(Straight Insertion Sort)的基本思想是:
把n个待排序的元素看成为一个有序表和一个无序表.
开始时有序表中只包含1个元素,无序表中包含有n-1个元素,排序过程中每次从无序表中取出第一个元素,将它插入到有序表中的适当位置,使之成为新的有序表,重复n-1次可完成排序过程.

直接插入排序对于数据规模较小或者基本有序的数据效率很高。
数据有序程序越高，直接插入排序越高效。

优化

优化方式一

二分插入排序
二分法插入排序,简称二分排序,是在插入第i个元素时,对前面的0～i-1元素进行折半,先跟他们中间的那个元素比,如果小,则对前半再进行折半,否则对后半进行折半,直到left<right,然后再把第i个元素前1位与目标位置之间的所有元素后移,再把第i个元素放在目标位置上.

算法思想简单描述:二分法没有排序,只有查找.所以当找到要插入的位置时.移动必须从最后一个记录开始,向后移动一位,再移动倒数第2位,直到要插入的位置的记录移后一位.

二分插入排序是稳定的与二分查找的复杂度相同:平均时间O(n^2)
最好的情况是当插入的位置刚好是二分位置 所用时间为O(log₂n);
最坏的情况是当插入的位置不在二分位置 所需比较次数为O(n),无限逼近线性查找的复杂度.
S<=∑n「log₂n「-2^n「log₂n「+1
k= 1
平均时间O(n^2)

优化方式二

不用先查找，而是在内存循环直接将满足条件的元素后移（这里的移动可以用交换），最后将元素插入合适的位置；

优化方式三

对数组进行简单预处理，循环数组将nums[i]>nums[i+1]的两个元素进行交换，如果未进行交换是有序的，然后在进行插入排序

Python实现及其优化

def insert_sort1(dest_list=[]):
    if len(dest_list) < 2:
        return dest_list
    count = 0
    for i in range(1, len(dest_list)):
        print('第{}次排序为:'.format(str(i)), dest_list)
        for j in range(i, 0, -1):
            print('----', dest_list)
            if dest_list[j] < dest_list[j - 1]:
                dest_list[j], dest_list[j - 1] = dest_list[j - 1], dest_list[j]
                count += 1
    print('最后进行交换的次数是:{}'.format(str(count)))
    return dest_list

dest = [5, 3, 4, 6, 2, 1, 7]
result = insert_sort1(dest)
print('最后的结果是:', result)

'''
第1次排序为: [5, 3, 4, 6, 2, 1, 7]
---- [5, 3, 4, 6, 2, 1, 7]
第2次排序为: [3, 5, 4, 6, 2, 1, 7]
---- [3, 5, 4, 6, 2, 1, 7]
---- [3, 4, 5, 6, 2, 1, 7]
第3次排序为: [3, 4, 5, 6, 2, 1, 7]
---- [3, 4, 5, 6, 2, 1, 7]
---- [3, 4, 5, 6, 2, 1, 7]
---- [3, 4, 5, 6, 2, 1, 7]
第4次排序为: [3, 4, 5, 6, 2, 1, 7]
---- [3, 4, 5, 6, 2, 1, 7]
---- [3, 4, 5, 2, 6, 1, 7]
---- [3, 4, 2, 5, 6, 1, 7]
---- [3, 2, 4, 5, 6, 1, 7]
第5次排序为: [2, 3, 4, 5, 6, 1, 7]
---- [2, 3, 4, 5, 6, 1, 7]
---- [2, 3, 4, 5, 1, 6, 7]
---- [2, 3, 4, 1, 5, 6, 7]
---- [2, 3, 1, 4, 5, 6, 7]
---- [2, 1, 3, 4, 5, 6, 7]
第6次排序为: [1, 2, 3, 4, 5, 6, 7]
---- [1, 2, 3, 4, 5, 6, 7]
---- [1, 2, 3, 4, 5, 6, 7]
---- [1, 2, 3, 4, 5, 6, 7]
---- [1, 2, 3, 4, 5, 6, 7]
---- [1, 2, 3, 4, 5, 6, 7]
---- [1, 2, 3, 4, 5, 6, 7]
最后的结果是: [1, 2, 3, 4, 5, 6, 7]
'''


"""
优化方式一
为减少查找时间：使用二分查找元素插入位置；

二分法插入排序，简称二分排序，是在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left<right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。

二分法插入排序，简称二分排序，是在插入第i个元素时，对前面的0～i-1元素进行折半，先跟他们中间的那个元素比，如果小，则对前半再进行折半，否则对后半进行折半，直到left<right，然后再把第i个元素前1位与目标位置之间的所有元素后移，再把第i个元素放在目标位置上。

算法思想简单描述：
二分法没有排序，只有查找。所以当找到要插入的位置时。移动必须从最后一个记录开始，向后移动一位，再移动倒数第2位，直到要插入的位置的记录移后一位。

二分插入排序是稳定的与二分查找的复杂度相同
最好的情况是当插入的位置刚好是二分位置 所用时间为O(log₂n);
最坏的情况是当插入的位置不在二分位置 所需比较次数为O(n)，无限逼近线性查找的复杂度。
S<=∑n「log₂n「-2^n「log₂n「+1
k= 1
平均时间O(n^2)
"""
def insert_sort2(arr):
    if len(arr) < 2:
        return arr
    
    count = 0
    for i in range(1, len(arr)):
        tem = arr[i]

        # 二分法进行插入位置的查找
        left = 0
        right = i - 1
        # 待插入的值与已排序区域的中间值比较，不断缩小区域范围，直到left和right相遇。
        while left <= right:
            mid = (left + right) // 2
            if arr[i] < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1

        # 当left和right相遇的时候，待插入的位置其实就是left的位置，此时要将left到有序序列的最后一个元素都向后移动一个位置，才能插入元素。
        # 这里一定要用left-1,否则当left的位置就是有序序列的最后一个位置时，j取不到值，后面的元素会被这个位置的元素值覆盖。
        for j in range(i - 1, left - 1, -1):
            arr[j + 1] = arr[j]

        # 插入元素
        if left != i:
            arr[left] = tem
            count += 1
        print('第{}次排序为:'.format(str(i)), arr)
    print('共循环%i次' % count)
    return arr

dest = [5, 3, 4, 6, 2, 1, 8, 7]
result = insert_sort2(dest)
print('最后的结果是:', result)

'''
第1次排序为: [3, 5, 4, 6, 2, 1, 8, 7]
第2次排序为: [3, 4, 5, 6, 2, 1, 8, 7]
第3次排序为: [3, 4, 5, 6, 2, 1, 8, 7]
第4次排序为: [2, 3, 4, 5, 6, 1, 8, 7]
第5次排序为: [1, 2, 3, 4, 5, 6, 8, 7]
第6次排序为: [1, 2, 3, 4, 5, 6, 8, 7]
第7次排序为: [1, 2, 3, 4, 5, 6, 7, 8]
共循环5次
最后的结果是: [1, 2, 3, 4, 5, 6, 7, 8]
'''

"""
优化方式二
不用先查找，而是在内存循环直接将满足条件的元素后移（这里的移动可以用交换），最后将元素插入合适的位置；
"""


def insert_sort3(dest_list=[]):
    if len(dest_list) < 2:
        return dest_list

    length = len(dest_list)
    for i in range(length):
        temp = dest_list[i]
        pos = i
        for j in range(i, 0, -1):
            if temp < dest_list[j - 1]:
                dest_list[j] = dest_list[j - 1]
                pos = j
            else:
                break
        dest_list[pos] = temp
        print('第{}次排序结果是:'.format(str(i+1)), dest_list)
    return dest_list

'''
第1次排序结果是: [1, 2, 3, 4, 5, 6, 7]
第2次排序结果是: [1, 2, 3, 4, 5, 6, 7]
第3次排序结果是: [1, 2, 3, 4, 5, 6, 7]
第4次排序结果是: [1, 2, 3, 4, 5, 6, 7]
第5次排序结果是: [1, 2, 3, 4, 5, 6, 7]
第6次排序结果是: [1, 2, 3, 4, 5, 6, 7]
第7次排序结果是: [1, 2, 3, 4, 5, 6, 7]
最后的结果是: [1, 2, 3, 4, 5, 6, 7]
**************************************************
第1次排序结果是: [1, 2, 3, 4, 5, 6, 7, 8]
第2次排序结果是: [1, 2, 3, 4, 5, 6, 7, 8]
第3次排序结果是: [1, 2, 3, 4, 5, 6, 7, 8]
第4次排序结果是: [1, 2, 3, 4, 5, 6, 7, 8]
第5次排序结果是: [1, 2, 3, 4, 5, 6, 7, 8]
第6次排序结果是: [1, 2, 3, 4, 5, 6, 7, 8]
第7次排序结果是: [1, 2, 3, 4, 5, 6, 7, 8]
第8次排序结果是: [1, 2, 3, 4, 5, 6, 7, 8]
最后的结果是: [1, 2, 3, 4, 5, 6, 7, 8]
**************************************************
第1次排序结果是: [7, 6, 5, 4, 3, 2, 1]
第2次排序结果是: [7, 6, 5, 4, 3, 2, 1]
第3次排序结果是: [7, 5, 6, 4, 3, 2, 1]
第4次排序结果是: [7, 4, 5, 6, 3, 2, 1]
第5次排序结果是: [7, 3, 4, 5, 6, 2, 1]
第6次排序结果是: [7, 2, 3, 4, 5, 6, 1]
第7次排序结果是: [7, 1, 2, 3, 4, 5, 6]
最后的结果是: [7, 1, 2, 3, 4, 5, 6]
**************************************************
第1次排序结果是: [8, 7, 6, 5, 4, 3, 2, 1]
第2次排序结果是: [8, 7, 6, 5, 4, 3, 2, 1]
第3次排序结果是: [8, 6, 7, 5, 4, 3, 2, 1]
第4次排序结果是: [8, 5, 6, 7, 4, 3, 2, 1]
第5次排序结果是: [8, 4, 5, 6, 7, 3, 2, 1]
第6次排序结果是: [8, 3, 4, 5, 6, 7, 2, 1]
第7次排序结果是: [8, 2, 3, 4, 5, 6, 7, 1]
第8次排序结果是: [8, 1, 2, 3, 4, 5, 6, 7]
最后的结果是: [8, 1, 2, 3, 4, 5, 6, 7]
**************************************************
'''


"""
优化方式三
对数组进行简单预处理，循环数组将nums[i]>nums[i+1]的两个元素进行交换，如果未进行交换是有序的，然后在进行插入排序
"""


def insert_sort4(dest_list=[]):
    if len(dest_list) < 2:
        return dest_list

    length = len(dest_list)
    for i in range(length):
        for j in range(i, 0, -1):
            if dest_list[j] < dest_list[j - 1]:
                dest_list[j], dest_list[j - 1] = dest_list[j - 1], dest_list[j]
        print('第{}次排序结果是:'.format(str(i+1)), dest_list)
    return dest_list

dest = [5, 3, 4, 6, 2, 1, 8, 7]
result = insert_sort4(dest)
print('最后的结果是:', result)
'''
第1次排序结果是: [5, 3, 4, 6, 2, 1, 8, 7]
第2次排序结果是: [3, 5, 4, 6, 2, 1, 8, 7]
第3次排序结果是: [3, 4, 5, 6, 2, 1, 8, 7]
第4次排序结果是: [3, 4, 5, 6, 2, 1, 8, 7]
第5次排序结果是: [2, 3, 4, 5, 6, 1, 8, 7]
第6次排序结果是: [1, 2, 3, 4, 5, 6, 8, 7]
第7次排序结果是: [1, 2, 3, 4, 5, 6, 8, 7]
第8次排序结果是: [1, 2, 3, 4, 5, 6, 7, 8]
最后的结果是: [1, 2, 3, 4, 5, 6, 7, 8]
'''

C语言实现及其优化

#include<stdio.h>


void insert_sort1(int arr[],int len)
{
    for(int i=1; i<len; i++)
    {
        for(int j=0; j<i; j++)
        {
            if(arr[j]>arr[i])
            {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

/*
优化方式:
二分查找法来减少比较操作的次数

二分法插入排序,简称二分排序,是在插入第i个元素时,对前面的0～i-1元素进行折半,先跟他们中间的那个元素比,如果小,则对前半再进行折半,否则对后半进行折半,直到left<right,然后再把第i个元素前1位与目标位置之间的所有元素后移,再把第i个元素放在目标位置上.

法思想简单描述:
二分法没有排序,只有查找.所以当找到要插入的位置时.移动必须从最后一个记录开始,向后移动一位,再移动倒数第2位,直到要插入的位置的记录移后一位.

二分插入排序是稳定的与二分查找的复杂度相同
最好的情况是当插入的位置刚好是二分位置 所用时间为O(log₂n);
最坏的情况是当插入的位置不在二分位置 所需比较次数为O(n),无限逼近线性查找的复杂度.
S<=∑n「log₂n「-2^n「log₂n「+1
k= 1
平均时间O(n^2)
*/
void insert_sort2(int arr[],int len)
{
    int i,j,left,mid,right;
    int count=0;
    for(i=1; i<len; i++)
    {
        int temp = arr[i];
        left = 0;
        right = i-1;                /* 置已排序区间的下、上界初值 */
        while(left <= right)
        {
            mid =(left + right)/2; /* mid指向已排序区间的中间位置 */
            if(arr[i] < arr[mid])
                right = mid-1;      /* 插入元素应在左子区间 */
            else
                left = mid+1;       /* 插入元素应在右子区间 */
        }
        for(j = i-1; j >= left; j--)
            arr[j+1] = arr[j];      /* 将排序码大于ki的记录后移 */
        if(left != i)
            arr[left] = temp;
            count ++;
    }
    printf("本次排序一共交换了%d次\n",count);
}

/*
不用先查找,而是在内存循环直接将满足条件的元素后移(这里的移动可以用交换),最后将元素插入合适的位置;
*/
void insert_sort3(int nums[],int len)
{
    int tem;
    int j;
    for(int i = 0; i < len; i++)
    {
        tem = nums[i];
        //这里代码优化:可以将if条件加到for中  for(j = i;j > 0 && tem < nums[j-1];j--)
        for(j = i; j > 0; j--)
        {
            if(tem < nums[j - 1])
                nums[j] = nums[j - 1];
            else
                break;
        }
        nums[j] = tem;
    }
}


/*
对数组进行简单预处理,循环数组将nums[i]>nums[i+1]的两个元素进行交换,如果未进行交换是有序的,然后在进行插入排序
*/
void insert_sort4(int nums[],int len)
{
    int j;
    int tem;
    for(int i = 0; i < len; i++){
        for(j = i; j > 0  && nums[j] < nums[j - 1]; j--){
            tem = nums[j - 1];
            nums[j - 1] = nums[j];
            nums[j] = tem;
        }
    }
}


int main()
{
//    int dest1[7] = { 5,3,4,6,2,1,7 };
//    insert_sort1(dest1,7);
//    for(int i=0;i<7;i++)
//        printf("%d ",dest1[i]);
//    printf("\n");

//    int dest2[7] = { 5,3,4,6,2,1,7 };
//    insert_sort2(dest2,7);
//    for(int i=0;i<7;i++)
//        printf("%d ",dest2[i]);
//    printf("\n");


//    int dest3[7] = { 5,3,4,6,2,1,7 };
//    insert_sort3(dest3,7);
//    for(int i=0;i<7;i++)
//        printf("%d ",dest3[i]);
//    printf("\n");

    int dest4[7] = { 5,3,4,6,2,1,7 };
    insert_sort4(dest4,7);
    for(int i=0;i<7;i++)
        printf("%d ",dest4[i]);
    printf("\n");


    return 0;
}