针织衫技术支持东莞网站建设,开元酒店集团品牌建设,网站设计策划书,dw做的网站如何用手机看课上
归并排序 最大时#xff0c;就是两个都是完全倒序#xff0c;但注意一定有一个序列先用完#xff0c;此时剩一个序列只有一个元素#xff0c;不用比较#xff0c;直接加入#xff0c;所以就是nn-1,
最小时#xff0c;是都是完全有序#xff0c;且一个序列中的元…课上
归并排序 最大时就是两个都是完全倒序但注意一定有一个序列先用完此时剩一个序列只有一个元素不用比较直接加入所以就是nn-1,
最小时是都是完全有序且一个序列中的元素完全全部小于另一个序列中元素但每次都需要第一个值进行比较直到小的序列全用完就直接一直不用比较加剩下的序列中元素 自顶向下 自底向上 这个意思是说确定外层确定子序列的长度然后每次都从这个序列的头部开始逐渐合并外层确定长度的子序列即内层循环为不断归并两个长度相同为外层确定的长度的子序列直到左子序列的左端到达当前序列的尾部
这句需注意
确定左子序列左端然后根据当前子序列长度确定右子序列左端左子序列右端由于内层判断是lxr-len,所以左子序列右端右子序列左端一定可以直接加减得到但是右子序列右端不能确定所以需要一个min函数 链表合并 经典面试题 极端情况是一直动二号顺序表的元素那就说明二号顺序表元素都比一号顺序小那么k到i时一号顺序表都在对应正确的位置
其他情况下移动一号顺序表就意味着一号顺序表长度变短了
另一种极端情况是一直移动一号顺序表那么k到j时二号顺序表都在正确位置
如果不倒置就是在原基础上按大的排即之前倒置是比较两个表头哪个小把小的放前面现在是比较表尾哪个大把大的放后面就可以直接在原来基础上排序
逆序对
就是后面的序列表头元素放到前面时就相当于此时这个元素比前面的所有元素都小都能构成逆序对即逆序对数量前面序列剩余的长度
如果前面的表头元素移动和后面的不构成逆序对其内部也在底层递归时统计过所以就没有逆序对产生即只在后面序列前移时产生逆序对 翻转对力扣493 逆序对依然产生在后面序列中只不过需要再加一个条件判断
回顾 冒泡排序 每次都可以选出一个当前最大值那么后续比较的时候尾部长度逐渐减小
每次比较都要从第一个元素开始
void bubbleSort(vectorint v){//冒泡排序for(int i 0; i v.size(); i){for(int j 0; j v.size() - i - 1; j){if(v[j] v[j 1])swap(v[j], v[j 1]);}}
}说让排序完成时
快速排序最快nlogn,最差n^2
