本文將介紹三種排序算法--插入排序，希爾排序，堆排序。本文所有例子都是使用升序

創(chuàng)新互聯(lián)主要從事成都網(wǎng)站建設(shè)、成都做網(wǎng)站、網(wǎng)頁設(shè)計(jì)、企業(yè)做網(wǎng)站、公司建網(wǎng)站等業(yè)務(wù)。立足成都服務(wù)天元,十余年網(wǎng)站建設(shè)經(jīng)驗(yàn),價(jià)格優(yōu)惠、服務(wù)專業(yè),歡迎來電咨詢建站服務(wù):18980820575

 一.插入排序

  算法思想

  維護(hù)一個(gè)有序數(shù)組，將要插入的數(shù)據(jù)與有序數(shù)組自最后一個(gè)元素直到合適位置的數(shù)一一比較。

eg: 有序數(shù)組：1，3，5，6，7  現(xiàn)在待插入數(shù)據(jù)為2，那么他將會和7，6，5，3，依次作比較，當(dāng)帶插入數(shù)據(jù)小于有序數(shù)組最后的元素大小，則將該元素后移，直到待插入元素找到合適位置為止。

  代碼實(shí)現(xiàn)

void InsertSort(int* a, int size)
{
	assert(a);
	for (int i = 0; i < size - 1; ++i)
	{
		int end = i;                                 //標(biāo)識有序數(shù)組的最后一位
		int tmp = a[end + 1];
		while (end >= 0 && tmp < a[end])
		{
			a[end + 1] = a[end];                     //待插入數(shù)據(jù)比有序數(shù)組的最后一個(gè)數(shù)小，將有序數(shù)組最后一位向后移位
			--end;
		}
		a[end + 1] = tmp;
	}
}

  總結(jié)

  1.插入排序可以認(rèn)為是間距為1的插入算法，說這個(gè)是為了待會兒更好的理解希爾排序。

   2.插入排序的時(shí)間復(fù)雜度為O(n^2);

  3.插入排序的空間復(fù)雜度為O(1);

  4.具有穩(wěn)定性

 排序算法的穩(wěn)定性是指，經(jīng)過排序算法排序的相同元素的相對位置不會發(fā)生改變。

 二.希爾排序

  算法思想

  希爾排序可以認(rèn)為是插入排序的增強(qiáng)版，因?yàn)?，他加入了一個(gè)預(yù)排的過程，即在實(shí)現(xiàn)間距為1的插入算法之前，他已經(jīng)預(yù)先將間距為gap（gap一直減減直到>0）的數(shù)組排列過了。所以，當(dāng)進(jìn)行g(shù)ap = 1的插入排序之前使得待排序數(shù)組已經(jīng)高度接近有序，使得這次進(jìn)行的gap = 1的排序的時(shí)間復(fù)雜度，可以小于O(N^2)(gap = 1的插入排序，最好情況的時(shí)間復(fù)雜度為O(1)，前面的預(yù)排過程正是出于這個(gè)目的)。

  代碼實(shí)現(xiàn)

//希爾排序
void ShellSort(int* a,size_t size)
{
	assert(a);
	int gap = size / 2;
	while (gap > 0)
	{
		for (int i = 0; i < size - gap; ++i)
		{
			int end = i;                                
			int tmp = a[end + gap];
			while (end >= 0 && tmp < a[end])
			{
				a[end + gap] = a[end];                    
				end -= gap;
			}
			a[end + gap] = tmp;
		}
		--gap;
	}
}

 總結(jié)

 上圖為gap = 5 的時(shí)候的預(yù)排效果圖

 1.希爾排序預(yù)排的思想和插入排序的思想是一致的，只是，他把原數(shù)組分成不同的區(qū)間。

 2.希爾排序的時(shí)間復(fù)雜度為O(N^2),空間復(fù)雜度為O(1);

 3，具有不穩(wěn)定性

 三.堆排序

 算法思想

代碼實(shí)現(xiàn)

void AdjustDown(int* a, size_t size, int parent)
{
	assert(a);
	int child = parent * 2 + 1;
	while (child= 0; --i)  //從第一個(gè)非葉子節(jié)點(diǎn)開始調(diào)
	{
		AdjustDown(a, size, i);
	}
	for (size_t i = 0; i < size; ++i)
	{
		swap(a[0], a[size - 1 - i]);
		AdjustDown(a, size - i - 1, 0);
	}
}

 總結(jié)

 1.時(shí)間復(fù)雜度為O(N*lgN),空間復(fù)雜度為O(1);

 2.具有不穩(wěn)定性

 以上就是本人在學(xué)習(xí)過程中的一些經(jīng)驗(yàn)總結(jié)。當(dāng)然，本人能力有限，難免會有紕漏，希望大家可以指正。

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

網(wǎng)站標(biāo)題：插入排序，希爾排序，堆排序-創(chuàng)新互聯(lián)
標(biāo)題路徑：http://weahome.cn/article/cooceg.html