這篇文章主要為大家展示了C++如何實現希爾排序，內容簡而易懂，希望大家可以學習一下，學習完之后肯定會有收獲的，下面讓小編帶大家一起來看看吧。
一、思路：
希爾排序:又稱縮小增量排序，是一種改進的插入排序算法，是不穩定的。
設排序元素序列有n個元素，首先取一個整數gap<n作為間隔，將全部元素分為gap個子序列，所有距離為gap的元素放在同一個子序列中，在每一個子序列中分別施行直接插入排序。然后縮小間隔gap，重復上述的子序列和排序工作。
二、實現程序：
#include <iostream>
using namespace std;
const int maxSize = 20;
// 希爾排序：每次減小1/3，直到d=1;
// 因為前面增量比較大，間隔比較，減少比較的次數，已經將部分排好序，
// 后面雖然d越來越小，但是因為前面已經排好序，所以，后面插入需要比
// 較的次數減少。
template <class T>
void ShellSort(T arr[], const int left, const int right) {
int i, j, gap, temp; // gap為增量
gap = right - left + 1; // 增量的初始值
do{ // 直到增量值為1
gap = gap / 3 + 1; // 求下一增量值
for(i = left + gap; i <= right; i++) {
if(arr[i] < arr[i-gap]) {
temp = arr[i];
j = i - gap;
do {
arr[j+gap] = arr[j]; // 后移元素
j = j - gap; // 再比較前一元素
}while(j >= left && temp < arr[j]);
arr[j+gap] = temp; // 回填
}
} // for
}while(gap > 1);
} // ShellSort
int main(int argc, const char * argv[]) {
int i, n, arr[maxSize];
cout << "請輸入要排序的數的個數：";
cin >> n;
cout << "請輸入要排序的數：";
for(i = 0; i < n; i++)
cin >> arr[i];
cout << "排序前：" << endl;
for(i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
ShellSort(arr, 0, n-1);
cout << "排序后：" << endl;
for(i = 0; i < n; i++)
cout << arr[i] << " ";
cout << endl;
return 0;
}測試結果：
以上就是關于C++如何實現希爾排序的內容，如果你們有學習到知識或者技能，可以把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
