C++ 算法之希爾排序詳解及實例
更新時間：2017年05月12日 16:44:45 投稿：lqh
這篇文章主要介紹了C++ 算法之希爾排序算法詳解及實例的相關(guān)資料,需要的朋友可以參考下
C++ 算法之希爾排序算法詳解及實例
希爾排序算法
定義：
希爾排序是插入排序的一種，也稱縮小增量排序，是直接插入排序算法的一種更高效的改進版本。
算法思想：
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序，隨著增量逐漸減少，每組包含的關(guān)鍵詞越來越多，當增量減至1時，整個文件恰好被分為一組，算法終止。
時間復雜度：
O(N)
空間復雜度：
O(1)
性能：
希爾排序為不穩(wěn)定算法（一次插入排序是穩(wěn)定的，不會改變相同元素的相對順序，但是在不同的插入排序中，相同的元素可能在各自的插入排序中移動，會打亂其穩(wěn)定性）
優(yōu)勢：
希爾排序不需要大量的輔助空間，比直接插入排序時間要快，并且代碼很好實現(xiàn)。
缺點：
雖然希爾排序相對于直接插入排序要優(yōu)化很多，但是O（N）的算法依舊效率不是很高，并且希爾排序不穩(wěn)定。
代碼實現(xiàn)：
#include <iostream>
#include <Windows.h>
#include <assert.h>
using namespace std;
//希爾排序,從小到大排
void ShellSort(int* arr, int len)
{
assert(arr);
int gap = 3; //先給一個初始組間距，gap為1時即為直接插入排序
for (gap = 3; gap > 0; --gap) //不斷縮小組間距，直到gap=1
{
for (int i = 0; i < len; ++i)
{
for (int j = i + gap; j < len; j = j + gap)
{
if (arr[j-gap] > arr[j])
{
int temp = arr[j]; //將arr[j]處的值先保存起來
arr[j] = arr[j-gap];
arr[j-gap] = temp;
}
}
}
}
}
#include "ShellSort.h"
void TestShellSort()
{
int arr[] = { 100, 2,888, 6, 10, 5, 3, 666, 78, 9, 10000, 45, 67, 33 };
int len = sizeof(arr) / sizeof(arr[0]);
cout << "未排序序列：" << "";
for (int i = 0; i < len; ++i)
{
cout << arr[i] << "->";
}
cout << endl;
ShellSort(arr, len);
cout << "已排序序列：" << "";
for (int j = 0; j < len; ++j)
{
cout << arr[j] << "->";
}
cout << endl;
}
int main()
{
TestShellSort();
system("pause");
return 0;
}
感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
相關(guān)文章
基于OpenCV讀取攝像頭實現(xiàn)單個人臉驗證MFC程序
這篇文章主要為大家詳細介紹了基于OpenCV讀取攝像頭實現(xiàn)單個人臉驗證MFC程序，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-08-08
Visual?Studio?2022?安裝低版本?.Net?Framework的圖文教程
這篇文章主要介紹了Visual?Studio?2022?如何安裝低版本的?.Net?Framework,首先打開?Visual?Studio?Installer?可以看到vs2022?只支持安裝4.6及以上的版本，那么該如何安裝4.6以下的版本，下面將詳細介紹，需要的朋友可以參考下2022-09-09
Linux系統(tǒng)下C語言gets函數(shù)出現(xiàn)警告問題的解決方法
這篇文章主要給大家介紹了關(guān)于在Linux系統(tǒng)下C語言gets函數(shù)出現(xiàn)警告問題的解決方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2018-12-12
這篇文章主要為大家詳細介紹了C++文件上傳、下載工具的相關(guān)資料，感興趣的小伙伴們可以參考一下2016-05-05
這篇文章主要介紹了C++寬字符與普通字符的轉(zhuǎn)換實例詳解的相關(guān)資料,需要的朋友可以參考下2017-06-06
這篇文章主要為大家詳細介紹了C++ Eigen庫計算矩陣特征值及特征向量，具有一定的參考價值，感興趣的小伙伴們可以參考一下2019-06-06
C語言的abs()函數(shù)和div()函數(shù)你了解嗎
這篇文章主要為大家詳細介紹了C語言的abs()函數(shù)和div()函數(shù)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-02-02
在C語言中，浮點數(shù)是一個很重要的類型，浮點數(shù)可以使數(shù)據(jù)更為精確。浮點數(shù)說白了就是帶有小數(shù)點的數(shù)。比如1.6?0.0000?765.2等等，浮點數(shù)具體是怎么用的呢，讓我們一起來看看2022-04-04
這篇文章主要為大家詳細介紹了C語言實現(xiàn)簡單的計算器，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-02-02
C++中的deque是一種雙端隊列，可以在隊列的前端和后端進行插入元素和刪除操作，同時可以視作一個長度不定的數(shù)組，支持高效的插入和刪除操作。本篇文章將深入探討C++中的deque的使用，感興趣的可以了解一下2023-05-05