C算法：插入排序（内附详细图解）！！！

插入排序

下面是示意图：

直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列。[1]
例如,已知待排序的一组纪录是：
60,71,49,11,24,3,66
假设在排序过程中，前3个纪录已按关键码值递增的次序重新排列，构成一个有序序列：
49,60,71
将待排序纪录中的第4个纪录（即11）插入上述有序序列，以得到一个新的含4个纪录的有序序列。首先，应找到11的插入位置，再进行插入。可以讲11放入数组的第一个单元r[0]中，这个单元称为监视哨，然后从71起从右到左查找，11小于71，将71右移一个位置，11小于60，又将60右移一个位置，11小于49，又再将49右移一个位置，这时再将11与r[0]的值比较，11≥r[0]，它的插入位置就是r[1]。假设11大于第一个值r[1]。它的插入位置应该在r[1]和r[2]之间，由于60已经右移了，留出来的位置正好留给11.后面的纪录依照同样的方法逐个插入到该有序序列中。若纪录数n,续进行n-1趟排序，才能完成。
直接插入排序的算法思路：
（1） 设置监视哨r[0]，将待插入纪录的值赋值给r[0]；
（2） 设置开始查找的位置j；
（3） 在数组中进行搜索，搜索中将第j个纪录后移，直至r[0].key≥r[j].key为止；
（4） 将r[0]插入r[j+1]的位置上。

例1

实现代码：

#include <iostream>
using namespace std;

//exchange the 2 items a and b
void swap(int &a, int &b)
{
    if (a == b)
        return;
    a = a + b;
    b = a - b;
    a = a - b;
}

//ergodic the buf and print it
void ergodic(int  *p,int length)
{
    for (int i = 0; i < length; i++)
    {
        cout << p[i] << " ";
    }
}

void insert_sort(int  *p, int length)
{
    int k; //记录当前要插入的元素的下标
    int temp; //记录当前要插入的元素的值

    for (int i = 1; i < length; i++) //默认第一个元素已经是有序的，因此从第二个元素开始
    {
        k = i;
        temp = p[k];
        int j = i - 1;
        while ((j >=0)&&(p[j] > temp)) //前一个元素比待插元素大
        {
            p[j + 1] = p[j]; //如果待插入元素比拍好元素大，则循环右移大的那部分元素
            //留出位置给待插元素
            k = j; //记录待插元素需要插入的位置
            j--;

        }
        p[k] = temp; //插入元素
    }
}

int main(int argc, char *args[])
{
    int buf[10] = { 12, 4, 34, 6, 8, 65, 3, 2, 988, 45 };
    int m = sizeof(buf);
    cout << "排序前:" << endl;
    ergodic(buf,sizeof(buf)/sizeof(int));

    //BubbleSort(buf, sizeof(buf) / sizeof(int));
    //select_sort(buf, sizeof(buf) / sizeof(int));
    insert_sort(buf, sizeof(buf) / sizeof(int));

    cout << "\n\n\n排序后：" << endl;
    ergodic(buf, sizeof(buf) / sizeof(int));
    getchar();

}

运行结果：

例2

实现代码：

#include<iostream>
#include<vector>
#include<random>
#include<ctime>
#include<iterator>
#include<algorithm>
using namespace std;
 
/*
* 插入排序，从小到大
*/
template<typename T>
void insertionSort(vector<T> & a)
{
	for (size_t p = 1; p < a.size(); ++p) // 从第二个数开始
	{
		T tmp = a[p];
		size_t j = p;
		for (; j > 0 && a[j-1] > tmp; --j)
			a[j] = a[j-1];
		a[j] = tmp;
	}
}
 
template<typename T>
void printVector(vector<T> & v)
{
	copy(v.cbegin(), v.cend(), ostream_iterator<T>(cout, " "));
	cout << endl;
}
 
int main()
{
	vector<int> source;
	uniform_int_distribution<int> u(0, 100);
	default_random_engine e(static_cast<unsigned int>(time(0)));
	for (int i = 0; i < 10; i++)
	{
		source.push_back(u(e));
	}
 
	cout << "排序前：" << endl;
	printVector(source);
 
	insertionSort(source);
	
	cout << "排序后：" << endl;
	printVector(source);
 
	return 0;
}

运行结果：

总结：

插入排序叫其它两种简单排序冒泡和选择排序，虽然算法复杂度都是O(n^2)，但是其思想相对于他们要难理解一点。其思想主要是将一个待排数列分为两个数列，第一个数列只有第一个元素(只有一个元素当然是有序的)，第二个序列为第二个元素到最后一个元素。因此for循环从第一个元素开始，最后一个元素截止，将数据一个个的插入第一个数列
for (int i = 1; i < length; i++)，在这个for循环里面我们需要记下当前要插入的元素的下标和值，然后用一个while循环判断当前插入元素和之前排号元素的大小关系，并进行移动为待插元素腾出位置。
int j = k -1; j记录的则是已排好序列的最后一个下标
while( p[j] > temp) 判断已排好的序列的最大值是否比待插值大，如果是，则移动已排好的序列，如果不是，那在它之前的元素更加不可能比待插值大，最后将待插值插入指定的地方。
虽然插入排序理解起来较为复杂，但是它也是一个稳定的排序，而且，在后面的排序都是基于插入排序进行改进以提高排序效率。

小伙伴们学会了吗？