? ? ? ? ? ? ? ? ? ? ? ? ?

目錄

一. 直接插入排序

?基本思想

?代碼實現(xiàn)

?時間和空間復(fù)雜度

?穩(wěn)定性

二. 希爾排序

?基本思想

?代碼實現(xiàn)?? ?

?時間和空間復(fù)雜度

?穩(wěn)定性

一. 直接插入排序

? ? ??基本思想

? ? ? ? ? ?把待排序的記錄按其關(guān)鍵碼值的大小依次插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列。

? ? ? 圖解：

? ? ?

? ? ? ?代碼實現(xiàn)

? ? ??

//直接插入排序
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1 ; i++)
	{
		int j = i;
		int tmp = a[j + 1]; //保存待排序元素
		while (j >= 0)
		{
			if (tmp < a[j])  //將a[j+1]插入有序子表
				a[j + 1] = a[j];  //記錄后移位置
			else
				break;
			j--;
		}
		a[j + 1] = tmp;  //插入到正確位置
	}
}

?時間和空間復(fù)雜度

? ? ? 時間復(fù)雜度：o(n^2)

? ? ? 空間復(fù)雜度：o(1)

? ??? ? 平均時間復(fù)雜度也是?O(n^2)，空間復(fù)雜度為常數(shù)階?O(1)，具體時間復(fù)雜度和數(shù)組的有序性也是有關(guān)聯(lián)的。

? ? ? ? 當(dāng)待排序數(shù)組是有序時，是最優(yōu)的情況，只需當(dāng)前數(shù)跟前一個數(shù)比較一下就可以了，這時一共需要比較?N-1?次，時間復(fù)雜度為?O(N)。最壞的情況是待排序數(shù)組是逆序的，此時需要比較次數(shù)最多，最壞的情況是?O(n^2)。

說明：元素集合越接近有序，直接插入排序算法的時間效率越高

穩(wěn)定性

? ? ? ?一種排序?qū)嵤┣昂?，關(guān)鍵碼相同的任意兩個對象其前后次序沒有發(fā)生變化，就說明這個排序是穩(wěn)定的，否則是不穩(wěn)定的。

直接插入排序：穩(wěn)定排序

二. 希爾排序

? ? ? ?希爾排序又稱縮小增量排序，也是一種插入排序類的方法，此種方法是在直接插入排序的基礎(chǔ)上改進(jìn)的，在時間效率上有了很大的提高。

? ? ?基本思想

? ? ? ? 以增量為步長劃分子序列，即同一子序列中的邏輯上相鄰元素，其下標(biāo)步長等于增量。對每一個子序列進(jìn)行直接插入排序。不斷縮小增量，當(dāng)增量為1時，所有數(shù)組元素都在一個子序列中排好序。

? ?圖示：

? ? ? ? ? 選擇增量?gap = n / 2，縮小增量以?gap = gap / 2?的方式

? ? ? ? 注意：增量序列的最后一個增量值必須為1才行

? ? ? ?

? ? ? ? ?

? ???代碼實現(xiàn)?? ?

? ? ? ? ?代碼一： 多組并排方式

? ? ? ?圖解

? ? ? ? ?

//希爾排序
void ShellSort(int* a, int n)
{
	int gap = n;  //增量初始值
	while (gap > 1)
	{
		gap = gap / 2; //縮小增量
		for (int i = 0; i < n - gap; i++) //對每一組進(jìn)行直接插入排序
		{
			int j = i;
			int tmp = a[j + gap];
			while (j >= 0)
			{
				if (tmp < a[j])
				{
					a[j + gap] = a[j];
					j -= gap;
				}
				else
					break;
			}
			a[j + gap] = tmp;
		}
	}	
}

? ? ???代碼二： 一組走完，再走下一組

void ShellSort(int* a, int n)
{
	int gap = n / 2;  //增量初始值
	//gap組進(jìn)行插入排序
	for (int j = 0; j < gap; j++)
	{
		for (int i = j; i < n - gap; i += gap) //對一組進(jìn)行直接插入排序
		{
			int end = i;
			int tmp = a[end + gap];
			while (end >= 0)
			{
				if (tmp < a[end])
				{
					a[end + gap] = a[end];
					end -= gap;
				}
				else
					break;
			}
			a[end + gap] = tmp;
		}
	}
}

說明：代碼一是對代碼二的改進(jìn)，并沒有提升效率，兩種方式在效率及性能上沒有本質(zhì)的區(qū)別。

時間和空間復(fù)雜度

? ? ? ?時間復(fù)雜度：?O(n^1.3)

? ? ? ?空間復(fù)雜度： O(1)

說明：1. 希爾排序是對直接插入排序的優(yōu)化。
? ? ? ? ? ?2. 當(dāng)gap > 1時都是預(yù)排序，目的是讓數(shù)組更接近于有序。當(dāng)gap == 1時，數(shù)組已經(jīng)接近有? ? ? ? ? ? ? ? ?序的了，這樣就會很快。這樣整體而言，可以達(dá)到優(yōu)化的效果。
? ? ? ? ? ?3. 希爾排序的時間復(fù)雜度不好計算，因為gap的取值方法很多，導(dǎo)致很難去計算，因此在一? ? ? ? ? ? ? ? 些書中給出的希爾排序的時間復(fù)雜度都不固定

穩(wěn)定性

? 希爾排序：不穩(wěn)定排序。預(yù)排序時相同的數(shù)據(jù)可能分在不同的組

? ??文章來源地址http://www.zghlxwxcb.cn/news/detail-725724.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】排序(1) ——插入排序 & 希爾排序的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！