算法分类

https://www.jianshu.com/p/b5b1b8e1747f
https://www.jianshu.com/p/d93c074b1a41

简介

常用的算法包含但不限于以下几种：

• 分治：分而治之，将问题拆解为形式相同子问题处理，然后合并为原问题解；
• 穷举：无差别例举每一种可能解；
• 迭代：不断用变量的旧值推出新值；
• 回溯：按条件走，走不通就退回重新再走，回溯的核心在递归；
• 贪心：将问题拆解为子问题来处理，每一步都先考虑当前最优（贪心）选择；
• 动态规划：将问题拆解为子问题来处理，整理问题的最优解依赖各个子问题的最优解，自下而上求解，需要记录之前的所有局部最优解；

下面比价经典的案例：

一、排序算法总览

排序大的分类可以分为两种：内排序和外排序。在排序过程中，全部记录存放在内存，则称为内排序，如果排序过程中需要使用外存，则称为外排序。下面讲的排序都是属于内排序。内排序有可以分为以下几类：

(1)、插入排序：直接插入排序、二分法插入排序、希尔排序。
(2)、选择排序：简单选择排序、堆排序。
(3)、交换排序：冒泡排序、快速排序。
(4)、归并排序。
(5)、线性时间排序：计数排序、基数排序、桶排序。
算法复杂度以及稳定性分析

image.png

1.1、直接插入排序（Insertion Sort）

基本思想：将数组中的所有元素依次跟前面已经排好的元素相比较，如果选择的元素比已排序的元素小，则交换，直到全部元素都比较过为止。
算法描述：
① 从第一个元素开始，该元素可以认为已经被排序
② 取出下一个元素，在已经排序的元素序列中从后向前扫描
③ 如果该元素（已排序）大于新元素，将该元素移到下一位置
④ 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
⑤ 将新元素插入到该位置后
⑥ 重复步骤② ~ ⑤
代码实现：

public static void sort(int[] a) {
    for (int i = 0; i < a.length - 1; i++) {
        for (int j = i + 1; j > 0; j--) {
            if (a[j] < a[j - 1]) {   //交换
                int temp = a[j];
                a[j] = a[j - 1];
                a[j - 1] = temp;
            }
        }
    }
}

效果图如下：

image.png

1.2、希尔排序（Shell Sort）

基本思想：将待排序数组按照步长gap进行分组，然后将每组的元素利用直接插入排序的方法进行排序；每次再将gap折半减小，循环上述操作；当gap=1时，利用直接插入，完成排序。
可以看到步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。一般来说最简单的步长取值是初次取数组长度的一半为增量，之后每次再减半，直到增量为1。
算法描述：
① 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；（一般初次取数组半长，之后每次再减半，直到增量为1）
② 按增量序列个数k，对序列进行k 趟排序；
③ 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1时，整个序列作为一个表来处理，表长度即为整个序列的长度。
代码实现：

public static void sort(int[] a) {
    int length = a.length;
    int h = 1;
    while (h < length / 3) h = 3 * h + 1;
    for (; h >= 1; h /= 3) {
        for (int i = 0; i < a.length - h; i += h) {
            for (int j = i + h; j > 0; j -= h) {
                if (a[j] < a[j - h]) {
                    int temp = a[j];
                    a[j] = a[j - h];
                    a[j - h] = temp;
                }
            }
        }
    }
}

效果图如下：

image.png

1.3 选择排序（Selection Sort）

基本思想：
选择排序的基本思想：比较 + 交换。
在未排序序列中找到最小（大）元素，存放到未排序序列的起始位置。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。
算法描述：
① 从待排序序列中，找到关键字最小的元素；
② 如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换；
③ 从余下的 N - 1 个元素中，找出关键字最小的元素，重复① 、② 步，直到排序结束。
代码实现

public static void selectionSort(int[] arr){
    for(int i = 0; i < arr.length-1; i++){
        int min = i;
        for(int j = i+1; j < arr.length; j++){    //选出之后待排序中值最小的位置
            if(arr[j] < arr[min]){
                min = j;
            }
        }
        if(min != i){
            int temp = arr[min];      //交换操作
            arr[min] = arr[i];
            arr[i] = temp;
            System.out.println("Sorting:  " + Arrays.toString(arr));
        }
    }
}

效果图如下：

image.png

