綜述

插入排序(Insertion-Sort)的算法描述是一種簡單直觀的排序算法.
它的工作原理是通過構(gòu)建有序序列,對(duì)于未排序數(shù)據(jù),在已排序序列中從后向前掃描,找到相應(yīng)位置并插入.

算法描述

一般來說,插入排序都采用in-place在數(shù)組上實(shí)現(xiàn).具體算法描述如下:
1.從第一個(gè)元素開始,該元素可以認(rèn)為已經(jīng)被排序;
2.取出下一個(gè)元素,在已經(jīng)排序的元素序列中從后向前掃描;
3.如果該元素(已排序)大于新元素,將該元素移到下一位置;
4.重復(fù)步驟3,直到找到已排序的元素小于或者等于新元素的位置;
5.將新元素插入到該位置后;
6.重復(fù)步驟2~5.

示意圖

插入排序動(dòng)態(tài)圖

插入排序靜態(tài)圖

性質(zhì)

排序類別:交換排序
是否是穩(wěn)定排序:穩(wěn)定
是否是原地排序:是
時(shí)間復(fù)雜度:最好為O(N), 最壞為O(N^2), 所以時(shí)間復(fù)雜度為O(N^2)
空間復(fù)雜度:O(1)

解釋

直接插入排序(Straight Insertion Sort)的基本思想是:
把n個(gè)待排序的元素看成為一個(gè)有序表和一個(gè)無序表.
開始時(shí)有序表中只包含1個(gè)元素,無序表中包含有n-1個(gè)元素,排序過程中每次從無序表中取出第一個(gè)元素,將它插入到有序表中的適當(dāng)位置,使之成為新的有序表,重復(fù)n-1次可完成排序過程.

直接插入排序?qū)τ跀?shù)據(jù)規(guī)模較小或者基本有序的數(shù)據(jù)效率很高。
數(shù)據(jù)有序程序越高，直接插入排序越高效。

優(yōu)化

優(yōu)化方式一

二分插入排序
二分法插入排序,簡稱二分排序,是在插入第i個(gè)元素時(shí),對(duì)前面的0～i-1元素進(jìn)行折半,先跟他們中間的那個(gè)元素比,如果小,則對(duì)前半再進(jìn)行折半,否則對(duì)后半進(jìn)行折半,直到left<right,然后再把第i個(gè)元素前1位與目標(biāo)位置之間的所有元素后移,再把第i個(gè)元素放在目標(biāo)位置上.

算法思想簡單描述:二分法沒有排序,只有查找.所以當(dāng)找到要插入的位置時(shí).移動(dòng)必須從最后一個(gè)記錄開始,向后移動(dòng)一位,再移動(dòng)倒數(shù)第2位,直到要插入的位置的記錄移后一位.

二分插入排序是穩(wěn)定的與二分查找的復(fù)雜度相同:平均時(shí)間O(n^2)
最好的情況是當(dāng)插入的位置剛好是二分位置 所用時(shí)間為O(log?n);
最壞的情況是當(dāng)插入的位置不在二分位置 所需比較次數(shù)為O(n),無限逼近線性查找的復(fù)雜度.
S<=∑n「log?n「-2^n「log?n「+1
k= 1
平均時(shí)間O(n^2)

優(yōu)化方式二

不用先查找，而是在內(nèi)存循環(huán)直接將滿足條件的元素后移（這里的移動(dòng)可以用交換），最后將元素插入合適的位置；

優(yōu)化方式三

對(duì)數(shù)組進(jìn)行簡單預(yù)處理，循環(huán)數(shù)組將nums[i]>nums[i+1]的兩個(gè)元素進(jìn)行交換，如果未進(jìn)行交換是有序的，然后在進(jìn)行插入排序

Python實(shí)現(xiàn)及其優(yōu)化

