[数据结构与算法]插入排序--直接插入、折半插入、希尔排序

?

//1、直接插入排序
vector<int> insertSort(vector<int>& nums)
{
	int len = nums.size();		
	//假定第0个数有序，从第1个数开始插入
	for (int j = 1; j < len; j++)
	{
		int temp = nums[j];	
		int i = j;           // [0,1,2,...j-1, j ,j+1,len-1]  temp = j
		//找插入点           //  [0,1,2,...j-1,   ,j+1,len-1]        
                            //            i-1  i
		while (temp > nums[i-1])
		{			
			nums[i] = nums[i-1];//后移	
			i--; // 继续比较下一个数

			//注意i不能出界
			if (i == 0) 
			{
				break;
			}
		}		
		nums[i] = temp;		
	}
	return nums;	
}

// 2、折半插入排序
vector<int> binaryInsertSort(vector<int>& nums)
{	
	int len = nums.size();
	//假定第0个数有序，从第1个数开始插入
	for (int j = 1; j < len; j++)
	{
		int temp = nums[j];	  // [0,1,2,...,j-1,j,j+1,...,len-1]		   
		int left = 0;         //取出j插入，则二分查找区间[0,j-1]
		int right = j - 1;
		while (left <= right)//找插入点
		{
			int mid = (left + right) / 2;
			if (temp > nums[mid]) //左半部分查找
			{
				right = mid - 1;
			}
			else  //右半部分
			{
				left = mid + 1;
			}			
		}
		// 找到插入点后，插入点left到j-1中间的元素整块后移
		for (int k = j - 1; k >= left; k--)
		{
			nums[k+1] = nums[k];
		}
		nums[left] = temp; // 插入		
	}
	return nums;
}

//3 希尔排序
vector<int> shellSort(vector<int>& nums)
{	  
	int len = nums.size()		;	
	//初始gap=len/2 
   // 每次gap/2,... gap=1(将所有元素排序),gap= 0结束
	for (int gap = len/2; gap > 0; gap /= 2)  
	{	
		//直接插入排序 逆序		
		for (int j = gap; j < len; j++)
		{		
			int temp = nums[j]; //取出待插入的数				
			int i = j;  //每个小组内,插入点的相对查找区间[0,i] 			
			//比前一个元素大,继续找插入点,比较下一个元素i-gap
			for (i; i >= gap  && temp > nums[i - gap]; i -= gap) 
			{
				nums[i] = nums[i - gap]; // 后移	
			}
			nums[i] = temp;//插入		
		}
	}
	return nums;
}