1.4 堆排序（Heap Sort）

基本思想：
此处以大顶堆为例，堆排序的过程就是将待排序的序列构造成一个堆，选出堆中最大的移走，再把剩余的元素调整成堆，找出最大的再移走，重复直至有序。
算法描述：
① 先将初始序列建成一个大顶堆, 那么此时第一个元素最大, 此堆为初始的无序区.
②再将关键字最大的记录 (即堆顶, 第一个元素)和无序区的最后一个记录交换, 由此得到新的无序区和有序区, 且满足
③交换和后, 堆顶可能违反堆性质, 因此需将调整为堆. 然后重复步骤②, 直到无序区只有一个元素时停止。
代码实现

public static void sort(int[] a) {

    for (int i = a.length - 1; i > 0; i--) {
        max_heapify(a, i);

        //堆顶元素(第一个元素)与Kn交换
        int temp = a[0];
        a[0] = a[i];
        a[i] = temp;
    }
}

/***
 *
 *  将数组堆化
 *  i = 第一个非叶子节点。
 *  从第一个非叶子节点开始即可。无需从最后一个叶子节点开始。
 *  叶子节点可以看作已符合堆要求的节点，根节点就是它自己且自己以下值为最大。
 *
 * @param a
 * @param n
 */
public static void max_heapify(int[] a, int n) {
    int child;
    for (int i = (n - 1) / 2; i >= 0; i--) {
        //左子节点位置
        child = 2 * i + 1;
        //右子节点存在且大于左子节点，child变成右子节点
        if (child != n && a[child] < a[child + 1]) {
            child++;
        }
        //交换父节点与左右子节点中的最大值
        if (a[i] < a[child]) {
            int temp = a[i];
            a[i] = a[child];
            a[child] = temp;
        }
    }
}

效果图如下：

image.png

1.5 冒泡排序（Bubble Sort）

基本思想：
冒泡排序（Bubble Sort）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
算法描述：
① 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
② 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
③ 针对所有的元素重复以上的步骤，除了最后一个。
④ 持续每次对越来越少的元素重复上面的步骤① ~ ③ 直到没有任何一对数字需要比较。
代码实现：

public static void bubbleSort(int[] arr){
    for (int i = arr.length; i > 0; i--) {      //外层循环移动游标
        for(int j = 0; j < i && (j+1) < i; j++){    //内层循环遍历游标及之后(或之前)的元素
            if(arr[j] > arr[j+1]){
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
                System.out.println("Sorting: " + Arrays.toString(arr));
            }
        }
    }
}

效果图如下：

image.png

1.6 快速排序（Quick Sort）

基本思想：
快速排序的基本思想：挖坑填数+分治法。
首先选一个轴值(pivot，也有叫基准的)，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
算法描述：
① 从数列中挑出一个元素，称为”基准”（pivot）。
② 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
③ 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归到最底部时，数列的大小是零或一，也就是已经排序好了。

代码实现

public static void sort(int[] a, int low, int high) {
    //已经排完
    if (low >= high) {
        return;
    }
    int left = low;
    int right = high;

    //保存基准值
    int pivot = a[left];
    while (left < right) {
        //从后向前找到比基准小的元素
        while (left < right && a[right] >= pivot)
            right--;
        a[left] = a[right];
        //从前往后找到比基准大的元素
        while (left < right && a[left] <= pivot)
            left++;
        a[right] = a[left];
    }
    // 放置基准值，准备分治递归快排
    a[left] = pivot;
    sort(a, low, left - 1);
    sort(a, left + 1, high);
}

效果图如下：

image.png

1.7 归并排序（Merging Sort）

基本思想：
归并排序算法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
算法描述：
归并排序可通过两种方式实现：
自上而下的递归
自下而上的迭代
一、递归法（假设序列共有n个元素）：
① 将序列每相邻两个数字进行归并操作，形成 floor(n/2)个序列，排序后每个序列包含两个元素；
② 将上述序列再次归并，形成 floor(n/4)个序列，每个序列包含四个元素；
③ 重复步骤②，直到所有元素排序完毕。
二、迭代法
① 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
② 设定两个指针，最初位置分别为两个已经排序序列的起始位置
③ 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
④ 重复步骤③ 直到某一指针到达序列尾
⑤ 将另一序列剩下的所有元素直接复制到合并序列尾
代码实现：

