2021-09-18

算法与数据结构笔记

1. 关于算法的时间/空间复杂度

Big-O	名称	描述
O(1)	恒定（Constant）	最好，程序执行的结果与输入数据量大小无关，总是需要相同的时间/空间量，例如：用索引查找数组元素。
O(logN)	对数（Constant）	非常好，时间或空间性能与输入呈对数比例增长。即使对于大量的数据，这也是非常快的。例子：二进制搜索。
O(n)	线性（Linear）	良好，时间或空间性能与输入呈对数比例增长。例子：顺序搜索。
O(NlogN)	线性化（Linearithmic）	不错，比线性略差，但也不坏。
O(N^2))	平方（Quadratic）	较慢，时间或空间性能与输入呈平方比例增长。通常使用两层嵌套循环的算法都属于此类，如：插入排序、冒泡排序。
O(N^3)	立方（Cubic）	不佳，时间或空间性能与输入呈平方比例增长。如：矩阵乘法。
O(2^N)	指数级（Exponential）	非常差，输入的少量增加即可使得运行事件加倍。如：旅行推销员问题。
O(N!)	阶乘（Factorial）	不能忍受，做任何事情都需要一百万年的时间。

1.1 O(1) - 固定时间/空间（Constant）

O(1)表示无论输入的大小怎样，一个算法都将在相同的时间或空间内完成。

1	int n = 1000;

1.2 O(n) - 线性

O(1)表示一个算法的时间或空间与输入呈线性比例增长。

1
2
3

for (int i =0; i < n; i++) {
    // some constant time operation
}

1.3 O(n^2) - 平方

O(n^2)表示一个算法的时间或空间性能与输入呈平方比例增长。

for (int i = 0; i < n; i++) {
  for (int j = 0; j < n; j++) {
    // some constant time operation
  }
}

1.4 O(log n) - 对数

O(log n) 表示一个算法的时间或空间性能与输入呈对数比例增长。

1
2
3

for (int i = 0; i < n; i *= 2) {
    // some constant time operation
}

1.5 O(NlogN) 线性化（linearithmic）

线性化算法对于非常大的数据量来说但是比较好的，比如快速排序、归并排序、堆排序等。

for (int i = 0; i < n; i++ )
    for (int j = 1; j < n; j *= 2) {
        // some constant time operation
    }
}

总结：
算法的复杂度分析可以帮助你理解一个算法的事件或者空间性能，上面各种复杂度放在一起比较可以有一个直观的认识：

2. 排序算法

2.1 冒泡排序

依次比较相邻的两个数，较小数放前面，较大数放后面，直到最大数放在最后，然后重复操作，最后排序为升序。

演示：

第一层循环为重复的次数，循环次数为array.length-1

第二次循环为依次比较相邻的数，循环次数为array.length-1-i

for (int i = 0; i < arr.length - 1; i++){
  for (int j = 0; j<arr.length - i -1; j++){
    if (arr[j] > arr[j+1]){
      swap(arr, j, j+1);
    }
  }
}

2.2 选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕。

动图演示

public void sort(int[] arr) {
  // 总共需要N-1轮比较
  for(int i = 0; i <arr.length - 1; i++){
    int min = i;    // 最小值位置

    // 每轮需要比较的次数（N-i）
    for (int j = i+1; j<arr.length; j++) {
      if (arr[j]< arr[min]){
        min = j;    // 记录最小值索引
      }
    }

    // 每轮将找到的最小值和i位置所在的值进行交换
    if (i != min){
      swap(arr, i, min);
    }
  }
}

2.3 插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

演示：

public void sort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {   // 从第2个元素开始遍历，默认第一个元素为有序的。
        int key = arr[i];   // 记录要插入的数据

        // 从已经排序的序列的最右边开始比较，找到比其小的数
        int j = i;
        while (j > 0 && key < arr[j - 1]) {
            arr[j] = arr[j - 1];
            j--;
        }
        // 存在比其小的数，插入
        if (j != i)
            arr[j] = key;
    }
}

[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]

第一轮：

i = 1
key = arr(1) = 1

j 由 1 循环至 0
[[6], (1), 2, 7, 9, 3, 4, 5, 10, 8]
满足j>0并且key<6, 则：
arr[j] = arr[j-1]
[[6], (6), 2, 7, 9, 3, 4, 5, 10, 8]
j--;(执行后j=0)

j(0)<i(1) ,说明存在比其小的数，则执行插入
arr[j] = key;
[[1], (6), 2, 7, 9, 3, 4, 5, 10, 8]

