数据结构和算法-递归和排序

简述

Recursion,递归是一种非常广泛的算法,很多数据结构和算法的编码实现都要用到递归,比如DFS深度优先搜索、前中后序二叉树遍历等。

Sort,排序算法是每个人都要掌握的算法,分析排序算法同样也能够锻炼对大O表示法的掌握。

递归

递归条件

递归需要满足的三个条件:

  • 一个问题可以分解为几个子问题的解;

  • 问题和子问题之间,除了数据规模,解题思路是一样;

  • 存在递归终止条件。

递归代码的关键在于如何找到将大问题分解为小问题的规律,并且基于此写出递归公式,然后推敲终止条件,最后将递推公式和终止条件翻译成代码,例如f(n)=f(n-1)+f(n-2)

递归问题

警惕堆栈溢出和重复计算。

堆栈溢出:

计算中的函数调用会使用临时变量所封装的栈帧压入栈,系统栈或者虚拟机栈空间一般都不大,如果递归的数据规模很大,很容易堆栈溢出,解决办法是,最好设置一个最大的调用深度。

重复计算:

例如计算f(5),可以分解为f(4)+f(3),也就是分解为f(3)+f(2)+f(3),此时f(3)就计算了两次,解决办法是,利用散列表或者某种其他的数据结构保存已经计算的结果。

还有空间复杂度可能会较高的问题。

排序

种类:

排序算法时间复杂度是否基于比较
冒泡、插入、选择O(n²)
快排、归并O(nlogn)
桶、计数、基数O(n)×

分析方法:

  1. 最好情况、最坏情况、平均情况时间复杂度,因为有序度不同的数据对排序会有一定影响;
  2. 时间复杂度的系数、常数、低阶,由于常用的排序数据可能不多,所以要考虑这些因素;
  3. 比较次数和交换次数;
  4. 内存消耗,原地排序就是指空间复杂度为O(1)的排序算法;
  5. 稳定性,如果待排序的数据中存在相等的数据,这两个相等数据没有发生前后顺序的变化,则称该算法为稳定排序;
  6. 有序度:数组中具有有序关系的元素对的个数,满有序度就是所有元素有序,其值为:n*(n-1)/2,逆序度=满有序度-有序度。

冒泡排序(Bubble Sort)

原理:前后两个元素两两比较,根据结果排序。

例如:

[4,5,6,3,2,1]
满有序度:6*5/2=15
有序度:3
逆有序度:12(需要交换12次)
第一次冒泡:[4,5,3,2,1,6]交换3次
第二次冒泡:[4,3,2,1,5,6]交换3次
第三次冒泡:[3,2,1,4,5,6]交换3次
第四次冒泡:[2,1,3,4,5,6]交换2次
第五次冒泡:[1,2,3,4,5,6]交换1次
第六次冒泡:[1,2,3,4,5,6]交换0次

特征:原地排序、稳定排序
时间复杂度:

  • 最好:O(n);
  • 最坏:O(n²);
  • 平均:最好的情况下,有序度就是n(n-1)/2,所以平均可以取中间值O(n(n-1)/4),即为O(n²),这是种好用但是不严格的分析方法。

插入排序(Insertion Sort)

原理:将待排序数据分为两个区间,已排序区和未排序区,然后分别取未排序区数据放入到已排序区。

例如:

[4,5,6,1,3,2]
满有序度:15
有序度:5
逆有序度:10(需要交换10次)
4作为已排序区,剩下的作为未排序区
第一次插入:5>4,位置不变
第二次插入:6>4,位置不变
第三次插入:1<4,将1往前移3位到第一位[1,4,5,6,3,2]
第四次插入:1<3<4,将3往前移3位到第二位[1,3,4,5,6,2]
第五次插入:1<2<3,将2往前移4位到第二位[1,2,3,4,5,6]

特征:原地排序、稳定排序
时间复杂度:

  • 最好:O(n)
  • 最差:O(n²)
  • 平均:O(n²)

选择排序(Selection Sort)

原理:将待排序数据分为两个区间,已排序区和未排序区,每次从未排序区找到最小的元素,将其放到已排序区的末尾。

例如:

[4,5,6,3,2,1]

第一次选择:1和4交换[1,5,6,3,2,4]
第二次选择:2和5交换[1,2,6,3,5,4]
第三次选择:6和3交换[1,2,3,6,5,4]
第四次选择:6和4交换[1,2,3,4,6,5]
第五次选择:6和5交换[1,2,3,4,5,6]

特征:原地排序、非稳定排序(因为交换可能导致前面的数被交换到最后一位)

  • 最好:O(n²)
  • 最差:O(n²)
  • 平均:O(n²)

归并排序(Merge Sort)

原理:分治思想,将大问题分解成小问题,解决小问题以后合并。

例如:

初始:[11,8,3,9,7,1,2,5]
第一次分治:[11,8,3,9] [7,1,2,5]
第二次分治:[11,8][3,9][7,1][2,5]
排序:[8,11][3,9][1,7][2,5]
合并并排序:[3,8,9,11][1,2,5,7]
合并并排序:[1,2,3,5,7,8,9,11]

伪代码:

