归并排序首先递归划分数组直至一个元素,每次都是**“对半”划分**(不能保证每次划分的两个子区间内元素数量相等),时间复杂度稳定,然后从下往上进行归并处理。
递归划分的过程:
0
层,n
个数被划分为1
个子区间1
层,将n
个数划分为2
个子区间2
层,将n
个数划分为4
个子区间…
log n
层,将n
个数划分为n
个子区间例如对于数组[5,2,3,4,1,8,7,6]
,l = 0, r = 7
。**递归划分(自上而下)**如下图所示:
选取8个元素的数组为例是为了更好地看出划分的效果。显然并不是所有情况都能划分地这么“规整”,会存在划分的子区间内元素不等的情况,但是由于每次划分下标的选取都是采用的是(区间左下标+区间右下标)/2
,所以总体来说,递归划分的深度为log n
层。当区间内只有一个元素时,无法再进行划分,直接返回。
**归并处理(自下而上)**的示意图如下:
圆弧表示这段区间内的排序操作,旁边的数字表示操作的顺序。排序使用的方法是归并(用一个临时数组合并两个有序数组),时间复杂度为O(n)
,空间复杂度为O(n)
,n
为归并的元素个数,具体归并操作就不展开了,本文主要分析其过程和复杂度。
显然:
2
层中,共4
个子区间,发生了4次排序,共排序8
个元素。1
层中,共2
个子区间,发生了2次排序,共排序8
个元素。0
层中,共1
个子区间,发生了1次排序,共排序8
个元素。即对于每一层的每一个子区间(最后一层不算,因为它每个区间只有一个元素,不需要排序),处理的时候都需要遍历一次区间中的每一个元素。
所以对于每一层来说,遍历个数都为n
,复杂度为O(n)
。而总共log n
层,所以归并排序的时间复杂度为O(nlog n)
。
又因为每次归并过程中需要用到临时数组来存储元素,而且在第0
层所需数组大小的最大,其大小为n
;所以归并排序的空间复杂度为O(n)
。(也可考虑其递归过程产生的log n
层递归调用的空间复杂度)
void merge(int l, int r){
if(l >= r) // 该子区间只有一个元素,直接返回
return;
int mid = (l + r) >> 1; // 取分界点 mid = (l + r) / 2
merge(l, mid); // 左子区间为(l, mid)
merge(mid + 1, r); // 右子区间为(mid + 1, r)
int tmp[r - l + 1] = {0}; // 临时数组,大小为区间长度
int k = 0, i = l, j = mid + 1; // k是已归并的元素数量,i是做子区间起点,j是右子区间起点
while(i <= mid && j <= r){ // 归并操作,合并两个有序子区间
if(a[i] < a[j])
tmp[k++] = a[i++];
else
tmp[k++] = a[j++];
}
while(i <= mid)
tmp[k++] = a[i++];
while(j <= r)
tmp[k++] = a[j++];
for(int i = 0;i < k;i++) // 更新一次数组,上层在此基础之上继续归并排序(自下而上)
a[l + i] = tmp[i];
}
快速排序也是利用分治的思想对各区间进行排序处理,时间复杂度不那么稳定,然后从上往下进行排序处理。与归并排序不同,快速排序不是每次将区间“对半”划分,而是按轴(值)划分,轴左边的数小于等于他,轴右边的数大于等于他。所以轴的选取非常重要,将会影响到他的时间复杂度。
快速排序有很多种模板,但是核心都是将区间分为两部分,再对子区间进行处理,直至区间不可分
有一种是将区间分为两部分:小于等于x的部分、大于等于x的部分
还有是将区间分为三部分,小于等于x的部分、x、大于等于x的部分(因为不会递归x的部分,所以也可以理解为分成了两部分)
…
*第2
种方法,是本文使用的方法。因为他每一次划分都将数x
放在了正确的位置上,笔者认为这样更好理解时间复杂度。*如下图所示:
3
层中的弧线没有排序操作,因为他只有一个元素会直接返回,这里花弧线主要是方便标顺序以及表示这个数的位置被确认了1
层确定了1
个元素的位置;第2
层确定了2
个元素的位置(注意不是同时确定的);…如果每次选取轴都恰好能像上图一样使区间“对半”划分,则快速排序的递归划分的复杂度为log n
,即划分最多log n
层;对于每一层,执行上述的过程中都要遍历每一个元素,复杂度为O(n)
;这两点点和归并排序一样,即快速排序最好的总时间复杂度为O(n log n)
。
但是,每次都“对半”划分这个概率是否有点太低?甚至假如每次都选取了当前区间的最大/小值最为轴的话:
递归的第0层,
n
个数被划分为1
个子区间,每个子区间的数字个数为n
;递归的第1层,
n
个数被划分为2
个子区间,每个子区间的数字个数为n-1
、1
;(那1个数即是最大/小值,他没有右/左子区间;后续同理)递归的第2层,
n-1
个数被划分为2
个子区间,每个子区间的数字个数为n-2
、1
;递归的第3层,
n-2
个数被划分为2
个子区间,每个子区间的数字个数为n-3
、1
;…
- 递归的第
n-1
层,2
个数被划分为2
个子区间,每个子区间的数字个数为1
、1
;- 递归的第
n
层,1
个数被划分为1
个子区间,每个子区间的数字个数为1
;- (可以理解为每次划分得很极限,人家归并排序都一半一半分(即
log n
层),这里直接一个一个分,所以就要分n
层咯)对于每一层,处理的时候都需要遍历一次区间中的每一个元素,所以对于
1~n
层来说,遍历个数为n
、n-1
、n-2
、…、2
、1
。所以时间复杂度最差为
n + n-1 + ...+ 2 + 1
等差数列求和为:n(1+n)/2
,即O(n^2)?
。
空间复杂度主要是递归造成的栈空间的使用,最好情况,递归树的深度为log n
;最坏情况,需要进行n
次递归调用,其空间复杂度为O(n)
,
// a[n]
// qsort(0, n - 1);
void qsort(int l, int r) {
if(l >= r)
return;
int i = l, j = r;
// 轴为 a[l]
while(i < j) {
while(i < j && a[j] >= a[l]) j--; // 从右边开始选一个小于轴的数。注意要先从j开始找,因为如果a=[5,4,3,2,6],先从i找会导致5和6交换,原因就在于没有先使用右指针限制左指针的移动范围
while(i < j && a[i] <= a[l]) i++; // 从左边开始选一个大于轴的数
swap(a[i], a[j]); // 交换这两个不在正确区域的数
}
swap(a[i], a[l]); // 把轴换到交界处,真的是轴
qsort(l, i - 1); // 左子区间
qsort(i + 1, r); // 右子区间
}
从上面分析可知,每次排序都会确定一个数的位置,左边都是大于等于他的数,右边都是大于等于他的数。所以如果我需要前k
小的数或者第k
小的数,就可以根据每次确定的这个位置来选择下次递归的方向,相当于进行了剪枝。
例如,如果需要第5
小的数。第一次我选取的轴恰好是第8
小的数,说明此时,轴左边部分的数小于等于轴(即比第8
小还小,第9,10,11...
小),就算再递归这一部分,也是南辕北辙;所以递归右边大于等于轴部分才能接近第5
小,后续同理。
所以理想情况下,每次只需要递归一边(约为上一次的一半),时间复杂度:
n
+
n
2
+
n
4
+
.
.
.
=
n
(
1
+
1
2
+
1
4
+
1
8
.
.
.
)
<
2
n
n + \frac{n}{2} + \frac{n}{4}+ ... =n(1+\frac12+\frac14+\frac18...)<2n
n+2n?+4n?+...=n(1+21?+41?+81?...)<2n,即O(n)
。
同理上节,最坏情况下复杂度为O(n^2)
。
要找第
1
小,第一次选到第10
小(最大),选择靠近第1
小的那边(也没有另一半来选撒),然后选到第9
小…然后然后选到第8
小…即每次都脸黑地选取到区间最大/小值。
// a[n]
void q_select(int l, int r, int &k) {
if(l >= r)
return;
int i = l, j = r;
while(i < j) {
while(i < j && a[j] >= a[l]) j--;
while(i < j && a[i] <= a[l]) i++;
swap(a[i], a[j]);
}
swap(a[i], a[l]); // 与上述快速排序一致
if(i == k - 1) // 恰好是
return;
if(i < k - 1) // 判边
q_select(i + 1, r, k);
else
q_select(l, i - 1, k);
}