void InsertSort(int* arr, int len)
{
	//assert arr!=NULL
	for (int i = 1; i < len; i++)//一共跑了多少趟  //01234   12345  
	{
		int tmp = arr[i];//待插入的值  
		//j 指向 這一趟開(kāi)始的時(shí)候的已排序好的隊(duì)列中最后一個(gè)值的下標(biāo)
		int j;
		for (j = i - 1; j >= 0; j--)//這里控制待插入的值和 已排序隊(duì)列的挨著比較（從右向左比較）
		{
			if (arr[j] <= tmp)
			{
				break;//這時(shí)應(yīng)該停下來(lái)
			}
			else
			{
				arr[j + 1] = arr[j];
			}
		}
		arr[j + 1] = tmp;
	}
}

1.5直接插入排序性能分析

時(shí)間復(fù)雜度：

（1）順序排序時(shí)，只需比較(n-1)次，插入排序時(shí)間復(fù)雜度為O(n)；

（2）逆序排序時(shí)，需比較n(n-1)/2次，插入排序時(shí)間復(fù)雜度為O(n^2)；

（3）當(dāng)原始序列雜亂無(wú)序時(shí)，平均時(shí)間復(fù)雜度為O(n^2)。

空間復(fù)雜度：

插入排序過(guò)程中，需要一個(gè)臨時(shí)變量temp存儲(chǔ)待排序元素，因此空間復(fù)雜度為O(1)。

算法穩(wěn)定性：

插入排序是一種穩(wěn)定的排序算法。

二.希爾排序

2.1希爾排序引入

希爾排序其實(shí)就是對(duì)直接插入排序的優(yōu)化，在第一部分我們說(shuō)過(guò)==(1)直接插入排序數(shù)據(jù)越有序，插入的效率就越高；(2)記錄數(shù)比較少時(shí)，直接插入的優(yōu)勢(shì)也很明顯。==希爾排序就是根據(jù)這兩個(gè)特點(diǎn)進(jìn)行的優(yōu)化。

2.2希爾排序的核心思想與算法分析

核心思想：通過(guò)一個(gè)不斷縮小的增量序列，對(duì)無(wú)序序列反復(fù)的進(jìn)行拆分并且對(duì)拆分后的序列使用插入排序的。

算法分析：

先將整個(gè)待排元素序列分割成若干個(gè)子序列（由相隔某個(gè)“增量”的元素組成的）；
分別進(jìn)行直接插入排序，然后依次縮減增量再進(jìn)行排序；
待整個(gè)序列中的元素基本有序（增量足夠小）時(shí)，再對(duì)全體元素進(jìn)行一次直接插入排序；
完成排序。

2.3實(shí)例說(shuō)明

以12，2，9，8，5，88，99，10，7，17，77，66，89，10，21為例，排序過(guò)程如下：

這里相同顏色的線相同的分組
每次增量取上一次的一半（向下取整）
注意：最后一個(gè)增量值必須等于1才可以

2.4希爾排序代碼實(shí)現(xiàn)

代碼如下：

void Shell(int arr[], int len, int gap)//一趟希爾排序
{
	for (int i = gap; i < len; i++)//i++  不是i=i+gap;
	{
		int tmp = arr[i];//待插入的值  
		//j 指向 這一趟開(kāi)始的時(shí)候的已排序好的隊(duì)列中最后一個(gè)值的下標(biāo)
		int j;
		for (j = i - gap; j >= 0; j = j - gap)//這里控制待插入的值和 已排序隊(duì)列的挨著比較（從右向左比較）
		{
			if (arr[j] <= tmp)
			{
				break;//這時(shí)應(yīng)該停下來(lái)
			}
			else
			{
				arr[j + gap] = arr[j];
			}
		}
		arr[j + gap] = tmp;
	}
}
void ShellSort(int arr[], int len)
{
	int gap[] = { 5, 3, 1 };//
	int gap_len = sizeof(gap) / sizeof(gap[0]);
	for (int i = 0; i < gap_len; i++)
	{
		Shell(arr, len, gap[i]);
	}
}