插入排序-排序算法

前言

在玩斗地主的时候，你是如何理牌的？

当我们手中没扑克牌时，不管抓的是什么牌，都是放到手里。其他时候拿到一张牌，是从右向左找一个位置：右边是大于这张牌，左边是小于等于这张牌或者左边没有牌。而插入排序的思想就是这个。

插入排序

插入排序：它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因为在从后向前扫描的过程中，需要反复把已排序的元素逐步向后挪位，为新元素提供插入空间。

具体描述如下：

1.从第一个元素开始，该元素可以认为已经被排序；

2.取出下一个元素，在已经排序的元素序列中从后向前扫描；

3.如果该元素(己排序)大于新元素，将该元素移到下一位置；
重复步骤3，直到找到己排序的元素小于或者等于新元素的位置。

4.将新元素插入到该位置;

重复步骤2~5

例子

下面提供一个例子直观地展示前面的概念，以这一组数据：18,14,10,19,1,3 为例。

1.首先从第一个元素 18 开始考虑，因为只有一个，认为已经有序（有序序列用橙色表示）。

2.选取下一个元素 14 保存起来，并让 14 所在的位置空出来，在有序的序列中从后往前遍历。

3.元素 18 大于新元素 14 ，将元素 18 向后移动。

4.元素 18 前已经没有元素了，将刚刚保存的元素 14 放到空位。这样，14这个新元素就加入了有序序列。

5.选取下一个元素 10 保存起来，并让10所在的位置空出，在有序的序列中从后向前扫描。

6.元素 18 大于 10 ， 18 向后移一位。

7.元素 14 大于 10，14向后移动。

8.元素 14 前已经没有数了，将刚刚保存下来的元素 10?放到空位中。这样，有序序列又加入了一个数 10。

9.选取下一个元素 19 保存起来，让其所在位置空出，在有序序列中由后到前比较。

10.不断比较，直到找到小于等于新元素的位置，恰好第一次比较就找到了 18 ，把 19 放入空位。

……

这样重复地比较、挪位，放入位置。就能得到有序的整个数组。

代码

也许上面这个过程你能明白，可是代码才是解决问题的。

#include <iostream>
using namespace std;


void InsertSort(int arr[], int left, int right)
{
	int current = 0; // 保存要插入的元素的值（新元素）
	int preindex = 0; // 指向有序序列中的数

	for (int i = left + 1; i <= right; i++)
	{
		current = arr[i];
		preindex = i - 1;
		while (preindex >= left && arr[preindex] > current)
		{
			arr[preindex + 1] = arr[preindex];
			preindex--;
		} //循环结束后就找到了合适的位置的前一个位置

		arr[preindex + 1] = current;
	}

}


int main(void)
{
	int arr[] = { 18,14,10,19,1,3 };
	int len = sizeof(arr) / sizeof(arr[0]);

	InsertSort(arr, 0, len - 1);

	for (int i = 0; i < len; i++)
	{
		cout << arr[i] << " ";
	}
	return 0;
}