引自：http://hi.baidu.com/gsgaoshuang/item/17a8ed3c24d9b1ba134b14c2

學習算法的一個好網站

http://student.zjzk.cn/course_ware/data_structure/web/paixu/paixu8.2.2.1.htm

希爾排序（Shell Sort）又稱為縮小增量排序，輸入插入排序算法，是對直接排序算法的一種改進。本文介紹希爾排序算法。

??? 對于插入排序算法來說，如果原來的數據就是有序的，那么數據就不需要移動，而插入排序算法的效率主要消耗在數據的移動中。因此可知：如果數據的本身就是有序的或者本身基本有序，那么效率就會得到提高。

??? 希爾排序的基本思想是：將需要排序的序列劃分成為若干個較小的子序列，對子序列進行插入排序，通過則插入排序能夠使得原來序列成為基本有序。這樣通過對較小的序列進行插入排序，然后對基本有序的數列進行插入排序，能夠提高插入排序算法的效率。

??? 在希爾排序中首先解決的是子序列的選擇問題。對于子序列的構成不是簡單的分段，而是采取相隔某個增量的數據組成一個序列。一般的選擇原則是：去上一個增量的一般作為此次序列的劃分增量。首次選擇序列長度的一般為增量。

??? 先假如：數組的長度為10，數組元素為：25,19,6,58,34,10,7,98,160,0

??????? 整個希爾排序的算法過程如下如所示：

上圖是原始數據和第一次選擇的增量 d = 5。本次排序的結果如下圖：

?

?

上圖是第一次排序的結果，本次選擇增量為 d=2。 本次排序的結果如下圖：

當d=1 是進行最后一次排序，本次排序相當于冒泡排序的某一次循環。最終結果如下：

在實際使用過程中，帶排序的數據肯定不是只有十個，但是上述是希爾排序的思想。其實希爾排序只是插入排序的一種優化。

希爾排序的整個流程如下圖所示：假設帶排序的數據結構為整型數組 A[n] 數組長度為 n

?

C++實現希爾排序的代碼如下所示：

// ShellSort.cpp : Defines the entry point for the console application.

//

?

#include "stdafx.h"

#include <iostream>

?

using namespace std;

?

void Display(int array[],int length);

?

void ShellSort(int array[],int length);

?

int main(int argc, char* argv[])

{

???????? int arr[10] = {25,19,6,58,34,10,7,98,160,0};

???????? Display(arr,10);

?

???????? ShellSort(arr,10);

?

???????? Display(arr,10);

???????? system("pause");

???????? return 0;

}

?

//輸出數組

void Display(int array[],int length)

{

???????? for(int i =0;i<length;i++)

???????? {

?????????????????? cout<<array[i]<<", ";

???????? }

???????? cout<<endl;

}

?

//希爾排序算法的實現

void ShellSort(int array[],int length)

{

???????? int d = length/2;?? //設置希爾排序的增量

???????? int i ;

???????? int j;

???????? int temp;

???????? while(d>=1)

???????? {

?????????????????? for(i=d;i<length;i++)

?????????????????? {

??????????????????????????? temp=array[i];

??????????????????????????? j=i-d;

??????????????????????????? while(j>=0 && array[j]>temp)

??????????????????????????? {

???????????????????????????????????? array[j+d]=array[j];

???????????????????????????????????? j=j-d;

??????????????????????????? }

//不明白為何要-d，循環出來之后又+d，不是多此一舉 啊

??????????????????????????? array[j+d] = temp;

?????????????????? }

?????????????????? Display(array,10);

?????????????????? d= d/2;??? //縮小增量

???????? }

}

?

/*

希爾排序是對插入排序的一種改進。該算法思路和代碼都比較復雜。以上代碼在VC 6.0 中成功運行

*/

?

?

轉載于:https://www.cnblogs.com/fickleness/p/3339008.html

總結

以上是生活随笔為你收集整理的希尔排序-插入改进的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。