首页 > 代码库 > 希尔排序

希尔排序

我体会的希尔排序,是插入排序的的一种改进,对待排序的数组以一定的间隔划分成子数组,将这些子数组进行插入排序。随后间隔减小,划分新的子数组,插入排序。直至间隔为1,对完整的数组进行插入排序。

贴出希尔排序的实现和插入排序的实现,可以进行对比。

 1 // Shell sort, can be treated as a evolution of insert sort. 2 void 3 ShellSort(int arr[], int len) 4 { 5     // a common way of choosing increment: len, len/2, ..., 1 6     for (int increment = len/2; increment > 0; increment /= 2) { 7         // insert sort of array consist of elements separated by increment 8         for (int i = increment; i < len; i++) { 9             int tmp = arr[i];10             int j;11             for (j = i; j >= increment && arr[j-increment] > tmp; j -= increment) {12                 arr[j] = arr[j-increment];13             }14             arr[j] = tmp;15         }16     }17 }18 19 // Insert sort20 void21 InsertSort(int arr[], int len)22 {23     for (int i = 1; i < len; i++) {24         int tmp = arr[i];25         int j;26         for (j = i; j >= 1 && arr[j-1] > tmp; j--) {27             arr[j] = arr[j-1];28         }29         arr[j] = tmp;30     }31 }

 

希尔排序