def insert_sort1(dest_list=[]):
    if len(dest_list) < 2:
        return dest_list
    count = 0
    for i in range(1, len(dest_list)):
        print('第{}次排序?yàn)?'.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('最后進(jìn)行交換的次數(shù)是:{}'.format(str(count)))
    return dest_list

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

'''
第1次排序?yàn)? [5, 3, 4, 6, 2, 1, 7]
---- [5, 3, 4, 6, 2, 1, 7]
第2次排序?yàn)? [3, 5, 4, 6, 2, 1, 7]
---- [3, 5, 4, 6, 2, 1, 7]
---- [3, 4, 5, 6, 2, 1, 7]
第3次排序?yàn)? [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次排序?yàn)? [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次排序?yàn)? [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次排序?yàn)? [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]
最后的結(jié)果是: [1, 2, 3, 4, 5, 6, 7]
'''


"""
優(yōu)化方式一
為減少查找時(shí)間：使用二分查找元素插入位置；

二分法插入排序，簡稱二分排序，是在插入第i個(gè)元素時(shí)，對(duì)前面的0～i-1元素進(jìn)行折半，先跟他們中間的那個(gè)元素比，如果小，則對(duì)前半再進(jìn)行折半，否則對(duì)后半進(jìn)行折半，直到left<right，然后再把第i個(gè)元素前1位與目標(biāo)位置之間的所有元素后移，再把第i個(gè)元素放在目標(biāo)位置上。

二分法插入排序，簡稱二分排序，是在插入第i個(gè)元素時(shí)，對(duì)前面的0～i-1元素進(jìn)行折半，先跟他們中間的那個(gè)元素比，如果小，則對(duì)前半再進(jìn)行折半，否則對(duì)后半進(jìn)行折半，直到left<right，然后再把第i個(gè)元素前1位與目標(biāo)位置之間的所有元素后移，再把第i個(gè)元素放在目標(biāo)位置上。

算法思想簡單描述：
二分法沒有排序，只有查找。所以當(dāng)找到要插入的位置時(shí)。移動(dòng)必須從最后一個(gè)記錄開始，向后移動(dòng)一位，再移動(dòng)倒數(shù)第2位，直到要插入的位置的記錄移后一位。

二分插入排序是穩(wěn)定的與二分查找的復(fù)雜度相同
最好的情況是當(dāng)插入的位置剛好是二分位置 所用時(shí)間為O(log?n);
最壞的情況是當(dāng)插入的位置不在二分位置 所需比較次數(shù)為O(n)，無限逼近線性查找的復(fù)雜度。
S<=∑n「log?n「-2^n「log?n「+1
k= 1
平均時(shí)間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]

        # 二分法進(jìn)行插入位置的查找
        left = 0
        right = i - 1
        # 待插入的值與已排序區(qū)域的中間值比較，不斷縮小區(qū)域范圍，直到left和right相遇。
        while left <= right:
            mid = (left + right) // 2
            if arr[i] < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1

        # 當(dāng)left和right相遇的時(shí)候，待插入的位置其實(shí)就是left的位置，此時(shí)要將left到有序序列的最后一個(gè)元素都向后移動(dòng)一個(gè)位置，才能插入元素。
        # 這里一定要用left-1,否則當(dāng)left的位置就是有序序列的最后一個(gè)位置時(shí)，j取不到值，后面的元素會(huì)被這個(gè)位置的元素值覆蓋。
        for j in range(i - 1, left - 1, -1):
            arr[j + 1] = arr[j]

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

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

'''
第1次排序?yàn)? [3, 5, 4, 6, 2, 1, 8, 7]
第2次排序?yàn)? [3, 4, 5, 6, 2, 1, 8, 7]
第3次排序?yàn)? [3, 4, 5, 6, 2, 1, 8, 7]
第4次排序?yàn)? [2, 3, 4, 5, 6, 1, 8, 7]
第5次排序?yàn)? [1, 2, 3, 4, 5, 6, 8, 7]
第6次排序?yàn)? [1, 2, 3, 4, 5, 6, 8, 7]
第7次排序?yàn)? [1, 2, 3, 4, 5, 6, 7, 8]
共循環(huán)5次
最后的結(jié)果是: [1, 2, 3, 4, 5, 6, 7, 8]
'''

"""
優(yōu)化方式二
不用先查找，而是在內(nèi)存循環(huán)直接將滿足條件的元素后移（這里的移動(dòng)可以用交換），最后將元素插入合適的位置；
"""


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('第{}次排序結(jié)果是:'.format(str(i+1)), dest_list)
    return dest_list

'''
第1次排序結(jié)果是: [1, 2, 3, 4, 5, 6, 7]
第2次排序結(jié)果是: [1, 2, 3, 4, 5, 6, 7]
第3次排序結(jié)果是: [1, 2, 3, 4, 5, 6, 7]
第4次排序結(jié)果是: [1, 2, 3, 4, 5, 6, 7]
第5次排序結(jié)果是: [1, 2, 3, 4, 5, 6, 7]
第6次排序結(jié)果是: [1, 2, 3, 4, 5, 6, 7]
第7次排序結(jié)果是: [1, 2, 3, 4, 5, 6, 7]
最后的結(jié)果是: [1, 2, 3, 4, 5, 6, 7]
**************************************************
第1次排序結(jié)果是: [1, 2, 3, 4, 5, 6, 7, 8]
第2次排序結(jié)果是: [1, 2, 3, 4, 5, 6, 7, 8]
第3次排序結(jié)果是: [1, 2, 3, 4, 5, 6, 7, 8]
第4次排序結(jié)果是: [1, 2, 3, 4, 5, 6, 7, 8]
第5次排序結(jié)果是: [1, 2, 3, 4, 5, 6, 7, 8]
第6次排序結(jié)果是: [1, 2, 3, 4, 5, 6, 7, 8]
第7次排序結(jié)果是: [1, 2, 3, 4, 5, 6, 7, 8]
第8次排序結(jié)果是: [1, 2, 3, 4, 5, 6, 7, 8]
最后的結(jié)果是: [1, 2, 3, 4, 5, 6, 7, 8]
**************************************************
第1次排序結(jié)果是: [7, 6, 5, 4, 3, 2, 1]
第2次排序結(jié)果是: [7, 6, 5, 4, 3, 2, 1]
第3次排序結(jié)果是: [7, 5, 6, 4, 3, 2, 1]
第4次排序結(jié)果是: [7, 4, 5, 6, 3, 2, 1]
第5次排序結(jié)果是: [7, 3, 4, 5, 6, 2, 1]
第6次排序結(jié)果是: [7, 2, 3, 4, 5, 6, 1]
第7次排序結(jié)果是: [7, 1, 2, 3, 4, 5, 6]
最后的結(jié)果是: [7, 1, 2, 3, 4, 5, 6]
**************************************************
第1次排序結(jié)果是: [8, 7, 6, 5, 4, 3, 2, 1]
第2次排序結(jié)果是: [8, 7, 6, 5, 4, 3, 2, 1]
第3次排序結(jié)果是: [8, 6, 7, 5, 4, 3, 2, 1]
第4次排序結(jié)果是: [8, 5, 6, 7, 4, 3, 2, 1]
第5次排序結(jié)果是: [8, 4, 5, 6, 7, 3, 2, 1]
第6次排序結(jié)果是: [8, 3, 4, 5, 6, 7, 2, 1]
第7次排序結(jié)果是: [8, 2, 3, 4, 5, 6, 7, 1]
第8次排序結(jié)果是: [8, 1, 2, 3, 4, 5, 6, 7]
最后的結(jié)果是: [8, 1, 2, 3, 4, 5, 6, 7]
**************************************************
'''


"""
優(yōu)化方式三
對(duì)數(shù)組進(jìn)行簡單預(yù)處理，循環(huán)數(shù)組將nums[i]>nums[i+1]的兩個(gè)元素進(jìn)行交換，如果未進(jìn)行交換是有序的，然后在進(jìn)行插入排序
"""


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('第{}次排序結(jié)果是:'.format(str(i+1)), dest_list)
    return dest_list

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

C語言實(shí)現(xiàn)及其優(yōu)化

#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;
            }
        }
    }
}

/*
優(yōu)化方式:
二分查找法來減少比較操作的次數(shù)

二分法插入排序,簡稱二分排序,是在插入第i個(gè)元素時(shí),對(duì)前面的0～i-1元素進(jìn)行折半,先跟他們中間的那個(gè)元素比,如果小,則對(duì)前半再進(jìn)行折半,否則對(duì)后半進(jìn)行折半,直到left<right,然后再把第i個(gè)元素前1位與目標(biāo)位置之間的所有元素后移,再把第i個(gè)元素放在目標(biāo)位置上.

法思想簡單描述:
二分法沒有排序,只有查找.所以當(dāng)找到要插入的位置時(shí).移動(dòng)必須從最后一個(gè)記錄開始,向后移動(dòng)一位,再移動(dòng)倒數(shù)第2位,直到要插入的位置的記錄移后一位.

二分插入排序是穩(wěn)定的與二分查找的復(fù)雜度相同
最好的情況是當(dāng)插入的位置剛好是二分位置 所用時(shí)間為O(log?n);
最壞的情況是當(dāng)插入的位置不在二分位置 所需比較次數(shù)為O(n),無限逼近線性查找的復(fù)雜度.
S<=∑n「log?n「-2^n「log?n「+1
k= 1
平均時(shí)間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;                /* 置已排序區(qū)間的下、上界初值 */
        while(left <= right)
        {
            mid =(left + right)/2; /* mid指向已排序區(qū)間的中間位置 */
            if(arr[i] < arr[mid])
                right = mid-1;      /* 插入元素應(yīng)在左子區(qū)間 */
            else
                left = mid+1;       /* 插入元素應(yīng)在右子區(qū)間 */
        }
        for(j = i-1; j >= left; j--)
            arr[j+1] = arr[j];      /* 將排序碼大于ki的記錄后移 */
        if(left != i)
            arr[left] = temp;
            count ++;
    }
    printf("本次排序一共交換了%d次\n",count);
}

/*
不用先查找,而是在內(nèi)存循環(huán)直接將滿足條件的元素后移(這里的移動(dòng)可以用交換),最后將元素插入合適的位置;
*/
void insert_sort3(int nums[],int len)
{
    int tem;
    int j;
    for(int i = 0; i < len; i++)
    {
        tem = nums[i];
        //這里代碼優(yōu)化:可以將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;
    }
}


/*
對(duì)數(shù)組進(jìn)行簡單預(yù)處理,循環(huán)數(shù)組將nums[i]>nums[i+1]的兩個(gè)元素進(jìn)行交換,如果未進(jìn)行交換是有序的,然后在進(jìn)行插入排序
*/
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;
}