C++希爾排序

開發(fā)工具與關(guān)鍵技術(shù)：C++、VisualStudio 作者：何任賢 撰寫時(shí)間：2019年08月01日 希爾排序和插入排序差不多，插入排序在元素序列基本有序的情況下和元素個(gè)數(shù)比較小 的時(shí)候，只有這樣情況下插入排序的效率才會(huì)高，但是這兩個(gè)條件比較苛刻，那么希爾排序就是根據(jù)這兩個(gè)條件來升級(jí)插入排序，希爾排序就是插入排序的升級(jí)版，希爾排序是同過分組的方法來解決的，分組后再對(duì)每一組進(jìn)行插入排序，這樣就可以提高排序效率。 那么希爾排序的規(guī)則是希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰好被分成一組時(shí)，算法便終止。 那么希爾排序是怎樣分組的呢？下面是希爾排序的代碼和一些排序結(jié)果。

#include
using namespace std;
//希爾排序
void shellSort(int *array, int len)
{
// 步長(zhǎng)
int gap = len;
while (gap > 1)
{
// 步長(zhǎng)遞減公式
gap = gap / 3 + 1;
// 分組, 對(duì)每一組, 進(jìn)行插入排序
for (int i = 0; i < gap; ++i)
{
int tmp; // 基準(zhǔn)數(shù)
int index; // 坑的位置
// 插入排序
// 無序序列
for (int j = i + gap; j < len; j += gap)
{
tmp = array[j];
index = j;
// 有序序列(從后往前遍歷)
for (int k = j - gap; k >= 0; k -= gap)
{
if (tmp < array[k])
{
// 后移
array[k + gap] = array[k];
// 位置
index = k;
}
else
{
break;
}
}
// 填坑
array[index] = tmp;
}
}
}
}
void main()
{
int i;
//定義整型數(shù)組
int array[] = { 12, 5, 33, 6, 10 };
//計(jì)算數(shù)組長(zhǎng)度
int len = sizeof(array) / sizeof(int);
//遍歷數(shù)組
cout << "待排序數(shù)組序列: ";
for (int i = 0; i < len; ++i)
{
cout << array[i] << " ";
}
cout << “\n”;
//排序
shellSort(array, len);
//遍歷
cout << "希爾排序之后的序列: ";
for (i = 0; i < len; ++i)
{
cout << array[i] << " ";
}
cout << “\n”;
}

總結(jié)

以上是生活随笔為你收集整理的C++希尔排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。