您现在的位置是:首页 > 正文

插入排序小结

2024-01-30 23:05:30阅读 0

最近上心找实习,把博客落下了,这不行啊
抓住3月的尾巴,赶紧更新
预计会把排序算法总结一下,手边有现撸的代码
其他的(二叉树、图等)还需要看情况,要找OJ去刷题(只怪先前没积累,还是要过笔试关的),或者修补一下其他短板,总结性的工作要靠后了。

直接插入排序

思想:

从未排序部分的数组中找到第一个元素,与已经排序(升序)部分由后向前比较,找到(有后向前)第一个比选中元素小的位置(或者说是最后一个比自己大的位置),这就是需要插入的地方。

关键点:

  • 就是寻找插入的位置:每一个选中的元素需要有后向前不停与已排序数组部分比较
  • 移动数据:记录下标,比较完成同意移动或者像下面代码中,边比较边移动

代码:

public void insertSort(int[] nums){
        int end=nums.length;
        //数组第一个元素单独可以看作是有序的,所以选择从数组第二个元素开始比较
        for(int i=1;i<end;i++){
            int temp=nums[i];
            /*注释部分代码和下面代码功能相同,while循环感觉不易懂,所以修改之
            */
            //int p=i-1;
            /*while(p>=0 && nums[p]>temp){
                nums[p+1]=nums[p];
                p--;
            }*/
            /*这种方式是一边比较一边就移动了元素
             *也可以用下标记录需要移动的位置,比较完成用循环统一移动数组元素(见折半插入的辅助函数)
            */
            for(int p=i-1;p>=0;p--){
                if(nums[p]>temp){
                    nums[p+1]=nums[p];
                }else break;
            }
            nums[p+1]=temp;
        }
    }

折半插入排序

折半插入与直接插入排序思想相同,区别在于未排序元素与已排序数组部分比较时,不是由后至前比较,而是采用二分法比较,提高比较时候的效率

代码:

