主要内容 #

1. 插入排序步骤
2. 插入排序练习2
3. 插入排序练习1

1. 插入排序步骤 #

1.1 算法思想 #

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
插入排序操作类似于摸牌并将其从大到小排列。每次摸到一张牌后，根据其点数插入到确切位置。

如上图：表示的是摸到草花7后进行插入的过程。忽略最右边的草花10，相当于一开始7在最右边，然后逐个与左边的牌相比较(当然左边的牌早已排好顺序)，将其放置在合适的位置。当摸到草花10后重复上述过程即可。

1.2 实现步骤： #

① 从第一个元素开始，该元素可以认为已经被排序
② 取出下一个元素，在已经排序的元素序列中从后向前扫描
③如果该元素（已排序）大于新元素，将该元素移到下一位置
④ 重复步骤③，直到找到已排序的元素小于或者等于新元素的位置
⑤将新元素插入到该位置后
⑥ 重复步骤②~⑤

2. 插入排序练习1 #

问题：以下程序执行后，数组中的元素是什么顺序？

#include <iostream>
using namespace std;

//sorted_right_index：目前已经排好序的数组的最大的下标。
//value: 待插入的元素。
void insert(int arr[], int sorted_right_index, int value)
{
    int pos = sorted_right_index;
    while (pos >= 0 && arr[pos] > value)
    {
        arr[pos + 1] = arr[pos];
        pos--;
    }
    arr[pos + 1] = value;
}

int main()
{
    int arr[8] = {3, 5, 7, 11, 13, 2, 9, 6};
    //前5(4+1)个元素已经排好，待插入元素2
    insert(arr, 4, 2);
    return 0;
}

3. 插入排序练习2 #

题目描述
给定包含N个元素的数组a1,a2,a3,…,aN，利用插入排序将其排成升序，
每次拿出未排序部分中的第一个元素，插入到已排序部分中，排在首个不大于这个元素的后面。
输入
2行
第1行包含1个正整数N（1 < N <= 10000），代表数组元素个数
第2行包含N个整数，空格隔开。
输出
N-1行，既依次输出每趟选择排序后的数组。
样例输入
4
4 3 1 2
样例输出
3 4 1 2
1 3 4 2
1 2 3 4
参考程序

#include < iostream >
using namespace std;
void insertion_sort(int arr[], int len)
{
    for (int i = 1; i < len; i++)
    {   //当前需要插入的数据
        int key = arr[i];
        //需要插入的位置
        int j = i - 1;
        while ((j >= 0) && (key < arr[j]))
        {
            arr[j + 1] = arr[j];
            j--;
        }
        //插入数据
        arr[j + 1] = key;
        for(int k = 0; k < len; ++k){
            cout << arr[k] << ' ';
        }
        cout << endl;
    }
}

int main()
{
    int arr[10001];
    int N;
    cin >> N;
    for(int i = 0; i < N; ++i){
        cin >> arr[i]; 
    }
    insertion_sort(arr, N);
    return 0;
}