C++實(shí)現(xiàn)希爾排序（ShellSort）

更新時(shí)間：2020年04月24日 17:00:06 作者：ChanJose

這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)希爾排序，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下

本文實(shí)例為大家分享了C++實(shí)現(xiàn)希爾排序的具體代碼，供大家參考，具體內(nèi)容如下

一、思路：

希爾排序:又稱縮小增量排序，是一種改進(jìn)的插入排序算法，是不穩(wěn)定的。

設(shè)排序元素序列有n個(gè)元素，首先取一個(gè)整數(shù)gap<n作為間隔，將全部元素分為gap個(gè)子序列，所有距離為gap的元素放在同一個(gè)子序列中，在每一個(gè)子序列中分別施行直接插入排序。然后縮小間隔gap，重復(fù)上述的子序列和排序工作。

二、實(shí)現(xiàn)程序：

#include <iostream>
using namespace std;
 
const int maxSize = 20;
 
// 希爾排序：每次減小1/3，直到d=1;
//   因?yàn)榍懊嬖隽勘容^大，間隔比較，減少比較的次數(shù)，已經(jīng)將部分排好序，
//   后面雖然d越來越小，但是因?yàn)榍懊嬉呀?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 << "請(qǐng)輸入要排序的數(shù)的個(gè)數(shù)：";
 cin >> n;
 cout << "請(qǐng)輸入要排序的數(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;
}

測(cè)試結(jié)果：

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持腳本之家。

您可能感興趣的文章:

相關(guān)文章

C語(yǔ)言中自動(dòng)隱式轉(zhuǎn)換與類型強(qiáng)制轉(zhuǎn)換實(shí)例分析
這篇文章主要介紹了C語(yǔ)言中自動(dòng)隱式轉(zhuǎn)換與類型強(qiáng)制轉(zhuǎn)換實(shí)例分析,需要的朋友可以參考下
2014-07-07
2048小游戲C語(yǔ)言實(shí)現(xiàn)代碼
這篇文章主要為大家詳細(xì)介紹了2048小游戲C語(yǔ)言實(shí)現(xiàn)代碼，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2018-05-05
如何利用最簡(jiǎn)單的C語(yǔ)言實(shí)現(xiàn)AI五子棋
這篇文章主要給大家介紹了關(guān)于如何利用最簡(jiǎn)單的C語(yǔ)言實(shí)現(xiàn)AI五子棋的相關(guān)資料,包含了一些五子棋常見的功能,文中也通過詳細(xì)的實(shí)例代碼和圖片介紹的非常詳細(xì),需要的朋友可以參考下
2021-07-07
使用C語(yǔ)言操作樹莓派GPIO的詳細(xì)步驟
今天抽空給大家普及使用C語(yǔ)言操作樹莓派GPIO的詳細(xì)步驟，本文大概分五步給大家介紹樹莓派GPIO安裝步驟，首先需要安裝GPIO庫(kù)然后進(jìn)行一步步設(shè)置，具體操作方法跟隨小編一起學(xué)習(xí)吧
2021-06-06
C++中putchar與getchar函數(shù)的細(xì)節(jié)及運(yùn)用
C語(yǔ)言提供putchar函數(shù)，用于給終端輸出一個(gè)字符；getchar函數(shù)，可以從終端接收用戶輸入的一個(gè)字符，本文給大家分享C++中putchar與getchar函數(shù)的細(xì)節(jié)及運(yùn)用，感興趣的朋友跟隨小編一起看看吧
2021-07-07
深入淺析OpenCV?copyTo()函數(shù)
在Mat矩陣類的成員函數(shù)中copyTo(roi , mask)函數(shù)是非常有用的一個(gè)函數(shù)，尤其是后面的mask可以實(shí)現(xiàn)蒙版的功能，下面通過本文給大家介紹下OpenCV copyTo()函數(shù)的相關(guān)知識(shí)，感興趣的朋友一起看看吧
2022-01-01
OpenCV實(shí)現(xiàn)簡(jiǎn)單套索工具
這篇文章主要為大家詳細(xì)介紹了OpenCV實(shí)現(xiàn)簡(jiǎn)單套索工具，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2022-01-01
C++實(shí)現(xiàn)簡(jiǎn)易反彈小球游戲的示例代碼
我們利用printf 函數(shù)實(shí)現(xiàn)一個(gè)在屏幕上彈跳的小球。彈跳的小球游戲比較簡(jiǎn)單、容易入門，也是反彈球消磚塊、接金幣、臺(tái)球等很多游戲的基礎(chǔ)，感興趣的可以了解一下
2022-10-10
淺談c++ hook 鉤子的使用介紹
本篇文章主要介紹了淺談c++ hook 鉤子的使用介紹，詳細(xì)的介紹了c++ hook 鉤子的原理和運(yùn)行機(jī)制，有興趣的可以了解一下
2017-11-11
一文搞懂C++中的四種強(qiáng)制類型轉(zhuǎn)換
很多朋友向小編了解C語(yǔ)言中怎么進(jìn)行強(qiáng)制類型轉(zhuǎn)換呢？在這小編告訴大家強(qiáng)制類型轉(zhuǎn)換可以分為兩種，一種是隱式類型轉(zhuǎn)換一種是顯示類型轉(zhuǎn)換，下面通過示例代碼給大家介紹下，需要的朋友參考下吧
2021-07-07