温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

c++怎么实现希尔排序

发布时间:2021-12-20 12:01:42 来源:亿速云 阅读:217 作者:iii 栏目:云计算

这篇文章主要讲解了“c++怎么实现希尔排序”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“c++怎么实现希尔排序”吧!

初始时,有一个大小为 10 的无序序列。
在第一趟排序中,我们不妨设 gap1 = N / 2 = 5,即相隔距离为 5 的元素组成一组,可以分为 5 组。
接下来,按照直接插入排序的方法对每个组进行排序。
在第二趟排序中,我们把上次的 gap 缩小一半,即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组,可以分为 2 组。
按照直接插入排序的方法对每个组进行排序。
在第三趟排序中,再次把 gap 缩小一半,即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组,即只有一组。
按照直接插入排序的方法对每个组进行排序。此时,排序已经结束。
需要注意一下的是,图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到,在排序过程中,两个元素位置交换了。
所以,希尔排序是不稳定的算法。
c++怎么实现希尔排序

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++怎么实现希尔排序这一问题有了更深刻的体会,具体使用情况还需要大家实践验证。这里是亿速云,小编将为大家推送更多相关知识点的文章,欢迎关注!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

c++
AI