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

我們提供的服務(wù)有：做網(wǎng)站、成都網(wǎng)站設(shè)計(jì)、微信公眾號開發(fā)、網(wǎng)站優(yōu)化、網(wǎng)站認(rèn)證、巍山ssl等。為1000多家企事業(yè)單位解決了網(wǎng)站和推廣的問題。提供周到的售前咨詢和貼心的售后服務(wù)，是有科學(xué)管理、有技術(shù)的巍山網(wǎng)站制作公司

  一.插入排序

   算法思想

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

eg: 有序數(shù)組：1，3，5，6，7   現(xiàn)在待插入數(shù)據(jù)為2，那么他將會(huì)和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è)是為了待會(huì)兒更好的理解希爾排序。

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

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

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

 排序算法的穩(wěn)定性是指，經(jīng)過排序算法排序的相同元素的相對位置不會(huì)發(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<size)
	{
		if (child+1<size && a[child] < a[child + 1])
			++child;
		if (a[parent] < a[child])
		{
			swap(a[parent], a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
		
	}
}
void HeapSort(int* a,size_t size)
{
	assert(a);
	//建堆
	for (int i = (size - 2) / 2; i >= 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)然，本人能力有限，難免會(huì)有紕漏，希望大家可以指正。

網(wǎng)站題目：插入排序，希爾排序，堆排序
網(wǎng)頁路徑：http://chinadenli.net/article44/ggjiee.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站制作、域名注冊、軟件開發(fā)、面包屑導(dǎo)航、小程序開發(fā)、網(wǎng)站策劃

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)