算法思想

Posted on Edited on In

十大经典排序算法

1. 冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function bubbleSort(arr) {
    int len = arr.length;
    for (int i = 0; i < len - 1; i++) {
	// 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成。
        boolean flag = true;
        for (int j = 0; j < len - 1 - i; j++) {
            if (arr[j] > arr[j+1]) {        // 相邻元素两两对比
                int temp = arr[j+1];        // 元素交换
                arr[j+1] = arr[j];
                arr[j] = temp;
            }
        }
	if (flag) {
           break;
        }
    }
    return arr;
}

在比较交换的时候可以让相同的元素不发生交换，因此冒泡是一个稳定的排序算法。但是每次交换冒泡需要赋值三次，效率不如其他算法。

2. 选择排序

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function selectionSort(arr) {
    var len = arr.length;
    var minIndex, temp;
    for (var i = 0; i < len - 1; i++) {
        minIndex = i;
        for (var j = i + 1; j < len; j++) {
            if (arr[j] < arr[minIndex]) {     // 寻找最小的数
                minIndex = j;                 // 将最小数的索引保存
            }
        }
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
    return arr;
}

选择排序每次都要找剩余未排序元素中的最小值，并和前面的元素交换位置，这样破坏了稳定性。

3. 插入排序

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void insertionSort(int[] a, int n) {
    if (n <= 1) return;
    for (int i = 1; i < n; ++i) {
        int value = a[i];
        int j = i - 1;
        // 查找插入的位置
        for (; j >= 0; --j) {
            if (a[j] > value) {
                a[j + 1] = a[j]; // 数据移动
            } else {
                break;
            }
        }
        a[j + 1] = value; // 插入数据
    }
}

插入排序在移动元素的时候只需一次，因此它的效率比冒泡要好，同时也是一种稳定的排序算法。

4. 希尔排序

希尔排序，也称缩小增量排序，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录”基本有序”时，再对全体记录进行依次直接插入排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function shellSort(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;
        }
    }
}

5. 归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。分治是一种解决问题的处理思想，递归是一种编程技巧

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
function mergeSort(arr) {
    var len = arr.length;
    if (len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}
 
function merge(left, right) {
    var result = [];
 
    while (left.length>0 && right.length>0) {
        if (left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
 
    while (left.length)
        result.push(left.shift());
 
    while (right.length)
        result.push(right.shift());
 
    return result;
}

归并排序稳不稳定关键要看merge() 函数，在合并的过程中，如果A[p…q]和A[q+1…r]之间有值相同的元素，可以先把A[p…q]中的元素放入 tmp 数组。这样就保证了值相同的元素，在合并前后的先后顺序不变。所以，归并排序是一个稳定的排序算法。

归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，**不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)。实际上，递归代码的空间复杂度并不能像时间复杂度那样累加。尽管每次合并操作都需要申请额外的内存空间，但在合并完成之后，临时开辟的内存空间就被释放掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个临时的内存空间在使用。临时内存空间最大也不会超过 n 个数据的大小，所以空间复杂度是 O(n)**。

6. 快速排序

快速排序的基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

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
public int[] sortArray(int[] nums) {
        quicksort(nums,0,nums.length-1);
        return nums;
    }
    void quicksort(int[] nums,int left,int right){
        if(left>=right) return;
        int index=help(nums,left,right);
        quicksort(nums,left,index-1);
        quicksort(nums,index+1,right);
    }
    int help(int[] nums,int left,int right){
        int t=nums[right];
        int index=left;
        for(int i=left;i<right;i++){
            if(nums[i]<t){
                swap(nums,index,i);
                index++;
            }
        }
        swap(nums,index,right);
        return index;
    }
    void swap(int[] nums,int a,int b){
        int t=nums[a];
        nums[a]=nums[b];
        nums[b]=t;
    }

因为分区的过程涉及交换操作，如果数组中有两个相同的元素在经过第一次分区操作之后，两个元素的相对先后顺序就会改变。所以，快速排序并不是一个稳定的排序算法。

如果数组中的数据原来已经是有序的了，比如 1，3，5，6，8。如果每次选择最后一个元素作为 pivot，那每次分区得到的两个区间都是不均等的。需要进行大约 n 次分区操作，才能完成快排的整个过程。每次分区我们平均要扫描大约 n/2 个元素，这种情况下，快排的时间复杂度就从 O(nlogn) 退化成了 O(n^2)。

二分搜索

1. 寻找左侧边界的二分搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int left_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    // 搜索区间为 [left, right]
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            // 搜索区间变为 [mid+1, right]
            left = mid + 1;
        } else if (nums[mid] > target) {
            // 搜索区间变为 [left, mid-1]
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 收缩右侧边界
            right = mid - 1;
        }
    }
    // 检查出界情况
    if (left >= nums.length || nums[left] != target)
        return -1;
    return left;
}

