插入排序

插入排序（Insertion Sort）是一种简单直观的排序算法。其工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序算法描述如下（以升序排序为例说明）：

1. 首先将第一个元素放入有序序列，当前有序序列只有一个元素；
2. 取无序部分的第一个元素作为待排序元素 x，在有序序列中从后向前扫描；
3. 如果扫描到有序序列的当前元素 y 大于待排序元素 x，将当前元素 y 后移到下一位置；
4. 重复步骤 3，在有序序列一直向前扫描，直到找到一个元素小于待排序元素的位置 pos；
5. 将待排序元素 x 插入到该位置 pos 后（pos+1处）；
6. 重复步骤 2~5，直到处理完所有待排序元素。

可知插入排序是从序列的第 2 个元素开始，将每个元素前插到前面的合适位置，使得序列第 1 个元素到该元素的整个区间有序。插入排序仍然是将序列前面部分变得有序，并且将有序的区间逐步扩大直到整个序列有序。我们玩扑克牌游戏，抓牌后一般会将手里的牌整理有序，一般的做法就是这里介绍的插入排序。

因为第一个元素不用前插，所以 \(n\) 个元素的序列插入排序需要经过 \(n-1\) 次前插到前面合适位置的过程：

//插入排序：对数组的r[0]~r[n-1]区域排序（升序排序）
void InsertSort(int r[],int n){
	for(int i=1;i<=n-1;i++){
		//考察当前r[i]插入到r[i-1]~r[0]哪一个元素前面 
		int x = r[i],k = i-1;  //前插后移会覆盖掉r[i]，所以先将r[i]保存到x中
		while(k>=0 && x<r[k]){	//x<r[k]，那么x插入的位置还能再靠前 
			//x要前插，那么r[k]要后移一位 
			r[k+1] = r[k];
			k--;
		}
		//插入到r[k+1] 
		r[k+1] = x;
	}
}
//调用方法举例：InsertSort(a,10);
//调用方法举例：InsertSort(a,n);

仿照 sort 函数的写法，用两个指针作为函数参数来指定排序的区域：

//插入排序：对指针begin~end区域排序（升序排序，不包括end）
void InsertSort(int *begin,int *end){
	for(int *p = begin+1;p<end;p++){
		//考察当前 x(也就是*p) 插入到 p-1 ~ begin哪一个元素前面 
		int x = *p,*q = p-1;  //前插后移会覆盖掉*p，所以先将*p保存到x中
		while(q>=begin && x < *q){	//x<*q，那么x插入的位置还能再靠前 
			//*p要前插，那么*q要后移一位 
			*(q+1) = *q;
			q--;
		}
		//插入到 q+1
		*(q+1) = x;
	}
}
//调用方法举例：InsertSort(a,a+10);
//调用方法举例：InsertSort(a,a+n);
//调用方法举例：InsertSort(a+1,a+n+1);

插入排序的时间复杂度是 \(O(n^2)\)，因为插入排序是依次让每个元素前插到合适位置，所以是稳定的。

考虑插入排序的特点，可以在输入数据的同时，将输入的数据前插到数组合适的位置，提高程序运行效率。