数据结构与算法_排序算法_插入排序和希尔排序

插入排序

如果数据趋于有序，那么插入排序是所有排序算法中，效率最高的排序算法！
思想：假设第一个元素是已经排好序的；从第二趟开始依次从未排序的数据中选出一个，插入到已经排好序的数列中。从有序数列最后一个元素开始比较，如果当前待插入元素大于有序数列中的数据时候，就插入到被比较元素的后边，后边的元素依次向后移动。
在基础排序中，插入排序 > 冒泡排序&选择排序 不仅仅没有交换而且比较的次数少！
特点：从第二个元素开始，把前面的元素序列当作已经有序的，然后找合适的位置插入。
优点：插入排序是普通排序里面效率最高的排序算法，而且在数据越趋于有序的情况下，插入排序的效率是最高的。

// 插入排序
void InsertSort(int arr[], int size)
{
	for (int i = 1; i < size; i++)  // i指向无序序列中的首元素 
	{
		int val = arr[i];  // val
		int j = i - 1;
		for (; j >= 0; j--)  // j指向了有序数列最后一个元素，每次比较实际上有序数列都多出一个位置
		{						// 这个for作用是找出待插入元素的位置，同时将待插入位置空出来
			if (arr[j] <= val)
			{
				break;
			}
			arr[j + 1] = arr[j];// j + 1 表示当前比较元素的后边一个元素，也就是要插入val的位置
		}
		arr[j + 1] = val;
	}
}

希尔排序

可以看成是插入排序的改进版；在写希尔排序时候，先写出插入排序；然后再改成希尔排序，将插入排序中添加一个循环。

void ShellSort(int arr[], int size)
{
	for (int gap = size / 2; gap > 0; gap /= 2)
	{
		for (int i = gap; i < size; i++)
		{
			int val = arr[i];  // i 仍然指向无序数列首元素
			int j = i - gap;     // j 仍然指向有序元素的最后一个位置
			for (; j >= 0; j -= gap)
			{
				if (arr[j] <= val)   // 有序数列中元素从后向前和val进行比较
				{
					break;
				}
				arr[j + gap] = arr[j];
			}
			arr[j + gap] = val;
		}
	}

}