数据结构-排序算法

插入排序的思想：把待排序的数按值的大小插入到一个有序的序列中。

直接插入排序动态图

void InsertSort(int* a, int n)
{
	assert(a);
	
	for (int i = 0; i < n - 1; ++i)
	{
		// 将x插入[0, end]有序区间
		int end = i;
		int x = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > x)
			{
				a[end + 1] = a[end];
				--end;
			}
			else
			{
				break;
			}
		}
		//break出来的情况有2种
		//1x比所有的值都小，不满足while条件
		//2x比end小break出来
		a[end + 1] = x;
	}
}

1.元素集合越接近有序，直接插入排序算法的时间效率越高
2.时间复杂度：O(N^2)
3.空间复杂度：O（1），是一种稳定的排序算法

希尔排序思想：分组预排让数组接近有序再直接插入排序
ShellSort动图

void ShellSort(int* a, int n)
{
	// 多次预排序(gap > 1) 
	//直接插入 (gap == 1)
	int gap = n;
	while (gap > 1)
	{
		//gap = gap / 2;//有点小快
		gap = gap / 3 + 1;//保证最后一次是1；

		// 多组一起来
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int x = a[end + gap];
			while (end >= 0)
			{
				if (a[end] > x)
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
				{
					break;
				}
			}

			a[end + gap] = x;
		}
	}
}

1. gap>1都是预排序，目的是让数组更接近有序。当gap==1时，数据接近有序。
2. 时间复杂度：最好O（N）；最坏F（N，gap）=（1+2+3+……N/gap）*gap //N/gap是分gap组后一组大概有N/gap个元素。 平均0（N^1.3）
3. gap越大预排越快，预排后不接近有序。
4. gap越小预排越慢，预排后越接近有序。