第二轮

i = 2;
key = arr(2) = 2
j初始=i=2，由右侧向左遍历
[[1, 6], (2), 7, 9, 3, 4, 5, 10, 8]

满足key < arr[j - 1] ，即2<arr(1) = 6, 则：
arr[j] = arr[j-1]
[[1, 6], (6), 7, 9, 3, 4, 5, 10, 8]
继续向左遍历j=1时，不满足key < arr[j - 1] ，即2< arr(0) = 1 条件不成立，因此本轮循环结束后j=1
插入：
[[1, 2, 6], 7, 9, 3, 4, 5, 10, 8]

2.4 希尔排序

通过增量(gap)将元素两两分组，对每组使用直接插入排序算法排序；增量(gap)逐渐减少，当增量(gap)减至1时，整个数据恰被分成一组，最后进行一次插入排序，整个数组就有序了。

演示：

第一轮：

第二轮：

第三轮：

参考https://zhuanlan.zhihu.com/p/122472667

代码：

public void sort(int[] arr) {
    int length = arr.length;
    int temp;
    for (int step = length / 2; step >= 1; step /= 2) {
        for (int i = step; i < length; i++) {
            temp = arr[i];
            int j = i - step;
            while (j >= 0 && arr[j] > temp) {
                arr[j + step] = arr[j];
                j -= step;
            }
            arr[j + step] = temp;
        }
    }
}

2.5 归并排序

演示：

2.6 快速排序

算法思想：选择序列中一个元素作为基准元素base，维护两个指针front和back分别指向序列的首尾，

首先用front指向的元素和base进行比较，如果大于base，则与back指向的元素进行交换，否则指针右移；

然后比较back指向的元素是否小于base，返回为true则与front指向的元素进行交换，否则指针左移。

前后交替这样就能保证较小数都放在base的左边，较大数在base的右边，然后递归调用对各部分继续排序，直到最后排好序。

public void sort(int[] sourceArray) {
    quickSort(sourceArray, 0, sourceArray.length - 1);
}

private void quickSort(int[] arr, int left, int right) {

    if (left > right)
        return;

    int i = left;
    int j = right;
    int pivot = arr[left];  // 取第一个元素作为基准

    while (i!=j){
        while (i<j && arr[j] >= pivot)  // 这里需要注意：一定要右侧先开始移动！
            j--;
        while (i<j && arr[i] <= pivot)
            i++;
        if (i<j)
            swap(arr, i, j);
    }
    arr[left] = arr[i];
    arr[i] = pivot;
    System.out.println(Arrays.toString(arr));
    quickSort(arr, left, i - 1);
    quickSort(arr, i+1, right);
}

1	[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]

第一轮：

基准为6：左边找个大的，右边找个小的：
[6, 1, 2, (7), 9, 3, 4, (5), 10, 8]
交换后：
[6, 1, 2, (5), 9, 3, 4, (7), 10, 8]

继续左边找个大的，右边找个小的：
[6, 1, 2, 5, (9), 3, (4), 7, 10, 8]
交换后：
[6, 1, 2, 5, (4), 3, (9), 7, 10, 8]

交换pivot和patation index
[（6）, 1, 2, 5, 4, (3), 9, 7, 10, 8]
交换后：
[（3）, 1, 2, 5, 4, (6), 9, 7, 10, 8]
这样交换之后，就以pivot（6）为分界，左边都比6小，右边都比6大
[3, 1, 2, 5, 4]  6, [9, 7, 10, 8]

然后两边再次递归使用快速排序，知道每个patation都只有一个元素为止。

第二轮(左边)：

[3, 1, 2, 5, 4]

右边找个小的，左边没找到，i和j碰头在元素2上面
[3, 1, (2), 5, 4]
则交换（2）和pivot（3）后：
[2, 1, 3, 5, 4]
分成
[2, 1], 3, [5, 4]

第三轮(左边)：

1
2
3

[2, 1]
交换后：
[1, 2]

第四轮(左边)：

1
2
3

[5, 4]
交换后：
[4, 5]

至此，第一轮左边patition部分均已排序完成

第五轮（右边）：

[9, 7, 10, 8]

[9, 7, (10), (8)]
交换后
[9, 7, (8), (10)]
右侧继续移动后，找到patition index元素，与pivot进行交换
[(9), 7, (8), 10]
交换后：
[(8), 7, (9), 10]

[8, 7], 9 [10]

第六轮（右边）：

1
2
3

[8, 7]
交换后：
[7, 8]

GeekHour

One hour technology tutorials