C++希爾排序原理+代碼實現(xiàn)（詳細注釋理解）-創(chuàng)新互聯(lián)

一、概念及其介紹

希爾排序和插入排序很相似，有點像插入排序的升級版本。

為長洲等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計制作服務(wù)，及長洲網(wǎng)站建設(shè)行業(yè)解決方案。主營業(yè)務(wù)為網(wǎng)站設(shè)計、成都網(wǎng)站建設(shè)、長洲網(wǎng)站設(shè)計，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠的服務(wù)。我們深信只要達到每一位用戶的要求，就會得到認可，從而選擇與我們長期合作。這樣，我們也可以走得更遠！

希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序，它是簡單插入排序經(jīng)過改進之后的一個更高效的版本，也稱為縮小增量排序，同時該算法是沖破O(n2）的第一批算法之一。

希爾排序也是一種插入排序算法，只不過在插入排序上突破了結(jié)界，達到了另一種頂峰的存在，這種頂峰使得時間復雜度變成 O(n^(1.3-2))

希爾排序是通過分組+插入

二、復雜度

希爾排序時間復雜度是 O(n^(1.3-2))，空間復雜度為常數(shù)階 O(1)。希爾排序沒有時間復雜度為 O(n(logn)) 的快速排序算法快 ，因此對中等大小規(guī)模表現(xiàn)良好，但對規(guī)模非常大的數(shù)據(jù)排序不是最優(yōu)選擇，總之比一般 O(n^2 ) 復雜度的算法快得多。

三、過程演示

希爾排序目的為了加快速度改進了插入排序，交換不相鄰的元素對數(shù)組的局部進行排序，并最終用插入排序?qū)⒕植坑行虻臄?shù)組排序。

在此我們選擇增量 step = length / 2，縮小增量以 step = step / 2 的方式，用序列 {n/2,(n/2)/2…1} 來表示。

下面借用菜鳥教程的圖

（1）初始增量第一趟 step = length / 2 = 4

（2）第二趟，增量縮小為 2：step = step / 2

（3）第三趟，增量縮小為 1：step = step / 2。得到最終排序結(jié)果

代碼實現(xiàn)

void shell_sort(int a[], int n) {//首先枚舉增量 
	for(int step = n / 2; step >= 1; step /= 2){//在當前增量下，查找當前元素a[i]應(yīng)該被插入的位置
		for(int i = step; i< n; i++) {	int temp = a[i];//記錄當前元素的值 
			int j;//j代表：以當前步長分割的數(shù)組的下標，所以不是"j - 1"，而是"j - 增量"也就是"j - step"
			
			//當前元素與前一個增量的元素作比較，如果小于前一個，那么就向后移動元素 
			for(j = i; j - step >= 0 && temp< a[j - step]; j -= step) {		a[j] = a[j - step];
			}
			//循環(huán)退出之后，也就是找到了當前元素應(yīng)該放入的位置
			//把比較元素放到當前下標，相當于插入 
			a[j] = temp;
		}
	}
}

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站題目：C++希爾排序原理+代碼實現(xiàn)（詳細注釋理解）-創(chuàng)新互聯(lián)
分享地址：http://www.jiaotiyi.com/article/cogcij.html