C++實現(xiàn)希爾排序（ShellSort）
更新時間：2020年04月24日 17:00:06 作者：ChanJose
這篇文章主要為大家詳細(xì)介紹了C++實現(xiàn)希爾排序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下
本文實例為大家分享了C++實現(xiàn)希爾排序的具體代碼，供大家參考，具體內(nèi)容如下
一、思路：
希爾排序:又稱縮小增量排序，是一種改進(jìn)的插入排序算法，是不穩(wěn)定的。
設(shè)排序元素序列有n個元素，首先取一個整數(shù)gap<n作為間隔，將全部元素分為gap個子序列，所有距離為gap的元素放在同一個子序列中，在每一個子序列中分別施行直接插入排序。然后縮小間隔gap，重復(fù)上述的子序列和排序工作。
二、實現(xiàn)程序：
#include <iostream>
using namespace std;
const int maxSize = 20;
// 希爾排序：每次減小1/3，直到d=1;
// 因為前面增量比較大，間隔比較，減少比較的次數(shù)，已經(jīng)將部分排好序，
// 后面雖然d越來越小，但是因為前面已經(jīng)排好序，所以，后面插入需要比
// 較的次數(shù)減少。
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 << "請輸入要排序的數(shù)的個數(shù)：";
cin >> n;
cout << "請輸入要排序的數(shù)：";
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;
}
測試結(jié)果：
以上就是本文的全部內(nèi)容，希望對大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。
相關(guān)文章
C語言中自動隱式轉(zhuǎn)換與類型強(qiáng)制轉(zhuǎn)換實例分析
這篇文章主要介紹了C語言中自動隱式轉(zhuǎn)換與類型強(qiáng)制轉(zhuǎn)換實例分析,需要的朋友可以參考下2014-07-07
這篇文章主要為大家詳細(xì)介紹了2048小游戲C語言實現(xiàn)代碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-05-05
這篇文章主要給大家介紹了關(guān)于如何利用最簡單的C語言實現(xiàn)AI五子棋的相關(guān)資料,包含了一些五子棋常見的功能,文中也通過詳細(xì)的實例代碼和圖片介紹的非常詳細(xì),需要的朋友可以參考下2021-07-07
今天抽空給大家普及使用C語言操作樹莓派GPIO的詳細(xì)步驟，本文大概分五步給大家介紹樹莓派GPIO安裝步驟，首先需要安裝GPIO庫然后進(jìn)行一步步設(shè)置，具體操作方法跟隨小編一起學(xué)習(xí)吧2021-06-06
C++中putchar與getchar函數(shù)的細(xì)節(jié)及運用
C語言提供putchar函數(shù)，用于給終端輸出一個字符；getchar函數(shù)，可以從終端接收用戶輸入的一個字符，本文給大家分享C++中putchar與getchar函數(shù)的細(xì)節(jié)及運用，感興趣的朋友跟隨小編一起看看吧2021-07-07
在Mat矩陣類的成員函數(shù)中copyTo(roi , mask)函數(shù)是非常有用的一個函數(shù)，尤其是后面的mask可以實現(xiàn)蒙版的功能，下面通過本文給大家介紹下OpenCV copyTo()函數(shù)的相關(guān)知識，感興趣的朋友一起看看吧2022-01-01
這篇文章主要為大家詳細(xì)介紹了OpenCV實現(xiàn)簡單套索工具，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-01-01
我們利用printf 函數(shù)實現(xiàn)一個在屏幕上彈跳的小球。彈跳的小球游戲比較簡單、容易入門，也是反彈球消磚塊、接金幣、臺球等很多游戲的基礎(chǔ)，感興趣的可以了解一下2022-10-10
本篇文章主要介紹了淺談c++ hook 鉤子的使用介紹，詳細(xì)的介紹了c++ hook 鉤子的原理和運行機(jī)制，有興趣的可以了解一下2017-11-11
一文搞懂C++中的四種強(qiáng)制類型轉(zhuǎn)換
很多朋友向小編了解C語言中怎么進(jìn)行強(qiáng)制類型轉(zhuǎn)換呢？在這小編告訴大家強(qiáng)制類型轉(zhuǎn)換可以分為兩種，一種是隱式類型轉(zhuǎn)換一種是顯示類型轉(zhuǎn)換，下面通過示例代碼給大家介紹下，需要的朋友參考下吧2021-07-07