直接插入排序

 将每个关键词，按照顺序，依次插入到前面有序的序列中去。检索到第i个关键字，那么前面所有的关键字都是有序的，所以，把第i个关键字也在前面中按序插入即可。C++代码如下：

void simpleInsertSort(vector<int> &nums){
	for(int i = 1 ; i < length ; i++){
		int temp = nums[i];
		for(int j = i - 1; j >= 0 && nums[j] > temp; j--){
			nums[j+1] = nums[j];
		}
        nums[j+1] = temp;
	}
}

折半插入排序

 思想跟前面一样，都是将第i个关键字插入到前面有序的序列中，但是插入位置，前面是用的顺序查找，这里可以用二分搜索。

C++代码如下：

void binInsertSort(vector<int> &nums)
{
	for (int i = 1; i < nums.size(); i++)
	{
		int temp = nums[i];
		int left = 0 , right = i-1;
		while(left <= right){
			int mid = (left + right) / 2;
			if(nums[i] >= nums[mid]) left = mid + 1;
			else right = mid - 1; 
		}
		for(int j = i-1; j >= left ;j--){
			nums[j+1] = nums[j];
		}
		nums[left] = temp;
	}
}

希尔排序

 根据前面的直接插入来看，如果数据基本有序的话，那么效率是非常快的。所以，希尔排序的思想是，慢慢让序列变得有序。直到完全有序。如何慢慢让数组变得有序呢？答：我们用到一个变量d，作用是，将每隔d个元素单独当作一个数列进行简单插入排序。成倍的慢慢缩小d，值到d=0。C++代码如下：

void shellSort(vector<int> nums){
	for(int d = nums.size() / 2; d >= 1; d/=2){
		for(int m = 0 ;m < d; m++){
			for(int i = m; i < nums.size() ;i+=d){
				int temp = nums[i];
				int j = i-d;
				for(; j >= 0 && temp < nums[j]; j-=d){
					nums[j+d] = nums[j];
				}
				nums[j+d] = temp;
			}
		}
	}
}