程序员社区

【数据结构与算法】插入排序与希尔排序

一.插入排序

插入排序的原理

插入排序的核心思路是将数据分为有序区和无序区,初始有序区只有第一个元素,插入算法就是从未排序的元素中挑选一个元素,在已排序的区间找到合适的位置并将其插入并保证有序区一直有序。插入排序属于原地排序,是稳定的排序,平均时间复杂度为O(n^2)。

代码示例

public static void insertSort(int[] num){
        if (num==null){
            return;
        }
        for (int i = 0; i < num.length-1; i++) {
            //变量在这里定义,是为了方便内层循环结束后,将temp值放到正确的位置,会用到j
            int j = i;
            //记录i+1的值,因为后续这个位置的值会变,所以必须记录下来
            int temp = num[i+1];
            for (;j>=0;j--){
                //如果比当前元素的值要小就将当前元素的值后移一位
                if (temp<num[j]){
                    //后移一位
                    num[j+1]=num[j];
                }else{
                    //因为数组的左边是有序的,因此只要有一次不满足条件就可跳出循环
                    break;
                }
            }
            //注意这里必须J++,因为上面的内层循环是递减的,
            // 当不满足条件或者break跳出循环时,j的值总会因为上次循环递减而少1,
            // 上次移动元素到后一位之后,最后被移动的元素会在数组中重复两次,因为原位置还是它
            // 所以在这里需要将元素的值用之前记录的temp值覆盖,换而言之就是把数组中后续最小的值插入到当前位置
            num[++j]=temp;
        }
    }

总结

插入排序的时间复杂度 就是判断比较次数有多少,而比较次数与 待排数组的初始顺序有关,当待排数组有序时,没有移动操作,此时复杂度为O(N),当待排数组是逆序时,比较次数达到最大,对于下标 i 处的元素,需要比较 i-1 次。总的比较次数:1+2+...+N-1 ,故时间复杂度为O(N^2)

二.希尔排序

希尔排序原理

希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序的基本思想是:

把记录按步长 gap 分组,对每组记录采用直接插入排序方法进行排序。
随着步长逐渐减小,所分成的组包含的记录越来越多,当步长的值减小到 1 时,整个数据合成为一组,构成一组有序记录,则完成排序。

【数据结构与算法】插入排序与希尔排序插图
希尔排序.jpg

代码示例

 public static void shellSort(int[] num){
        if (num==null){
            return;
        }
        //定义gap为数组长度一般,其实还可以为gap=(length-1)/3
        int gap = num.length/2;
        while (gap>=1){
            for (int i = gap; i < num.length; i++) {
                //变量在这里定义,是为了方便内层循环结束后,将temp值放到正确的位置,会用到j
                int j = i-gap;
                //记录i的值,因为后续这个位置的值会变,所以必须记录下来
                int temp = num[i];
                for (;j>=0;j-=gap){
                    //如果比当前元素的值要小就将当前元素的值后移gap位
                    if (temp<num[j]){
                        //后移gap位
                        num[j+gap]=num[j];
                    }else{
                        //因为数组的左边gap序列是有序的,因此只要有一次不满足条件就可跳出循环
                        break;
                    }
                }
                //注意这里必须j+gap,因为上面的内层循环是递减的,
                // 当不满足条件或者break跳出循环时,j的值总会因为上次循环递减而少gap,
                // 上次移动元素到后gap位之后,最后被移动的元素会在数组中重复两次,因为原位置还是它
                // 所以在这里需要将元素的值用之前记录的temp值覆盖,换而言之就是把数组中当前gap序列后续最小的值插入到当前位置
                num[j+gap]=temp;
            }
            //缩小增量  还可以为gap=gap/3
            gap = gap/2;
        }

    }

总结

时间复杂度情况如下:(n指待排序序列长度)

  1. 最好情况:序列是正序排列,在这种情况下,需要进行的比较操作需(n-1)次。后移赋值操作为0次。即O(n)
  2. 最坏情况:O(nlog2n)。
  3. 渐进时间复杂度(平均时间复杂度):O(nlog2n)

希尔算法在最坏的情况下和平均情况下执行效率相差不是很多。希尔排序没有快速排序算法快,因此中等大小规模表现良好,对规模非常大的数据排序不是最优选择。

由于多次插入排序,我们知道一次插入排序是稳定的,不会改变相同元素的相对顺序,但在不同的插入排序过程中,相同的元素可能在各自的插入排序中移动,最后其稳定性就会被打乱,所以希尔排序是不稳定的。

(注:专家们提倡,几乎任何排序工作在开始时都可以用希尔排序,若在实际使用中证明它不够快,再改成快速排序这样更高级的排序算法。)

赞(0) 打赏
未经允许不得转载:IDEA激活码 » 【数据结构与算法】插入排序与希尔排序

相关推荐

  • 暂无文章

一个分享Java & Python知识的社区