注意 :

  1. left + (right - left) / 2和(left + right) / 2的结果相同，但是有效防止了 left 和 right 太大直接相加导致溢出。
  2. 左右边界，mid，取值。

while循环的条件

初始化 right 的赋值是 nums.length - 1，即最后一个元素的索引，而不是 nums.length。

这二者可能出现在不同功能的二分查找中，区别是：前者相当于两端都闭区间 [left, right]，这个区间其实就是每次进行搜索的区间。后者相当于左闭右开区间 [left, right)，因为索引大小为 nums.length 是越界的。

边界判断

由于 while 的退出条件是 left == right + 1，区间的形式就是 [right + 1, right]，所以当 target 比 nums 中所有元素都大时，会存在以下情况使得索引越界,因此，最后返回结果的代码应该检查越界情况

2. 寻找右侧边界的二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int right_bound(int[] nums, int target) {
    int left = 0, right = nums.length - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] < target) {
            left = mid + 1;
        } else if (nums[mid] > target) {
            right = mid - 1;
        } else if (nums[mid] == target) {
            // 这里改成收缩左侧边界即可
            left = mid + 1;
        }
    }
    // 这里改为检查 right 越界的情况
    if (right < 0 || nums[right] != target)
        return -1;
    return right;
}

回溯算法(DFS)

回溯算法其实就是DFS算法，本质上就是一种暴力穷举算法。采用试错的思想，尝试分步的去解决问题。在分步解决问题的过程中，它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。代码框架如下所示：

  1. 路径：也就是已经做出的选择。

  2. 选择列表：也就是你当前可以做的选择。

  3. 结束条件：也就是到达决策树底层，无法再做选择的条件。

1
2
3
4
5
6
7
8
9
10
result = []
def backtrack(路径, 选择列表):
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        做选择
        backtrack(路径, 选择列表)
        撤销选择

要在递归之前做出选择，在递归之后撤销刚才的选择，就能正确得到每个节点的选择列表和路径。

BFS算法

把一些问题抽象成图,本质就是在一幅图中找到从起点 start 到终点 target 的最近距离，但是空间复杂度高，而 DFS 的空间复杂度较低。

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
// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路
    
    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

cur.adj() 泛指 cur 相邻的节点，比如说二维数组中，cur 上下左右四面的位置就是相邻节点；visited 的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要 visited

动态规划

动态规划问题的一般形式就是求最值，核心问题是穷举。动态规划存在重叠子问题和最优子结构，可以通过dp数组来进行剪枝优化，最后写出状态转移方程。

1
2
3
4
5
6
7
# 初始化 base case
dp[0][0][...] = base
# 进行状态转移
for 状态1 in 状态1的所有取值：
    for 状态2 in 状态2的所有取值：
        for ...
            dp[状态1][状态2][...] = 求最值(选择1，选择2...)

贪心算法

贪心算法是动态规划算法的一个特例，相比动态规划，使用贪心算法需要满足更多的条件（贪心选择性质），但是效率比动态规划要高。

++贪心选择性质：每一步都做出一个局部最优的选择，最终的结果就是全局最优。++

分治算法

分治算法通过将原问题分解成小规模的子问题，然后根据子问题的结果构造出原问题的答案。分治算法也需要满足一些条件，原问题结果应可以通过合并子问题结果来计算。

  1. 不思考整体，而是把目光聚焦局部
  2. 明确递归函数的定义是什么，相信并且利用好函数的定义