概述
如何理解直接插入排序?它需要几步来完成?是像字面意思那样直接插入到我们能看到的大小位置么?怎么个直接法?
我们先来看一下概念
直接插入排序:在插入第i个记录时,R1,R2....Ri-1均已排好序,这时将Ri的关键字Ki依次与关键字Ki-1,Ki-2等进行比较,从而找到应该插入的位置并将Ri插入,插入位置及其后的记录依次向后移动。
读完上面的概念我们就清楚了,直接插入排序需要四步
①、前提:插入前已排好序
②、比较:逐个从后面开始比较
③、直接插入:通过比较找到应该插入地方直接插入
④、排序:插入位置及其后的记录依次向后移动
所以,你是否get到了这个所谓的直接插入排序呢。就是直接插入到我想要插入的位置,其他的内容逐个向后移动!
但以上的排序有一个前提,那就是第一步已排好序,那如果初始状态未排好序要如何处理?
比如一个序列初始状态为:57 68 59 52
我们要如何进行直接插入排序呢?
它的时间复杂度是多少呢?比如我们有n个元素
已排好序时:最好的状态是比较一次就达到了结果,,时间复杂度为O(1),而最差的状态是从最后一个元素N比到了最前面第一个元素1,这时的时间复杂度为O(n)。
未排好序时:首先每个元素都要进行一次排序,时间复杂度为O(n),之后再加上已排好序后的n次比较,所以最后的时间复杂度为O(n^2)。
所以直接插入排序最后的时间复杂度为O(n^2)。
空间复杂度:在比较的过程中始终是一个元素一个元素的比较,所以这里的空间复杂度为O(1)。
最后
以上就是悲凉心情为你收集整理的排序一(直接插入排序)的全部内容,希望文章能够帮你解决排序一(直接插入排序)所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错,欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复