1.直接插入排序

当插入第 i 个元素时,前面的数据已经排好序了,将后续的数据按大小插入到前面已经排好序的数组中,就是插入排序

特点

1.元素集合越接近有序,时间效率越高

2.时间复杂度O(N^2)

3.空间复杂度O(1)

//插入排序
void InsertSort(int* a, int length)
{
	for (int i = 0; i < length - 1; i++)
	{
		int end = i;//已经排好的数组的尾部
		int temp = a[end + 1];
		while (end >= 0)
		{
			if (temp < a[end])//小就向前移
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{

				break;
			}
		}
		a[end + 1] = temp;
	}
}

2.希尔排序

时间复杂度约为O(N ^ 1.3)

先进行预排序 -- 目标 : 接近有序

然后再进行插入排序 -- 目标 : 有序

预排序

设定间距(两个数的下标之差)为gap,将彼此间距为gap的数进行插入排序

gap越大,数据跳的越快,大的数据更快到前面的位置,但是越不有序

gap越小,越接近有序

gap = 1时,就是插入排序

eg.

进行希尔排序时可以进行多次预排序,每次gap / 2,并且要求gap > 1保证最后一次预排序gap = 1,即完成排序

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap /= 2;//进行多次预排序,gap > 1保证最后一次预排序gap = 1,即完成排序
		for (int j = 0; j < gap; ++j)
		{
			for (int i = j; i < n - gap; i += gap)
			{
				int end = i;//已经排好的数组的尾部
				int temp = a[end + gap];
				while (end >= 0)
				{
					if (temp < a[end])//小就向前移
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = temp;
			}
		}
	}
}

gap也可以取3,但是为了保证最后一次预排序时gap为1,还需要gap + 1

即

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap /= 3 + 1;//进行多次预排序,gap > 1保证最后一次预排序gap = 1,即完成排序
		for (int j = 0; j < gap; ++j)
		{
			for (int i = j; i < n - gap; i += gap)
			{
				int end = i;//已经排好的数组的尾部
				int temp = a[end + gap];
				while (end >= 0)
				{
					if (temp < a[end])//小就向前移
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = temp;
			}
		}
	}
}