十大經(jīng)典排序算法系列博客——>傳送門

---

希爾排序由Shell在1959年發(fā)明，又叫縮小增量排序，是第一個突破O(n^2)的排序算法，屬于簡單插入排序的改進(jìn)版，會優(yōu)先比較距離較遠(yuǎn)的元素。

• 算法步驟：
  • 選擇一個增量序列T1,T2,…,Tk， 其中Ti>Tj，Tk=1, i>j;
  • 每趟排序，根據(jù)對應(yīng)的增量Ti，將待排序列分割成若干子序列，分別對各子序列進(jìn)行直接插入排序；
  • 按增量序列個數(shù)k，對序列進(jìn)行k趟排序。
• 希爾排序?qū)嵗?#xff1a;
  下圖的增量序列為：5，2，1，第一趟排序?qū)⒃隽繛?的子序列進(jìn)行插入排序，第二趟排序?qū)⒃隽繛?的子序列進(jìn)行插入排序，第三趟將增量為1的子序列進(jìn)行插入排序，最終完成排序
  

---

代碼實現(xiàn)

#include <iostream>using namespace std;int a[] = {70,30,40,10,80,20,90,100,75,60,45};void shell_sort(int a[],int n); int main() {cout<<"Before Sort: ";for(int i=0; i<11; i++)cout<<a[i]<<" ";cout<<endl;shell_sort(a, 11);cout<<"After Sort: ";for(int i=0; i<11; i++)cout<<a[i]<<" ";cout<<endl;system("pause"); }void shell_sort(int a[], int n) {int gap;for(gap = 3; gap >0; gap--){for(int i=0; i<gap; i++){for(int j = i+gap; j<n; j=j+gap){if(a[j]<a[j-gap]){int temp = a[j];int k = j-gap;while(k>=0&&a[k]>temp){a[k+gap] = a[k];k = k-gap;}a[k+gap] = temp;}}}} }

總結(jié)

以上是生活随笔為你收集整理的【GIF动画+完整可运行源代码】C++实现 希尔排序——十大经典排序算法之四的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。