递归与排序——冒泡、插入和选择

递归

递归代码都可以改为这种迭代循环的非递归写法。例如

1
2
3
4
5
6
7
8
9
10
f(x) =f(x-1)+1

改为
int f(int n) { 
    int ret = 1; 
    for (int i = 2; i <= n; ++i) { 
        ret = ret + 1;
    }
    return ret;
}

因为递归本身就是借助栈来实现的，只不过我们使用的栈是系统或者虚拟机本身提供的，我们没有感知罢了。如果我们自己在内存堆上实现栈，手动模拟入栈、出栈过程，这样任何递归代码都可以改写成看上去不是递归代码的样子。但是这种思路实际上是将递归改为了“手动”递归，本质并没有变

递归代码虽然简洁高效，但是，递归代码也有很多弊端。比如，堆栈溢出、重复计算、函数调用耗时多、空间复杂度高等，所以，在编写递归代码的时候，一定要控制好这些副作用。

排序

排序算法 时间复杂度 是否基于比较
冒泡、插入、选择 O(n2) - [x]
快排、归并 O(nlogn) 是
桶、计数、基数 O(n) 否
时间复杂度 是否稳定排序 是否原地排序
冒泡 O(n2) 是 是
插入 O(n2) 是 是
选择 O(n2) 否 是
快排 O(nlogn) 否 是
归并 O(nlogn) 是 否
计数 O(n+k) k是数据范围 是 否
桶 O(n) 是 否
基数 O(dn) d是维度 是 否

分析“排序算法”

1排序算法的执行效率

a.最好情况、最坏情况、平均情况时间复杂度

b.时间复杂度的系数、常数 、低阶

c. 比较次数和交换（或移动）次数

2.排序算法的内存消耗

3.排序算法的稳定性

冒泡、插入、选择

冒泡法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
354126  当某次冒泡操作已经没有数据交换时，说明已经达到完全有序，不用再继续执行后续的冒泡操作

// 冒泡排序，a表示数组，n表示数组大小
public void bubbleSort(int[] a, int n) {
  if (n <= 1) return;
 
 for (int i = 0; i < n; ++i) {
    // 提前退出冒泡循环的标志位
    boolean flag = false;
    for (int j = 0; j < n - i - 1; ++j) {
      if (a[j] > a[j+1]) { // 交换
        int tmp = a[j];
        a[j] = a[j+1];
        a[j+1] = tmp;
        flag = true;  // 表示有数据交换      
      }
    }
    if (!flag) break;  // 没有数据交换，提前退出
  }
}

插入排序：

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描；

在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
354126
// 插入排序，a表示数组，n表示数组大小

  <?php
  $arr = [2, 3, 1, 6, 4, 7, 5, 9];
  function insertSort($arr) {
      $len = count($arr);   //8
      for ($i = 1; $i < $len; $i++) {
          $key = $arr[$i]; // 记录当前值
         $pos = $i;
         while ($pos > 0 && $arr[$pos - 1] > $key) { //每个值与当前值进行比较
             $arr[$pos] = $arr[$pos - 1];// 当前值  =  前一个值    移动数据
             $pos = $pos - 1;
            }
           $arr[$pos] = $key; // 跳出循环赋值   插入
     }
     return $arr;
}

选择排序：

选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。

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
<?php

$arr = [33, 24, 8, 21, 2, 23, 3, 32, 16];

function selectSort($arr)
{
    $count = count($arr); //9
    
    for ($i = 0; $i < $count - 1; $i++) {
        $key = $i;  // 最小索引记录
        for ($k = $i + 1; $k < $count; $k++) {
            // 比较值，得到最小索引
            if ($arr[$key] > $arr[$k]) {
                $key = $k;
            }
        }

        if ($key != $i) {
            // 值交换
            $temp = $arr[$key];
            $arr[$key] = $arr[$i];
            $arr[$i] = $temp;
        }
    }

    return $arr;
}

插入排序比冒泡排序更受欢迎的原因：

冒泡排序需要 3 个赋值操作，而插入排序只需要 1 个

以java测试：

1
随机生成 10000 个数组，每个数组中包含 200 个数据，然后在机器上分别用冒泡和插入排序算法来排序，冒泡排序算法大约 700ms 才能执行完成，而插入排序只需要 100ms 左右就能搞定！

冒泡排序和插入排序在时间复杂度上是一样的，都是 O(n2)，但是如果我们希望把性能优化做到极致，那肯定首选插入排序

排序名 是否原地排序 是否稳定 最好 最坏 平均
冒泡 是 是 O(n) O(n2) O(n2)
插入 是 是 O(n) O(n2) O(n2)
选择 是 否 O(n2) O(n2) O(n2)

冒泡、插入、选择适合小规模数据排序。

以上学于极客时间，做的笔记