常見的排序算法（一） 插入排序

  插入排序分為：直接插入排序，二分插入排序（又稱折半插入排序），鏈表插入排序，希爾排序（又稱縮小增量排序）。屬于穩(wěn)定排序的一種（通俗地講，就是兩個(gè)相等的數(shù)不會(huì)交換位置） 。

在這里我具體講直接插入排序和希爾排序。

直接排序插入

直接插入排序是由兩層嵌套循環(huán)組成的。外層循環(huán)標(biāo)識(shí)并決定待比較的數(shù)值。內(nèi)層循環(huán)為待比較數(shù)值確定其最終位置。直接插入排序是將待比較的數(shù)值與它的前一個(gè)數(shù)值進(jìn)行比較，所以外層循環(huán)是從第二個(gè)數(shù)值開始的。當(dāng)前一數(shù)值比待比較數(shù)值大的情況下繼續(xù)循環(huán)比較，直到找到比待比較數(shù)值小的并將待比較數(shù)值置入其后一位置，結(jié)束該次循環(huán)。

 基本思想

 待排序記錄 R1，R2，… ，Rn–1, Rn

 第一步：R1

 第二步：(R1 ), R2

 第三步：(R1 , R2), R3

 ……

 第 j 步：(R1，R2，… ，Rj–1), Rj

 ……

 第 n 步: (R1，R2，… ，Rn–1), Rn．

正如以上圖片所示，直接排序總是先使前面一段有序，然后依次往后，知道整個(gè)數(shù)組都有序。

void InserSort(int * a,size_t size)   //直接插入排序
{
	assert(a);
	for(int i = 1;i < size ; i++)
	{
		int tem = a[i];
		int end = i - 1;
		while( end >= 0 && a[end]>tem)
		{
			a[end+1] = a[end];
			--end;
		}
		a[end+1] = tem;
	}
}

希爾排序

希爾排序(Shell Sort)是插入排序的一種。也稱縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方法因DL．Shell于1959年提出而得名。

希爾排序是按照不同步長(zhǎng)對(duì)元素進(jìn)行插入排序，當(dāng)剛開始元素很無(wú)序的時(shí)候，步長(zhǎng)最大，所以插入排序的元素個(gè)數(shù)很少，速度很快；當(dāng)元素基本有序了，步長(zhǎng)很小，插入排序?qū)τ谟行虻男蛄行屎芨?。所以，希爾排序的時(shí)間復(fù)雜度會(huì)比o(n^2)好一些。

正如下圖

此處，我的步長(zhǎng)是以3為例，由上便可以看出，步長(zhǎng)包括了整個(gè)數(shù)組。

第一個(gè)是：2，9，8，1  --》1，2，8，9

第二個(gè)是：5，3，7    ——》 3，5，7

第三步是：4，6，1  -》  1，4，6

代碼如下

void ShellSort(int* a, size_t size)   //希爾排序
{
	assert(a);
	int gap = size / 3;

	while(gap > 1)
  {
	  gap = gap/3 + 1;  //gap一直變小，知道它為1；
	for(int i = 0;i < (size - gap);++i)
	{
		int end = i;
		int tem = a[end + gap];
		while( end >= 0 && a[end]>tem)
		{
			a[end+gap] = a[end];
			end -= gap;
		}
		a[end+gap] = tem;
	}
  }
}

希爾排序的特點(diǎn)是不需要大量的輔助空間，和歸并排序一樣容易實(shí)現(xiàn)。希爾排序是基于插入排序的一種算法， 在此算法基礎(chǔ)之上增加了一個(gè)新的特性，提高了效率。希爾排序沒有快速排序算法快 O(n(logn))，因此中等大小規(guī)模表現(xiàn)良好，對(duì)規(guī)模非常大的數(shù)據(jù)排序不是最優(yōu)選擇。但是比O( N^2 )復(fù)雜度的算法快得多。并且希爾排序非常容易實(shí)現(xiàn)，算法代碼短而簡(jiǎn)單。 此外，希爾算法在最壞的情況下和平均情況下執(zhí)行效率相差不是很多，與此同時(shí)快速排序在最壞的情況下執(zhí)行的效率會(huì)非常差。