交换排序思维脑图思维导图
快速排序与冒泡排序内容讲解
树图思维导图提供 交换排序思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 交换排序思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：3f65e6dffcc237268b77d76da6a082e2
思维导图大纲
交换排序思维导图模板大纲
冒泡排序
思想
两两比较相邻元素，若为逆序就交换称为“一趟”，最多只需要n-1趟
每趟可以使一个元素移动到最终位置（最大/小值）
某一趟排序未交换过，算法提前结束
代码
会背
性能
空间复杂度O(1)
时间复杂度
最好：O(n)
顺序，比n-1次
最坏：O(n^2)
逆序，比、交换n(n-1)/2次，但是每次交换移动3次
平均：O(n^2)
稳定
顺序表、链表都适用
快速排序
思想
任取一个元素作枢轴（基准），一趟排序后分成两部分，前半部分小于基准，后半部分大于基准，递归对两子表重复上述过程
每趟确定1个元素位置
代码实现
万分重要，必须会背
算法思想
low < high才能继续快排；先划分，再划分左子表，再划分右子表
划分操作：最后结束时low == high，因此循环里是low < high，从后向前找到第一个比枢轴小的，换到前面；从前向后同理
最后low位置保存枢轴
性能
空间复杂度
最好：O(logn)
递归深度最小
最坏：O(n)
递归深度最大
递归深度即排序趟数
递归深度与初始数据的排列次序无关
时间复杂度
实际上，时间复杂度=O(n*递归深度)
最好：O(nlogn)
每趟的划分很平均
最坏：O(n^2)
原本正/逆序，此时退化为冒泡排序
平均O(nlogn)
不稳定
用于顺序表，适合并行处理
注意
所谓基准，不一定非得是最中间元素
快排基本思想：找到一个基准，对其附加条件改变元素相对位置
如使序列奇数都在偶数前：
两个指针，从前到后找到1个偶数L(i)，从后到前找到1个奇数L(j)，交换后i++，j--；
如果要利用非递归实现快排，用栈和队列都可以
栈或者队列其实保存的是另一边的上下界
用栈类似于深度优先，一直划分一边，直到划分到只剩一个；用队列类似于广度优先，划分完左边，划分右边，交替进行
相关思维导图模板
树图思维导图提供 专注力训练思维脑图 在线思维导图免费制作，点击“编辑”按钮，可对 专注力训练思维脑图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：ca6435a61cc80f311c29ac82082d8e36
树图思维导图提供 香山精神研究思维导图 在线思维导图免费制作，点击“编辑”按钮，可对 香山精神研究思维导图 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：3d8d880662a5489d30d081f5083ee3dd
沪公网安备 31011502019485号
上海工商