首页 > 代码库 > 希尔排序
希尔排序
我体会的希尔排序,是插入排序的的一种改进,对待排序的数组以一定的间隔划分成子数组,将这些子数组进行插入排序。随后间隔减小,划分新的子数组,插入排序。直至间隔为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 }
希尔排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。