public void binaryInsertionSort(int[] nums){
    int end=nums.length;//记录数组大小,虽然说编译器优化比人强,但总觉得这样保存起来会快一点
    for(int i=1;i<end;i++){
        int temp=nums[i];
        //二分查找
        int left=0,right=i-1,mid;
        while(left<=right){
            mid=(left+right)/2;
            if(temp>nums[mid]){
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        moveBackword(nums,left,i);
        nums[left]=temp;
    }
} 
/**用于向后移动数组中若干个元素
 * @param from 数组起始需移动元素,完成移动后数组from下标的内容无用,已经移动到后一个
 * @param to 数组终止需移动元素下标,数组to下标内容会被覆盖消失掉
*/
private void moveBackword(int[] nums,int from,int to){
    for(int i=to;i>from;i--){
        nums[i]=nums[i-1];
    }
}

希尔排序

思想:

排序算法中,如果待排序列比较有序,那么对待排序列排序的时间复杂度就会降低,如果完全有序(最好情况),那么排序通常就变成了遍历数组,复杂度变成O(n)。
希尔排序就是借助这个特点,首先将待排序列处理为部分有序的序列,然后再对若干个有序序列进行重排(有分治的思想)。

关键点:

  • 如何预处理:分治,需要先划分,这里希尔排序选择让待排序数组先两个一组、三个一组、四个一组……直到全部为一组的策略。这其中,需要设置一个数据“增量”,用来标识“每几个一组”的几个。
  • 增量的选择:下面代码使用的比较简单的,数组长度/2,然后每次排序之后再/2,但还有其他选择方式。
  • 稳定性:由于希尔排序分组的方式(数组first下标元素与mid下标元素为一组,以此类推),数组排序会出现元素“跳”着插入有序数组的情况,所以希尔排序是不稳定的。

代码:

public static void shellSort(int []nums){
        int end=nums.length;
        int d=nums.length/2;//增量,首先设为总数组的一半,这样下标0和0+d的元素是一组,而且一组只有两个元素,1、2...类推
        while(d>=1){
            for(int k=0;k<d;k++){
                //对于希尔排序预处理每一个小数组时使用直接插入排序
                for(int i=k+d;i<end;i+=d){
                    int temp=nums[i];
                    int p=i-d;
                    while(p>=0 && nums[p]>temp){
                        nums[p+d]=nums[p];
                        p-=d;
                    }
                    nums[p+d]=temp;
                }
            }
            d/=2;//一次排序完成之后,增量减半,下一次排序,每一组元素增加
        }
    }

网站文章

  • 控制流图、圈复杂度 热门推荐

    控制流图、圈复杂度 热门推荐

    继续上次的测试作业,学习完程序插装的概念,今天学习测试的静态分析方法:绘制控制流图与计算圈复杂度。 一、控制流图: 一个过程或程序的抽象表现,常以数据结构链的形式表示。 二、圈复杂度: 复杂度越高,软件质量就越低,测试就越困难。 圈复杂度(McCabe),其复杂度V(G)可按以下公式计算: V(G) = E – n + 2 其中,E为图G中的边数,

    2024-01-30 23:05:23
  • MT6701磁编码器使用指南,14Bit单圈绝对值,I2C stm32 HAL库读角度,兼容AS5600

    MT6701磁编码器使用指南,14Bit单圈绝对值,I2C stm32 HAL库读角度,兼容AS5600

    MT6701是麦歌恩(MagnTek)公司的磁性角度传感器芯片,提供14Bit 0~360°单圈绝对角度检测,拥有等多种信息输出方式,还可根据磁场强度的瞬时变化提供非接触式按压检测功能。能够以较低的成...

    2024-01-30 23:05:16
  • jcg 836 固件_JCG Studios – ArkDroid Beta发布

    jcg 836 固件_JCG Studios – ArkDroid Beta发布

    jcg 836 固件 大家好, 最近几个月,我们一直在忙于开发我们的第一个Android游戏项目。 方舟机器人我们就是所谓的“进化的碎石机”; 一个Arkanoid克隆游戏,它以电影故事和RPG精髓丰富了经典的“打破常规”游戏世界! 可以肯定的是,我们在Android平台上进行的首次游戏开发工作中学到了很多东西,并且打算与Java Code Geeks社区的其他成员共享所有“多汁的”细节! ...

    2024-01-30 23:04:49
  • JAVA和C语言有啥区别?是选择学习JAVA还是C?

    JAVA和C语言有啥区别?是选择学习JAVA还是C?

    JAVA和C语言有啥区别 1、C语言是面向过程的语言,执行效率高;Java是面向对象的语言,执行效率比C语言低; 2、C语言的安全性不如Java,C语言没有Java的垃圾回收机制,申请的空间要手动释放...

    2024-01-30 23:04:42
  • 程序员这个职业的危险期你知道吗

    这么多的职业病,再加上不分昼夜的加班,说不准哪天就又出来个胡新宇。 1.近视 整天瞅着屏幕,想不近视都难。每次开技术会议,往下看都是白茫茫一片。从事IT而不戴眼镜的人,真是让人羡慕啊。 2.颈椎病 每天坐在那里,盯着一个地方,时间稍长,就感觉脖子僵硬。赶快去检查下颈椎吧。 3.腰间盘突出 每天坐8个小时,很少活动,再加上坐姿不雅,腰酸背疼。 4.胃病 工作紧张,匆忙的快餐,有个好胃...

    2024-01-30 23:04:33
  • 关于AndroidStudio的代理(Proxy)设置无效问题

    关于AndroidStudio的代理(Proxy)设置无效问题

    AndroidStudio中的代理设置我们一般可以找到菜单Apperarance & Behavior->System Settings->HTTP Proxy配置界面大概如下直接配置HTTP代理即可...

    2024-01-30 23:04:04
  • 5G基本原理/5G NR的关键技术

    5G基本原理/5G NR的关键技术

    主要介绍5G技术的基本原理,包括调制方式、波形设计、帧结构、参考信号以及信道编码方式等。

    2024-01-30 23:03:57
  • Spring5框架

    Spring5框架

    Spring5框架文章目录Spring5框架概述小案例IOC什么是IOC底层原理IOC(beanfactory接口)IOC操作Bean管理什么是Bean管理Bean管理操作两种方式基于 xml 配置文...

    2024-01-30 23:03:49
  • C语言练习第14题

    C语言练习第14题

    前言我怎么又开始玩了,赶紧把囤的草稿全发了。第十四题题目:利用条件运算符的嵌套来完成此题:学习成绩>=90分的同学用A表示,60-89分之间的用B表示,60分以下的用C表示。我的思路:...

    2024-01-30 23:03:42
  • 技术方案评审

    技术方案评审

    把需求抽象成接口。

    2024-01-30 23:03:13