插入排序与希尔排序

插入排序

将一元素插入到已排序完毕的数组中

可以将无序数组的第一个元素看作 只有一个元素的有序数组

后将数组中的元素一一插入到有序数组中的合适位置

所有元素被插入到有序数组中时，便已将此数组置为有序

动图演示

 

代码逻辑如下：

以升序为例

将插入的元素通过 tmp保存

假设 此时有序数组中有 i+1 个元素

将有序数组的最后元素（最大的元素）的下标，记为end

通过end遍历数组，寻出元素插入的合适位置 

		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;

将 tmp 与 a[end]进行比较，

当 a[end] > tmp 时，将 a[end]后移一位，后 end--

接着与tmp进行比较 ，直至找到合适位置

合适位置的两种情况

1. tmp > end

2.tmp小于数组中所有元素

找到合适位置后，循环便结束，将数据存入合适位置 （end + 1）

此为一个元素插入到有序数组中的步骤

对 n 个元素的数组进行插入排序可以理解为

含有一个元素的有序数组中插入 n-1个元素

转化成代码即为

// 插入排序
void InsertSort(int* a, int n)
{
	int i = 0;
	for(i=0;i<n-1;i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

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

希尔排序

希尔排序是插入排序的进阶排序，大大优化了插入排序的算法效率

基本思想与代码分析实现

假设数组中共有N个元素

取一小于N的正整数gap

将数组中相距为gap的元素分为一组

注意：各组间元素并不重合，在取元素时，第一组以下标为0的元素为第一个元素

                                                                     第二种以下标为1的元素为第二个元素

                                                                                                                          ......

将各组元素进行插入排序

        int j = 0;
        //对每组元素进行排序
		for (j = 0; j < gap; j++)
		{
			int i = 0;
            //对一组元素进行排序
			for (i = j; i < n - gap; i += gap)
			{
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (a[end] > tmp)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}

后将 gap减小重复上述步骤

以升序为例子

当 gap > 1时

此过程称之为预排序，为了方便更好更快的进行插入排序

gap越大，大的元素就更快到后方，小的元素就更快到前方

gap越小，数据便越接近有序

当gap == 1时

便为插入排序

综上所述

void ShellSort(int* a, int n)
{
	//按照gap 进行插排
	int gap = n;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		int j = 0;
		for (j = 0; j < gap; j++)
		{
			int i = j;
			for (i = 0; i < n - gap; i += gap)
			{
				int end = i;
				int tmp = a[end + gap];
				while (end >= 0)
				{
					if (a[end] > tmp)
					{
						a[end + gap] = a[end];
						end -= gap;
					}
					else
					{
						break;
					}
				}
				a[end + gap] = tmp;
			}
		}
	}

}