排序算法一：插入排序

马谦马谦马谦

615
文章

17
评论

2018年3月3日20:56:24数据结构和算法评论399字数 348阅读1分9秒阅读模式

一、原理

从排序序列的第二个元素开始，依次往前面查询，知道找到一个合适的位置就把它插进去。每个元素在交换完成之后[0, n]都是一个有序序列，它的时间复杂度为O(n^2)。

排序逻辑：

for i in (1, n-1) 
    使用data[i]前向查找，找到一个合适的位置插入

1 2	for i in (1, n-1) 使用data[i]前向查找，找到一个合适的位置插入

以下是对序列[3, 7, 4, 1, 9, 6]的插入排序过程，初始时的状态为：

排序算法一：插入排序-图片1

执行第一次插入（从第二个元素开始），把7放到合适的位置：

排序算法一：插入排序-图片2

执行第二次插入过程，把4放到合适位置：

排序算法一：插入排序-图片3

执行第三次插入过程，把1放到合适位置：

排序算法一：插入排序-图片4

执行第四次插入过程，把9放到合适位置：

排序算法一：插入排序-图片5

执行最后一次插入过程，把6放到合适位置：

排序算法一：插入排序-图片6

二、代码实现

1. C++实现

void insert_sort(vector<int> &data){
    auto length = data.size();
    decltype(length) i, j, k;
    if (length < 2){ 
        return;
    }   
    int tmp;
    for (i = 1; i < length; i++){
        tmp = data[i];
        for (j = i; j > 0 && tmp < data[j - 1]; j--){
            data[j] = data[j - 1]; 
        }   
        data[j] = tmp;
    }   
}

void insert_sort(vector<int> &data){

auto length = data.size();

decltype(length) i, j, k;

if (length < 2){

return;

}

int tmp;

for (i = 1; i < length; i++){

tmp = data[i];

for (j = i; j > 0 && tmp < data[j - 1]; j--){

data[j] = data[j - 1];

}

data[j] = tmp;

}

2. python实现

def insert_sort(data):
    size = len(data)
    if size < 2:
        return
    for i in range(1, size):
        tmp = data[i]
        j = i
        while j > 0 and tmp < data[j - 1]:
            data[j] = data[j - 1]
            j -= 1
        data[j] = tmp