希尔排序

时间复杂度：小于O（n^2）.

#include<iostream> using namespace std; void shellsort2(int a[], int n) { for(int i=n/2;i>0;i/=2) { for(int j=i;j<n;j++) { if(a[j]<a[j-i]) { int x=a[j]; int k=j-i; while(a[k]>x&&k>=0) { a[k+i]=a[k]; k=k-i; } a[k+i]=x; } } } } int main() { int a[5]={2,5,3,4,1}; shellsort2(a, 5) ; for(int i=0;i<5;i++) cout<<a[i]<<endl; }