189 8069 5689
这篇文章主要讲解了“c++怎么实现希尔排序”，文中的讲解内容简单清晰，易于学习与理解，下面请大家跟着小编的思路慢慢深入，一起来研究和学习“c++怎么实现希尔排序”吧！
创新互联是一家集网站建设,龙湖企业网站建设,龙湖品牌网站建设,网站定制,龙湖网站建设报价,网络营销,网络优化,龙湖网站推广为一体的创新建站企业，帮助传统企业提升企业形象加强企业竞争力。可充分满足这一群体相比中小企业更为丰富、高端、多元的互联网需求。同时我们时刻保持专业、时尚、前沿，时刻以成就客户成长自我，坚持不断学习、思考、沉淀、净化自己，让我们为更多的企业打造出实用型网站。
初始时，有一个大小为 10 的无序序列。
在第一趟排序中，我们不妨设 gap1 = N / 2 = 5，即相隔距离为 5 的元素组成一组，可以分为 5 组。
接下来，按照直接插入排序的方法对每个组进行排序。
在第二趟排序中，我们把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。
按照直接插入排序的方法对每个组进行排序。
在第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。
按照直接插入排序的方法对每个组进行排序。此时，排序已经结束。
需要注意一下的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。
所以，希尔排序是不稳定的算法。
package com.lifeibigdata.fight;
/**
* Created by lifei on 16/10/24.
*/
public class ShellSort {
static int[] shellSort(int[] a){
int gap = a.length / 2;
while (gap >= 1){
// 把距离为 gap 的元素编为一个组，扫描所有组
// for (int i = gap; i < a.length; i++) {
// int j;
// int temp = a[i];
//对距离为 gap 的元素组进行排序
// for (j = i - gap; j >= 0 && temp < a[j]; j = j - gap) {//TODO j - gap
// a[j + gap] = a[j];//TODO i - gap + gap
// }
// a[j + gap] = temp;//TODO j - gap + gap = j
// }
for (int i = gap; i < a.length; i++) {
if (a[i] < a[i - gap]){// 2 0; 3 1;4 2;
int tmp = a[i];
a[i] = a[i - gap];
a[i - gap] = tmp;
}
}
gap = gap /2;
}
return a;
}
public static void main(String[] args) {
int[] a = new int[]{9 , 1 , 2 , 5 , 7 , 4 , 8 , 6 , 3 , 5};
int[] r = shellSort(a);
for (int x:r) {
System.out.println(x);
}
}
}直接插入排序和希尔排序的比较
直接插入排序是稳定的；而希尔排序是不稳定的。
直接插入排序更适合于原始记录基本有序的集合。
希尔排序的比较次数和移动次数都要比直接插入排序少，当N越大时，效果越明显。
在希尔排序中，增量序列gap的取法必须满足：最后一个步长必须是 1 。
直接插入排序也适用于链式存储结构；希尔排序不适用于链式结构。
感谢各位的阅读，以上就是“c++怎么实现希尔排序”的内容了，经过本文的学习后，相信大家对c++怎么实现希尔排序这一问题有了更深刻的体会，具体使用情况还需要大家实践验证。这里是创新互联，小编将为大家推送更多相关知识点的文章，欢迎关注！