成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

【算法】插入排序——希爾排序+直接插入排序

GitChat / 666人閱讀

希爾排序

在介紹希爾排序之前，先了解一下直接插入排序

一、直接插入排序

1. 單趟排序

x插入一個(gè)有序區(qū)間

這里end是指向數(shù)組最后一個(gè)元素

2. 直接插入排序

根據(jù)上面的單趟排序啟發(fā)

end是數(shù)組的最后一個(gè)元素，end之后的元素都是待排序

一個(gè)關(guān)鍵的判斷點(diǎn)，end和x比較大小

這里end < x

還需要再做改善

可以發(fā)現(xiàn)有兩個(gè)循環(huán)，一個(gè)循環(huán)時(shí)end倒著遍歷完之后，使得最開始的end結(jié)束的數(shù)組加入x后是一個(gè)有序數(shù)組，最后再返回這個(gè)新數(shù)組的最后一個(gè)元素所在位置

注意公共部分

end--；x = a[end + 1];

外面是一個(gè)for循環(huán)，從第二個(gè)到最后一個(gè)元素

for(i = 0; i < n - 1; i++){    }

代碼：

//插入排序void InsetSort(int* a, int n){	int end = 0;	int i = 0;	for (i = 0; i < n - 1; i++)	{		end = i;		int x = a[end + 1];		while (end >= 0)		{			if (a[end] > x)			{				a[end + 1] = a[end];				a[end] = x;							}			else			{				break;			}			end--;		}	}	}

時(shí)間復(fù)雜度O(N2)

測試：

int main(){	int a[4] = { 2, 6, 5, 3 };	InsetSort(a, 4);	//ShellSort(a, 4);	int i = 0;	for (i = 0; i < 4; i++)	{		printf("%d ", a[i]);	}	printf("/n");	return 0;}

二、希爾排序

希爾排序法又稱縮小增量法

希爾排序法的基本思想是：先選定一個(gè)整數(shù)，把待排序文件中所有記錄分成gap個(gè)組，所有距離為的記錄分在同一組內(nèi)，并對每一組內(nèi)的記錄進(jìn)行排序。然后，重復(fù)上述分組和排序的工作。當(dāng)?shù)竭_(dá)gap=1時(shí)，所有記錄在統(tǒng)一組內(nèi)排好序。

希爾排序是根據(jù)直接插入排序的基礎(chǔ)上，先進(jìn)行分組排序

以3個(gè)為一組進(jìn)行排序

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

每次排可以看作長度為gap的數(shù)組直接插入排序

一共有gap組，當(dāng)然并不是每組都是gap/n個(gè)元素，但當(dāng)數(shù)據(jù)相當(dāng)多的時(shí)候我們看作每個(gè)數(shù)組都有gap/n個(gè)元素

所以是 (1+2……+n/gap)gap

  • 如果gap = 1,則時(shí)間復(fù)雜度是O(n2)，相當(dāng)于直接插入排序
//希爾排序void ShellSort(int* a, int n){	int end = 0;	int i = 0;	int j = 0;	int gap = 6;	//預(yù)排序	for (j = 0; j < gap; j++)	{		//最后一個(gè)數(shù)一定是1		gap = gap / 2;		for (i = 0; i < n - gap; i++)		{			end = i;            //這里其實(shí)就是直接插入排序，而數(shù)組的每個(gè)元素間隔是gap			int x = a[end + gap];			while (end >= 0)			{				if (a[end] > x)				{					a[end + gap] = a[end];					a[end] = x;				}				else				{					break;				}				end -= gap;			}		}	}}

測試用例還是上面直接插入排序的例子

結(jié)果還是成功的

三、測試希爾排序和直接插入排序性能

//性能測試void TestOP(){	srand(time(0));    //以1000個(gè)數(shù)字為例	const int N = 10000;	int* a1 = (int*)malloc(sizeof(int) * N);	int* a2 = (int*)malloc(sizeof(int) * N);	for (int i = 0; i < N; ++i)	{		a1[i] = rand();		a2[i] = a1[i];	}    //這里clock是運(yùn)行到這里的時(shí)間	int begin1 = clock();	InsertSort(a1, N);	int end1 = clock();	int begin2 = clock();	ShellSort(a2, N);	int end2 = clock();    //end-begin為排序所用時(shí)間	printf("%d/n%d/n", end1 - begin1, end2 - begin2);}

可以看出希爾排序比直接排序快得多，但希爾排序因?yàn)間ap可以改變，目前沒有一個(gè)統(tǒng)一的時(shí)間復(fù)雜度，先按照時(shí)間復(fù)雜度為O(n1.3)來吧

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/123611.html

相關(guān)文章

  • JS中可能用得到的全部的排序算法

    本篇有7k+字, 系統(tǒng)梳理了js中常見的12種排序算法。除了基本排序算法，文章還包含了希爾排序、堆排序、桶排序等較為復(fù)雜的排序?qū)崿F(xiàn)，如果喜歡請點(diǎn)贊支持~謝謝. 原文: http://louiszhai.github.io/20... 導(dǎo)讀 排序算法可以稱得上是我的盲點(diǎn), 曾幾何時(shí)當(dāng)我知道Chrome的Array.prototype.sort使用了快速排序時(shí), 我的內(nèi)心是奔潰的(啥是快排, 我只知道...

    verano 評論0 收藏0

  • 基本算法學(xué)習(xí)(一)之希爾排序(JS)

    摘要：動(dòng)態(tài)定義間隔序列參考來源詳細(xì)介紹了十種算法大家可以去學(xué)習(xí)下以后大概會(huì)盡量每天更新一個(gè)算法學(xué)習(xí)吧溫故而知新 參考書:嚴(yán)蔚敏-數(shù)據(jù)結(jié)構(gòu) 希爾排序(Shells Sort) 希爾排序又稱縮小增量排序,歸屬于插入排序一類,簡單來說,和我們的插入排序比,它更快. 奇妙的記憶點(diǎn): 內(nèi)排序(內(nèi)存排序就夠了) 不穩(wěn)定(排序后原始順序無法保證) 希爾排序重點(diǎn)在于分割. 基本思想: 將整個(gè)待排序記錄序...

    cooxer 評論0 收藏0

  • Javascript算法——希爾排序

    摘要：常見的內(nèi)部排序算法有插入排序希爾排序選擇排序冒泡排序歸并排序快速排序堆排序基數(shù)排序等。這里主要介紹希爾排序。一圖勝千言算法介紹算法描述希爾排序，也稱遞減增量排序算法，是插入排序的一種更高效的改進(jìn)版本。但希爾排序是非穩(wěn)定排序算法。 常見的內(nèi)部排序算法有：插入排序、希爾排序、選擇排序、冒泡排序、歸并排序、快速排序、堆排序、基數(shù)排序等。這里主要介紹希爾排序。 一圖勝千言： showImg(h...

    lowett 評論0 收藏0

  • 希爾排序就這么簡單

    摘要：這時(shí)就用簡單插入排序?qū)?shù)列直至已序從直觀上看希爾排序就是把數(shù)列進(jìn)行分組不停使用插入排序，直至從宏觀上看起來有序，最后插入排序起來就容易了無須多次移位或交換。 一、希爾排序介紹 來源百度百科： 希爾排序(Shells Sort)是插入排序的一種又稱縮小增量排序（Diminishing Increment Sort），是直接插入排序算法的一種更高效的改進(jìn)版本。希爾排序是非穩(wěn)定排序算法。該方...

    paulli3 評論0 收藏0

發(fā)表評論

0條評論

最新活動(dòng)
閱讀需要支付1元查看
<