算法系列博客【算法】打磨问题范围的提出和代码规格
【算法】复杂度理论(时间复杂度)
【字符串】最长回文子串(bloot force算法)
【字符串】最长回文子串(中心线枚举算法)。
【字符串】最长回文子串(动态规划算法)
【字符串】字符串检索(蓝力算法)
(【字符串】字符串检索(Rabin-Karp算法) ) ) ) ) ) ) ) )。
【算法】双重指针算法|双重指针算法分类|对置双重指针|有效回文串)
(【算法】双定点算法(有效回文串II ) ) ) ) ) ) ) ) )。
(【算法】哈希表(2数之和) ) ) ) ) ) ) )。
【算法】快速排序
【算法】合并排序
【算法】快速排序与合并排序的比较
文章编目算法系列博客1、时间复杂度2、空间复杂度3、排序稳定性3、局部有序和整体有序
一、时间复杂性
快速排序(Quick Sort )和合并排序)时间复杂度均为o(O(nlogn ) o(O(nlogn ) o ) nlogn )；
快速排序的平均时间复杂度为o(O(nlogn ) o(n(logn ) o ) nlogn )，该时间复杂度是期望值，快速排序最坏情况下达到o (n2 ) o (n ^2) o ) N2 )。
有六种排列顺序，例如：阵列[ 1，2，3 ]的排列顺序，计算这六种排列顺序的时间复杂度的平均期望是o(O(nlogn ) o(n(logn ) o ) nlogn )。
最坏情况下，[ 1，2，3 ]序列时，时间复杂度o(n2 ) o ) n^2) o ) n2 )；
合并排序的最佳时间复杂度和最坏时间复杂度均为o(O(nlogn ) o(n ) logn ) o(O(nlogn )；
从时间复杂度来说，合并排序的稳定性高于快速排序，两者的时间复杂度相当
二、空间复杂度从空间复杂度来说，合并排序的空间复杂度是
O ( n ) O(n) O(n) , 快速排序 的空间复杂度是 O ( 1 ) O(1) O(1) , 快速排序没有使用额外的空间 , 在数组原地进行排序 ,三、排序稳定性
排序的稳定性 : 假如数组中有两个相同的元素 , 给这两个相同的元素分别打上标记 , 如果每次排列得到的元素顺序都是相同的 , 则说明该排序是稳定的 ;
如 : { 2 , 1 , 1 , 2 } {2,1,1,2} {2,1,1,2} , 中给 2 2 2 打上标记 , { 2 ′ , 1 , 1 , 2 ′ ′ } {2',1,1,2''} {2′,1,1,2′′} , 最终排序后是 { 1 , 1 , 2 ′ , 2 ′ ′ } {1,1,2', 2''} {1,1,2′,2′′} 还是 { 1 , 1 , 2 ′ ′ , 2 ′ } {1,1,2'', 2'} {1,1,2′′,2′} ;
快速排序中 , 这两个结果随机出现 , 同样使用快速排序 , 并不能保证得到的是相同的标记元素次序 ;
归并排序 , 可以保证 , 每次排序 , 得到的都是相同的结果 ;
三、局部有序与整体有序
快速排序 与 归并排序 , 都是将数组分为两个部分 , 然后两部分再次进行递归 ;
快速排序 随便选择了一个数组元素 p 作为中心点 , 将小于等于 p 的元素放在左边 , 将大于等于 p 的元素放在了右边 , 分割完毕后 , 左侧的元素肯定小于右侧的元素 ;
然后对左侧 和 右侧 再次分别选择一个元素 m , n , 进行分割 , 分为 4 份 ,
在 4 份的基础上 , 再次进行分割 , 分为 8 份 , 递归调用该快速排序算法 , 直到所有的元素有序为止 ;
快速排序 是 先整体有序 , 然后局部有序 ;
归并排序 先根据中心点分成两部分 , 左侧和右侧分别进行排序 , 两遍都排序完毕后 , 再组合到一起 ;
归并排序 是 先局部有序 , 然后整体有序 ;