public static int[] mergingSort(int[] arr){
    if(arr.length <= 1) return arr;

    int num = arr.length >> 1;
    int[] leftArr = Arrays.copyOfRange(arr, 0, num);
    int[] rightArr = Arrays.copyOfRange(arr, num, arr.length);
    System.out.println("split two array: " + Arrays.toString(leftArr) + " And " + Arrays.toString(rightArr));
    return mergeTwoArray(mergingSort(leftArr), mergingSort(rightArr));      //不断拆分为最小单元，再排序合并
}

private static int[] mergeTwoArray(int[] arr1, int[] arr2){
    int i = 0, j = 0, k = 0;
    int[] result = new int[arr1.length + arr2.length];  //申请额外的空间存储合并之后的数组
    while(i < arr1.length && j < arr2.length){      //选取两个序列中的较小值放入新数组
        if(arr1[i] <= arr2[j]){
            result[k++] = arr1[i++];
        }else{
            result[k++] = arr2[j++];
        }
    }
    while(i < arr1.length){     //序列1中多余的元素移入新数组
        result[k++] = arr1[i++];
    }
    while(j < arr2.length){     //序列2中多余的元素移入新数组
        result[k++] = arr2[j++];
    }
    System.out.println("Merging: " + Arrays.toString(result));
    return result;
}

效果图如下：

image.png

1.8 基数排序（Radix Sort）

基本思想：
它是这样实现的：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。
基数排序按照优先从高位或低位来排序有两种实现方案： `` MSD（Most significant digital）从最左侧高位开始进行排序。先按k1排序分组, 同一组中记录, 关键码k1相等, 再对各组按k2排序分成子组, 之后, 对后面的关键码继续这样的排序分组, 直到按最次位关键码kd对各子组排序后. 再将各组连接起来, 便得到一个有序序列。MSD方式适用于位数多的序列。
LSD （Least significant digital）从最右侧低位开始进行排序。先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。LSD方式适用于位数少的序列。
算法描述：
我们以LSD为例，从最低位开始，具体算法描述如下：

① 取得数组中的最大数，并取得位数；
② arr为原始数组，从最低位开始取每个位组成radix数组；
③ 对radix进行计数排序（利用计数排序适用于小范围数的特点）；
代码实现：

public static void radixSort(int[] arr){
    if(arr.length <= 1) return;

    //取得数组中的最大数，并取得位数
    int max = 0;
    for(int i = 0; i < arr.length; i++){
        if(max < arr[i]){
            max = arr[i];
        }
    }
    int maxDigit = 1;
    while(max / 10 > 0){
        maxDigit++;
        max = max / 10;
    }
    System.out.println("maxDigit: " + maxDigit);

    //申请一个桶空间
    int[][] buckets = new int[10][arr.length];
    int base = 10;

    //从低位到高位，对每一位遍历，将所有元素分配到桶中
    for(int i = 0; i < maxDigit; i++){
        int[] bktLen = new int[10];        //存储各个桶中存储元素的数量
        
        //分配：将所有元素分配到桶中
        for(int j = 0; j < arr.length; j++){
            int whichBucket = (arr[j] % base) / (base / 10);
            buckets[whichBucket][bktLen[whichBucket]] = arr[j];
            bktLen[whichBucket]++;
        }

        //收集：将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞
        int k = 0;
        for(int b = 0; b < buckets.length; b++){
            for(int p = 0; p < bktLen[b]; p++){
                arr[k++] = buckets[b][p];
            }
        }

        System.out.println("Sorting: " + Arrays.toString(arr));
        base *= 10;
    }
}

效果图如下：

image.png

总结

从时间复杂度来说：
(1). 平方阶O(n²)排序：各类简单排序：直接插入、直接选择和冒泡排序；
(2). 线性对数阶O(nlog₂n)排序：快速排序、堆排序和归并排序；
(3). O(n1+§))排序，§是介于0和1之间的常数：希尔排序
(4). 线性阶O(n)排序：基数排序

当原表有序或基本有序时，直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数，时间复杂度可降至O（n）；
而快速排序则相反，当原表基本有序时，将蜕化为冒泡排序，时间复杂度提高为O（n2）；
原表是否有序，对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

本文参考：
https://www.cnblogs.com/morethink/p/8419151.html
https://www.cnblogs.com/winterfells/p/9436882.html