web | Java

快排、归并怎么实现的?时间复杂度?

千锋教育

1. 快速排序

1. 是一个优秀的排序算法,O(n²)和Ω(nlgn),期望运行时间:θ(nlgn)且常数因子较小。

2. 快速排序采用了分治的思想 

- 分:将数组划分成两个部分(核心,partition) - 治:递归的对划分的两个子数组进行排序 


2. 归并排序

1. 归并排序(英语:Merge sort,或mergesort),是创建在归并操作上的一种有效的排序算法,效率为O(n log n)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

2. 让左右两部分的元素先有序,然后把两个有序的部分合并为一个有序的过程。那么如何让左边的部分和右边的部分有序呢?

继续把左边的部分分为两部分,然后排序。

然后再把右边的部分分为两部分,再排序。这是一个递归的过程