//归并排序算法,A是数组,n表示数组大小
merge_sort(A,n){
    merge_sort_c(A,0,n-1)
}
//递归调用函数
merge_sort_c(A,p,r){
    //递归终止条件
    if p >= r then return
    q = (p+r)/2
    //分治递归
    merge_sort_c(A,p,q)
    merge_sort_c(A,q+1,r)
    merge(A[p...r],A[p,,,q],A[q+1...r])
}
//合并函数
merge(A[p..r],A[p...q],A[q+1...r]){
    var i := p,j := q + 1,k := 0
    //申请一个大小跟第一个数组长度相等的数组
    var tmp := new array[0...r-p]
    while i <= q AND j <= r do {
        if A[i] <= A[j]{
            tmp[k++] = A[i++]
        }else tmp[k++] = A[j++]
    }
    //判断哪个子数组中有剩余的数据
    var start := i,end := q
    if j<= r then start := j, end := r

    //将剩余数据拷贝到临时数组tmp
    while start <= end do {
        tmp[k++] = A[start++]
    }
    //将tmp中数组拷贝回A[p...r]
    for i:=0 to r-p do {
        A[p+i] = tmp[i]
    }
}

类型:非原地排序,非稳定排序(空间复杂度O(n))
复杂度:

  • 任何情况下都是O(nlogn)

快速排序(Quick Sort)

原理:分治思想,选择待排序数据中的任意一点作为pivot分区点,然后对左右两个分区执行递归,直到分区缩小为1。

快速排序主要难点在于分区函数的实现,可以使用如下伪代码来实现分区:

partition(A,p,r){
    pivot := A[r]
    i := p
    for j := p to r - 1 do{
        if A[j] < pivot{
            swap A[i] with A[j]
            i := i + 1
        }
    }
    swap A[i] with A[r]
    return i 
}

时间复杂度:

  • 最好:O(nlogn)
  • 最坏:O(n²)

快速排序的顺序是从大问题开始,而归并排序是从小问题开始,最后合并结果,而且快拍是可以原地排序的,所以应用范围大于归并排序。

桶排序(Bucket sort)

原理:将要排序的n个数据均匀地分到m个桶内,对每个桶内的元素进行快排。时间复杂度O(n)为m个桶乘以每个桶的时间复杂度O(n/m*log(n/m)),将m带入到括号即为O(nlog(n/m)),如果桶的数量m无限接近于n时,log(n/m)则是一个常数。所以桶排序的时间复杂度接近O(n)。

虽然桶排序的时间复杂度看起来很低,但是不能替代之前的排序算法,因为要求桶和桶之间有着天然的大小顺序,并且数据在各个桶之间的分布是比较均匀的,极端情况下会退化为O(nlogn)。

桶排序适用于外部排序中,即将数据存储在外部磁盘中,数据量大的场景,例如对10个G的订单数据进行排序,可以按照订单价格区间放入到100个文件中。

计数排序(Counting sort)

原理:可以将计数排序理解为特殊的桶排序,当要处理数据所处范围不大的时候,可以将其分成固定数量的桶。

例如:

A[2,5,3,0,2,3,0,3]
数字范围从0到5,可以再申请一个数组C计算每个元素出现次数,数组中的元素记录待排序数据出现的次数,下标代表待排序数据的值:[2,0,2,3,0,1],此时对该数组内的值进行求和得到[2,2,4,7,7,8],接下来就到了关键的一步;

取出A[0],该值为2,则它应该放在已排序数组R第4位(下标为3的位置),而此时C[2]的值应该减1变成4,再取出A[1],此时应该放在已排序数组R第8位(下标为7的位置),依此类推;

当A数组遍历完的时候,R数组中所有数据都是有序的了。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public void countingSort(int[] a,int n){
if(n < 1) return;
//找到待排序数组中最大值
int max = a[0];
for(int i = 1;i<n;i++){
if(max < a[i]) max = a[i];
}
//声明一个能容纳最大值范围内所有数据的数组c,计算每个数出现次数
int[] c = new int[max+1];
for(int i = 0;i< = max;i++){
c[i] = 0;
}
//遍历a数组,每出现一次,C数组对应下标的数+1
for(int i = 0;i<n;i++){
c[a[i]]++;
}
//将c数组的数求和
for(int i = 1;i<=max;i++){
c[i] = c[i-1]+c[i];
}
//存放排序后的数
int[] r = new int[n];
for(int i = n -1;i>0;i--){
int index = c[a[i]] - 1;
r[index] = a[i];
c[a[i]]--;
}
//将排序后的数放回到原数组
for(int i = 0;i < n;i++){
a[i] = r[i];
}
}

应用场景:只能用在数据范围不大的场景,如果范围k比待排序数据的数量大的多,就不适合这种排序,而且它不能排序负数,

基数排序(Radix Sort)

原理:例如10万个手机号,排序可以按照最后一位依此往前排序,经过11次排序以后,所有手机号就都是有序的了,并且保证了稳定排序,时间复杂度是O(k*n),这里的k是指手机号有11位,n是数据量10万就,所以其时间复杂度近似于O(n)。如果不从最后一位低位开始排序,而从高位开始排序,就不是稳定排序了。

应用场景:对排序的数据有要求,需要可以分割出独立的”位“来比较,而且位之间有递进关系,每一位的访问不能太大,要用线性排序来排序,不然做不到O(n)的时间复杂度。

总结

如何选择合适的排序算法:

  1. 如果数据量不大,可以选择O(n²)复杂度的排序算法;如果数据量大,选择O(nlogn)复杂度的排序算法,所以O(nlogn)优先;
  2. 快速排序选择的pivotal尽量能够使得两个分区数量差不多,可以使用三数取中法,即从区间首、尾、中间分别取数然后对比大小,取三个数的中间值作为分区点;
  3. 可以多种排序算法结合,例如小数据量使用归并排序;大数据量使用快速排序。有时候数据极少时,还可以退化为插入排序,因为复杂度为O(n²)的排序在数据量极少时,不一定比时间复杂度为O(nlogn)的算法的执行时间长。

参考

本节相关的学习代码参考github:

https://github.com/liuhuijun11832/algorithm

坚持原创、技术分享。请作者喝杯茶吧!