1.希爾排序
希爾排序是對直接插入排序的一種改進，基本思想是隔一定間隔取元素組成一組元素，然后對這組元素進行直接插入排序，所有元素排序完一次后，間隔減少，再進行同樣的操作，直到間隔變為1，這時就是直接插入排序了，因為經過前面的步驟，元素大多數都是有序了，直接插入排序，對有序序列的效率是很高的，
2.步驟
1）首先取間隔gap,一般取gap=n/2,下面是8個元素進行一次排序后的結果，
每隔4個元素取一個元素組成一組，然后進行直接插入排序，
2）然后間隔gap=gap/2
3)再取一次gap=gap/2 gap就為1，就是直接插入排序了
3.代碼
代碼其實不難，就是直接插入排序演算法嵌套一層間隔回圈
1 #include<stdio.h> 2 //希爾排序 3 void shellSort(int * arr,int num) 4 { 5 int i,j,k; 6 int temp,gap; 7 //間隔每次除2 8 for(gap=num/2;gap>0;gap/=2) 9 { 10 //直接插入排序演算法 11 for(k=gap;k<num;k++) 12 { 13 temp=arr[k]; 14 j=k-gap; 15 while(j>=0&&arr[j]>temp) 16 { 17 arr[j+gap]=arr[j]; 18 j-=gap; 19 } 20 arr[j+gap]=temp; 21 } 22 } 23 } 24 int main() 25 { 26 int i; 27 int arr[10]={1,3,-9,0,10,2,8,9,19,-1}; 28 shellSort(arr,10);//希爾排序 29 for(i=0;i<10;i++) 30 printf("%d\n",arr[i]); 31 return 0; 32 }
希爾排序演算法的時間復雜度O(n^1.3到n^2)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/62071.html
標籤：其他
上一篇：Google Code Jam 2020 Round 1A 2020 題解
下一篇：滑動視窗（資料結構）