首页  

归并排序与快速排序     所属分类 algo 浏览量 271
分治 divide-and-conquer 
递归 
归并排序 mergeSort
快速排序 quickSort

归并排序 核心思想
数组从中间分成左右两部分
左右两部分分别排序
排好序的两部分合并 

稳定排序
时间复杂度 O(nlogn)   最好 最坏 平均情况 都是O(nlogn)
空间复杂度 O(n)  


快速排序 三步走
选择基准值  
将数组分成两个子数组 , 小于基准值的元素和大于基准值的元素
对两个子数组进行快速排序

非稳定排序
原地排序  不占用额外空间

分区点 基准点 pivot
借助双指针确定pivot位置的分区函数
大部分情况下的时间复杂度为 O(nlogn)  极端情况下退化到 O(n*n)

两个常见快排优化方法

三数取中法
从区间 首 尾 中间 分别取出一个数, 取这 3 个数的中间值作为分区点
随机法

上一篇     下一篇
线性代数词汇

微积分词汇

排列与组合

一些有趣的技术网站

程序数据结构与算法

Java switch tableswitch lookupswitch