电话怎么做网站推广,网站源码 照明,重庆有什么好玩的,wordpress文章加颜色1. 快速排序的非递归是通过栈来实现的#xff0c;则前序与层次可以通过控制入栈的顺序来实现#xff0c;因为递归是会一直开辟栈区空间#xff0c;所以非递归的实现只需要一个栈的大小#xff0c;而这个大小是小于递归所要的#xff0c;
非递归与递归的时间复杂度是一样的…1. 快速排序的非递归是通过栈来实现的则前序与层次可以通过控制入栈的顺序来实现因为递归是会一直开辟栈区空间所以非递归的实现只需要一个栈的大小而这个大小是小于递归所要的
非递归与递归的时间复杂度是一样的本质没有变化 2. 直接插入排序是把元素从前先后一个一个插入进去若是相同值的相对位置也不会改变所以稳定性好
归并排序 实现方法是分成多组但是合并的时候还是要比较大小来合所以相同值的相对位置也不会改变
选择排序每次选出一个最值若是最大值有多个会有稳定性不好的情况但是可以控制变成稳定性好
冒泡排序冒泡排序是每趟俩俩排序相同值的相对位置是不会改变的 3. 选择排序每次会选出一个最大值或者最小值可以确定位置
快速排序每次的基准值位置可以确定
堆排序每次堆顶的元素是可以确定的
归并排序是分组进行排序的不能确定一个准确的位置 4. 题目给的序列接近有序的插入排序在这里的时间复杂度接近为O(n)而快排在这种情况接近O(n^2),归并排序和堆排序都是O(nlogn) 5. 快速排序初始顺序影响大如果为有序则性能最差
插入排序如果初始为有序则性能最好
希尔排序希尔是插入排序的优化而在有序的情况下插入反而更快
堆排序与归并排序对初始数据的顺序不怎么影响 6. 从题目来看25214768这些数字位置被确定了而选择排序确定的最值所以是希尔排序
第一次的基准值为25左边都比25小右边都比25大第二次的基准值为2047(因为第一行的左边与右边的数字是21与47)则第三次的基准值就为15213568
7. 这里的辅助空间就是空间复杂度为多少快速排序递归过程中会开辟栈的空间递归的深度为二叉树的深度为logn而非递归实现是通过栈来实现 最大空间也就是把从头到叶结点因为每次是成对放入栈里面所以最大为数的高度俩倍2*logn
所以空间复杂度就为logn
8. 快速排序会确定基准值的位置 所以找满足基准值因为第二趟所以需要找到俩个基准值若没有俩个则就不可能为快速排序的第二趟
a第一趟可以为2第二趟可以为3满足情况
b:第一趟可以为2第二趟可以为9
c第一趟基准值只能是9基准值的位置跟排序好的位置是一样的则第二趟没有基准值了
d第一趟可以为9第二趟可以为5 9. 归并排序需要用到格外辅助空间要开辟一个跟原数据一样大的空间
归并排序是一种二分排序算法每次给n个元素排序理想排序的过程中深度为logn所以时间复杂度为nlongn
因为操作是在左右子树排完序之后进行合并合并是在遍历完左右子树的情况下所以就是左右根所以是后序、
归并排序相同值的相对位置不会改变稳定性好
10. 因为要通过堆排序来进行降序所以要建小堆而满足情况只用a为小堆
