【算法】直接插入排序、折半插入排序、希尔排序

1 直接插入排序

时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定

元素集合越接近有序，直接插入排序算法的时间效率越高

1.1直接插入排序思想

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

1.2直接插入排序代码实现

void InsertSort(int* a, int n)//直接插入排序:	时间复杂度:O(n*n)	空间复杂度:O(1)
{
	assert(a);

	for (int i = 1; i < n; i++)//总共插入n-1次
	{
		int temp = a[i];//将最后一个数保存下来
		int point = i-1;//从倒数第二个数依次往前遍历

		while (point >= 0)//单趟把末尾的数插入到正确的位置
		{
			if (temp < a[point])//把大的数后移(为了保有稳定性，相等的数不后移)
			{
				a[point + 1] = a[point];
				point--;
			}
			else//因为前面已经排好序了，小于当前的就肯定小于前面的，直接break
			{
				break;
			}
		}
		a[point + 1] = temp;//把数插入到对应的位置
	}
}

2 折半插入排序

时间复杂度：O(N^2)
空间复杂度：O(1)
稳定性：稳定

此算法改变了比较元素的次数，比较的时间复杂度约为O(nlogn)，但并未改变元素移动的次数，所以总体来看折半插入排序的时间复杂度仍然是O(n*n)

2.1折半插入排序思想

折半插入排序是直接插入排序的优化，在进行第n个数的插入时，对前面0~n-1个数进行二分查找，找到比第n个数小的数的下标，随后进行后移操作。

2.2折半插入排序代码实现

void InsertSort_Binary(int* a, int n)//折半插入排序:	时间复杂度:O(n*n)	空间复杂度:O(1)
{
	assert(a);

	for (int i = 1; i < n; i++)//总共插入n-1次
	{
		int temp = a[i];//将最后一个数保存下来
		int left = 0;
		int right = i - 1;
		int mid;

		while (left<=right)//单次找到小于temp的值的位置
		{
			mid = (left + right) / 2;
			if (temp >= a[mid])
			{
				left = mid + 1;
			}
			else
			{
				right = mid - 1;
			}
		}

		for (int j = i - 1; j >= left; j--)//把此位置及其之后全部后移1位
		{
			a[j + 1] = a[j];
		}
		a[left] = temp;

	}
}

3 希尔排序

时间复杂度：O(n^1.3)——O(n*n)
空间复杂度：O(1)
稳定性：不稳定

《数据结构(C语言版)》— 严蔚敏

《数据结构-用面相对象方法与C++描述》— 殷人昆

3.1希尔排序思想

由前面我们知道，元素集合越接近有序，直接插入排序算法的时间效率越高。所以我们先对数组进行预排序。

先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

3.2希尔排序代码实现

void ShellSort(int* a, int n)//希尔排序:	时间复杂度:O(n^1.3)-O(n^2)	
{
	int gap = n; 

	while (gap > 1)//gap>1时相当于预排序
	{
		gap = gap / 3 + 1;//+1保证了最后一次gap一定是1 

		for (int i = gap; i < n ; i++)//每一轮走(n-gap)次 
		{
			int temp = a[i];//将最后一个数保存下来(每组的最后一个)
			int point = i - gap;//从倒数第二个数依次往前遍历(每组的倒数第二个)
			while (point >= 0)//单趟把末尾的数插入到正确的位置
			{
				if (temp < a[point])
				{
					a[point+gap] = a[point];
					point -= gap;
				}
				else
				{
					break;
				}
			}
			a[point+gap] = temp;
		}
	}
}