Hill sort, compared to bubble sort, is a little bit less time complex and much more stable.
If a[5]<a[0], then swap directly. If a[10]<a[5], then swap directly. Then increment by 2 each time until increment by 1. Reduced time complexity.
#include <stdio.h> #include <time.h> void Shell(int a[],int len) { int n,j,i,d,tmp; n=5; for(d=n/2; d>0; d/=2) { for(i=d; i<len; i+=d) { tmp=a[i]; for(j=i; a[j-d]>tmp&&j>=d; J -=d)// Set j>=d in advance, otherwise the array will be out of bounds. { a[j]=a[j-d]; } a[j]=tmp; } } } void Print(int a[],int len) { for(int i=0; i<len; i++) { printf("%d->",a[i]); }} int main () {int a [] = {5,78,432,456,1223,4,12,4,1,78,432,456,1223,4,156,78,12,4,3,9}; int len=sizeof(a)/sizeof(a[0]); Shell(a,len); Print(a,len); }Copy the code