C++ 算法之希爾排序詳解及實(shí)例
C++ 算法之希爾排序算法詳解及實(shí)例
希爾排序算法
定義：
希爾排序是插入排序的一種，也稱(chēng)縮小增量排序，是直接插入排序算法的一種更高效的改進(jìn)版本。
算法思想：
希爾排序是把記錄按下標(biāo)的一定增量分組，對(duì)每組使用直接插入排序算法排序，隨著增量逐漸減少，每組包含的關(guān)鍵詞越來(lái)越多，當(dāng)增量減至1時(shí)，整個(gè)文件恰好被分為一組，算法終止。
時(shí)間復(fù)雜度：
O(N)
空間復(fù)雜度：
O(1)
性能：
希爾排序?yàn)椴环€(wěn)定算法（一次插入排序是穩(wěn)定的，不會(huì)改變相同元素的相對(duì)順序，但是在不同的插入排序中，相同的元素可能在各自的插入排序中移動(dòng)，會(huì)打亂其穩(wěn)定性）
優(yōu)勢(shì)：
希爾排序不需要大量的輔助空間，比直接插入排序時(shí)間要快，并且代碼很好實(shí)現(xiàn)。
缺點(diǎn)：
雖然希爾排序相對(duì)于直接插入排序要優(yōu)化很多，但是O（N）的算法依舊效率不是很高，并且希爾排序不穩(wěn)定。
代碼實(shí)現(xiàn)：
#include <iostream>
#include <Windows.h>
#include <assert.h>
using namespace std;
//希爾排序,從小到大排
void ShellSort(int* arr, int len)
{
assert(arr);
int gap = 3; //先給一個(gè)初始組間距，gap為1時(shí)即為直接插入排序
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]處的值先保存起來(lái)
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;
}
感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！
相關(guān)文章
這篇文章主要介紹了c++字符串分割的方法，幫助大家更好的理解和學(xué)習(xí)c++，感興趣的朋友可以了解下2020-08-08
C++實(shí)現(xiàn)LeetCode(90.子集合之二)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(90.子集合之二),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07
讓?xiě)?yīng)用程序只運(yùn)行一個(gè)實(shí)例的實(shí)現(xiàn)方法
c++10進(jìn)制轉(zhuǎn)換為任意2-16進(jìn)制數(shù)字的實(shí)例
C++ Dijkstra算法之求圖中任意兩頂點(diǎn)的最短路徑
OpenCV實(shí)現(xiàn)彩色照片轉(zhuǎn)換成素描卡通片
C++ string與int的相互轉(zhuǎn)換(使用C++11)
