首页 > 代码库 > 希尔排序小结
希尔排序小结
希尔排序
希尔排序就是将给定数组分成多个部分，进行插入排序。每次分组步长gap为n/2,即是每隔gap的数都是一组的。简单的说如果一个数组长度为10{0,1,2,3,4,5,6,7,8,9}，gap为2时，那么0,2,4,6,8,为一组，1,3,5,7,9为一组。然后分别对这两组进行插入排序。gap一般定为n/2,以此循环下去，n/2/2,每次步长为上一次的一半，直到gap==1时，那么在n==1完成后，最终排序也就完成了。
希尔排序图
如上图数组颜色一样的为一组，然后对这一组，进行插入排序。初始数据为 5,4,6,8,7,3,0,1 第一步gap==8/2。
分组情况为{5,7} {4,3} { 6,0} { 8,1}分别对这四组插入排序 { 5,7} {3,4} {0，6} {1,8}
最后数据为{5,3,0,1,7,4,6,8}
gap==2时分组情况为{5,0,7,6} {3,1,4，8} 分别插入排序结果是{0,5,6,7} {1,3,4,8}最后数据结果是{0,1,5,3,6,4,7,8}
如此循环直到n==1完成排序。
代码实现：
void shellsort1(int a[], int n) { int i, j, gap; /** * 步长，划分组的 */ for (gap = n / 2; gap > 0; gap /= 2) { /** * 划分成组 */ for (i = 0; i < gap; i++) { /** * 每组直接插入算法 */ for (j = i + gap; j < n; j += gap) { if (a[j] < a[j - gap]) { int temp = a[j]; int k = j - gap; while (k >= 0 && a[k] > temp) { a[k + gap] = a[k]; k -= gap; } a[k + gap] = temp; } } } } }
希尔排序小结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。