排序问题之插入排序

排序问题

算法问题的基础问题之一，便是排序问题：

　　输入：n个数的一个序列，<a₁, a₂,..., a_n>。

　　输出：一个排列<a_1^‘,a_2^‘, ... , a_n‘>，满足a_1^‘ ≤ a_2^‘ ≤... ≤ a_n‘ 。（输出亦可为降序，左边给出的例子为升序）

一.算法描述

      首先我们来看一种算法叫做插入排序。类比我们玩扑克牌时手上会首先拿到十几张无序的牌组，我们从左往右依次整理顺序使牌的大小从左至右保持不减。那么我们会把第二张牌插入其左边使左边两张牌成有序，再把第三张牌插入其左边使左边三张牌成有序，依次类推，直到把最后一张牌插入其左边之后手中的所有牌成有序状态。

      下面我们给出一个对序列[5, 2, 4, 6, 1, 3]使用插入排序得到递增序列的过程，在图中蓝色的部分是排序好的序列，红色部分标记即将插入到前面的元素，白色部分为未排序的部分。每进行一次插入操作后，sorted序列元素个数加1，unsorted序列元素个数减1，直到unsorted序列中无元素时终止。

二.代码实现

      下面是插入排序的C++实现：

#include<iostream>
#include<vector>
using namespace std;
//对向量进行插入排序
void InsertionSort(vector<int> &v)
{
    int i, j, key;

    //从第二个元素开始遍历数组
    for(i = 1; i < v.size(); i++){

        //取要插入的元素key
        key = v[i];

        //倒过来遍历key左边的sorted list, 如果不插入则右移一位直到j停留的位置值小于key或来到头部
        j = i - 1;
        while(j >= 0 && v[j] > key){
            v[j+1] = v[j];
            j--;
        }

        //插入key
        v[j+1] = key;
    }
}

int main()
{
    //arr为要排序的数组
    int arr[] = {5,2,4,7,10,9,8,1,6,3};

    //把数组放入向量中
    vector<int> v(arr, arr + sizeof(arr)/sizeof(int));
    
    //对向量使用插入排序
    InsertionSort(v);

    //按顺序打印排序后向量中的所有元素
    copy (v.begin(), v.end(), ostream_iterator<int> (cout, " "));
    cout << endl;
    
}

二.算法分析

（1）时间复杂度

　　Best-case：数组已排好序。每次考虑要插入的key时都比前一个大，则都不用移动。时间复杂度为o(n)。

　　Worst-case：数组已反向排好序。每次考虑要插入的key时都比第一个元素小，key前面的所有元素要往后挪动一个位置，然后key要头插。时间复杂度为o(n²)。

　　Average-case：每次考虑要插入的key时，期望会在前面序列的中间找到插入的位置。时间复杂度为o(n²)。

（2）稳定性

　　稳定性是指对于原有序列中的等值元素，是否在排序后不改变它们的相对顺序关系。分析易知插入排序是稳定的

（3）适合范围

      当需要排序的数组大多数都已排好序时（Almost Already Sorted），这种情况能更接近Best-case，使用插入排序所需的计算步骤更少。

排序问题之插入排序

原文：https://www.cnblogs.com/lovelybunny/p/10828429.html