简述

直接插入排序是一种最简单的排序方法，基本操作是讲一个记录插入到已排好的有序数列中。

当序列“基本有序”或者待排序记录很少时，插入排序的性能非常好。

代码实例

#include
    
     using namespace std;//前面提供两个辅助函数，一个二分查找函数，一个打印序列函数。int bin_search(int raw[], int begin, int end, int search){	//二分查找，返回被查找数应当放置的顺序位置	//n is the real length (do not include 0)	int low = begin;	int high = end;	while (low <= high){		int mid = (low + high) / 2;		if (search == raw[mid]) return mid;		if (search < raw[mid]) high = mid - 1;		if (search > raw[mid]) low = mid + 1;	}	//if not searched, low is the pos the searched number should placed	//raw[low]is higher than search,raw[high] is lower than search;	return low;}void dispList(int raw[], int n){	//from 1 to n not 0 to n	for (int i = 1; i <= n; i++) cout << raw[i] << ' ';}void simpleInsertSort(int raw[], int n){	//简单直接插入排序	int temp, j;	for (temp = 2; temp <= n; temp++){		raw[0] = raw[temp];         //raw[0]用作哨兵		for (j = temp - 1; raw[j]>raw[0]; j--)			raw[j + 1] = raw[j];    //大的记录依次向后移动		raw[j + 1] = raw[0];    //移动后，将新的位置留给新进入的记录	}}void simpleInsertSort_Bin(int raw[], int n){	//简单二分插入排序	int temp, j;	for (temp = 2; temp <= n; temp++){		raw[0] = raw[temp];		int pos = bin_search(raw, 1, temp - 1, raw[temp]);	//pos返回的位置是二分查找后，其被查找结果对应的顺序位置。		for (j = temp - 1; j >= pos; j--){ raw[j + 1] = raw[j]; }		raw[pos] = raw[0];	}}//以上是简单插入排序//如下给出希尔增量排序代码，其中增量序列随意取的，不具有优化意义。至于增量序列的取法这里不做讨论。void shellSort_basic(int raw[], int n, int step){    //每趟的排序部分。步长为step    //step is from a list for each loop,the last must be 1    int i, j;    for (i = 1 + step; i <= n; i++){        raw[0] = raw[i];        for (j = i - step; j>0 && raw[j]>raw[0]; j = j - step)//每次的步进单位都是step            raw[j + step] = raw[j];        raw[j + step] = raw[0];    }}void shellSort(int raw[], int n){    // this list should be careful set and must be end with 1    int step[3] = { 5, 3, 1 };//指定的增量序列    for (int i = 0; i<3; i++){        shellSort_basic(raw, n, step[i]);    }} void main(){	int a[9] = { 0, 3, 4, 8, 6, 7, 23, 21, 18 };	simpleInsertSort_Bin(a, 8);	dispList(a, 8);}
    

复杂度分析：

对于插入排序，其在理想情况下达到O(n)，在最坏情况下为O(n²)况

总结：

对于记录不多和基本有序情况，插入排序是最实惠的排序方法。