luo-frontend / leetcode-javascript Goto Github PK

强烈推荐：
    博客园：https://www.cnblogs.com/onepixel/p/7674659.html
    
参考资料：
    《大话数据结构》
    极客时间-数据结构和算法之美

不知道大家学习算法是从哪里起步的？反正我是之前没有学过数据结构和算法就上手代码做项目的，后来才觉得自己底子薄弱，在回头来看数据结构和算法的，我看了严蔚敏老师的那本数据结构，大话数据结构，还有王道那本考研数据结构，知道我看到排序算法，我才发现，原来我之前就接触过排序算法，不管大家之前有没有接触过排序算法，我觉得排序算法应该是所有人接触过的第一类算法。并不是指代码中，大家上学的时候肯定是“被排序的”，比如考试成绩，是按总分从高到低排序的；点名表大概率是按名字首字母排序的。那这些排序是怎么实现的？这就是排序算法。

基本定义就不说了。

我们来了解一下一些名词：

1）排序的稳定性：
    假设 ki = kj (1 <= i <= n, 1 <= j <= n, i != j),且在排序前的序列中ri领先rj(即 i < j).如果排序后ri仍领先于rj，则称所用的排序方法是稳定的。反之若可能使得排序后的序列中rj领先ri，则称所用的排序方法是不稳定的。
    
    比如：
        [0,0,5,4,3,2,1,0];
        这个数组使用排序算法。我们定义第一个0为01，第二个为02，第三个为03.
        稳定排序后，应该是[0,0,0.1,2,3,4,5]。其中0的顺序和之前定义的顺序一样，第一个0为01，第二个为02，第三个为03.
        不稳定排序后，结果也是[0,0,0.1,2,3,4,5]。但是其中0的顺序就不一定是之前定义的，有可能第一个0为01，第二个为03，第三个为02，或是其他的顺序。
        
2）内排序和外排序:
    内排序：是在排序整个过程中，待排序的所有记录全部被放置在内存中。
    外排序：是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据，才能进行。
    内排序、外排序具体每个算法需要具体分析。

1）最好、最坏、平均情况时间复杂度：
    这个没得说，时间复杂度是衡量算法效率的标准，这里需要的是这三种的时间复杂度，为什么呢？因为第一，有些排序算法会区分，为了好对比，所以我们最好都做一下区分。第二，对于要排序的数据，有的接近有序，有的完全无序。有序度不同的数据，对于排序的执行时间肯定是有影响的，我们要知道排序算法在不同数据下的性能表现。

2）时间复杂度的系数、常数、低阶：
    时间复杂度反应的是数据规模n很大的时候的一个增长趋势，所以它表示的时候会忽略系数、常数、低阶。但是实际的软件开发中，我们排序的可能是10个、100个、1000个这样规模很小的数据，所以，在对同一阶时间复杂度的排序算法性能对比的时候，我们就要把系数、常数、低阶也考虑进来。

3）比较次数和交换（或移动）次数：
    基于比较的排序算法的执行过程，会涉及两种操作，一种是元素比较大小，另一种是元素交换或移动。所以，如果我们在分析排序算法的执行效率的时候，应该把比较次数和交换（或移动）次数也考虑进去。

直接给出了，后面说明的时候慢慢理解。

排序算法分为 1比较类排序、2非比较类排序

1比较类算法：交换排序、插入排序、选择排序、归并排序
2非比较类排序：计数排序、橘排序、基数排序

交换排序：冒泡排序、快速排序
插入排序：简单插入排序、希尔排序
选择排序：简单选择排序、堆排序
归并排序：二路归并排序、多路归并排序

1、冒泡排序（Bubble Sort）

    1）比较相邻的元素。如果第一个比第二个大，就交换它们两个；
    2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
    3）针对所有的元素重复以上的步骤，除了最后一个；
    4）重复步骤1~3，直到排序完成。
    
    图解可以去查看最顶上那个博客园的链接。
    
    代码：
        function BubbleSort(arr) {
            let len = arr.length;
            for(let i = 0; i < len - 1; i++) {              //注意这里是len-1
                for(let j = 0; j < len - i - 1; j++) {      //注意这里是len - i - 1    
                    if (arr[j] > arr[j + 1]) {              //上面的len - 1和这里的j+1有关，
                                                            //自己推倒一下过程就知道，当排到数组下标为len-2的时候，则将数组中所有的元素排完了。
                        let temp = arr[j + 1];
                        arr[j + 1] = arr[j];
                        arr[j] = temp;
                    }
                }
            }
            return arr;
        }
        
        优化一下
        function bubbleSort1(arr) {
            let flag = true;
            for (let i = 0; i < arr.length - 1; i++) {
                if (flag) {                         //设置标识位，如果没有数据交换进行下一次循环
                    flag = false;
                    for (let j = 0; j < arr.length - 1 - i; j++) {   //内层遍历
        				if (arr[j] > arr[j + 1]) {                   //比较内层循环里相邻的两个数
        					swap(arr,arr[j],arr[j + 1]);
        					flag = true;            
        				}
        			} 
                }
            }
            return arr;
        }
        
    时间复杂度分析：
        最好情况：数组是排序好的，不需要去改变元素位置所以时间复杂度为O(n)
        最坏情况：数组是反序的，全部都需要换，所以是O(n^2);
        平均情况：这里是我自己想的，平均就是从最好的情况一直加到最坏情况 / n（加了n次）
            从最好的情况加到最坏情况：最好是O(n),差一点的就是需要移动一次，就是O(n * 1),两次就是O(n * 2),依次类推最后一次就是O(n * n-1),所以根据等差数列前n项和公式就是(n^2 + n) / 2，=>时间复杂度O(n^2)
            平均时间复杂度是个人见解，如有不对请批评指正。
        
        
2、快速排序（Quick Sort）

    快速排序的基本思路是基于分治法的：
        在待排序表L中任取一个元素pivot作为基准（通常取首元素），通过一趟排序将待排序表分为独立的两部分L[1, k-1]和L[k+1, n]，使得L[1, k-1]中所有的元素小于pivot,L[K+1,n]中的所有元素大于pivot，则pivo放在了其最终位置L[k]上，这个过程称为一趟快速排序，然后分别递归的对两个子表重复上述过程，直到每部分内都只有一个元素或空为止，即所有元素都放在了最终位置上。
        
    1）从数列中挑出一个元素，称为基准pivot。
    2）重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准大的摆在基准后面（相同的树可以放到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
    3）递归地把小于基准值元素的子数列和大于基准值元素的子树列排列
    
    function quckSort(arr, left, right) {
        let len = arr.length;
        let partitionIndex;
        let left = typeof left != 'number' ? 0 : left;
        let right = typeof right != 'number' ? len - 1 : right;
        
        if(left < right) {
            partitionIndex = partition(arr, left, right);
            quickSort(arr, left, partitionIndex - 1);
            quickSort(arr, partitionIndex + 1, right);
        }
        return arr;
    }
    
    //分区操作
    function partition(arr, left, right) {
        //设定基准值pivot
        let pivot = left;
        let index= pivot + 1;
        for(let i = index; i <= right; i++) {
            if(arr[i] < arr[pivot]) {
                swap(arr, i, index);
                index++;
            }
        }
    }
    
    function swap(arr, i, j) {
        vartemp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

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

    1）从第一个元素开始，该元素可以认为已经被排序；
    2）取出下一个元素，在已经排序的元素序列中从后向前扫描；
    3）如果该元素（已排序）大于新元素，将该元素移到下一位置；
    4）重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
    5）将新元素插入到该位置后；
    6）重复步骤2~5。
    
    function InsertionSort(arr) {
        let len = arr.length;
        let preIndex, current;
        for(let i = 1; i < len; i++) {
            preIndex = i - 1;                   //当前项的前一项（从1开始，所以preIndex从0开始）
            current = arr[i];                   //当前项的值
            //循环，将前一项后移一位，知道preIndex < 0或者 arr[preIndex] <= current 
            while(preIndex >= 0 && arr[preIndex] > current) {
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex + 1] = current;
        }
        return arr;
    }
    
2、希尔排序（Shell Sort）

    第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
    
    1）选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1。
    2）按增量序列个数k，对序列进行k 趟排序。
    3）每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。
    
    function shellSort(arr) {
        let len = arr.length;
        let gap = Math.floor(len/2);
        for(; gap > 0; gap = Math.floor(gap/2)) {
            for(let i = gap; i < len; i++) {
                let j = i;
                let current = arr[i];
                while(j - gap >= 0 && current < arr[j - gap]) {
                    arr[j] = aarr[j - gap];
                    j = j - gap;
                }
                arr[j] = currnt;
            }
        }
    }

1、简单选择排序（Selection Sort）

    1）初始状态：无序区为R[1..n]，有序区为空；
    2）第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；
    3）n-1趟结束，数组有序化了。
    
    function SelectionSort(arr) {
        let len = arr.length;
        let minIndex, temp;
        for(let i = 0; i < len - 1; i++) {              //这里是len - 1，因为只需要循环n - 1次
            minIndex = i;
            //查询最小数
            for(let j = i + 1; j < len; j++) {          //这里是len,因为要循环到最后一项。
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            //交换
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        return arr;
    }
    
    时间复杂度分析：
        最好时间复杂度：O(n)
        最坏时间复杂度：O(n^2)
        平均时间复杂度：O(n^2)

2、堆排序（Heap Sort）
    堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
    
    1）将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区；
    2）将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]；
    3）由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
    
    let len
    
    function buildMaxHeap(arr) {
        len = arr.length;
        for(let i = Math.floor(len / 2); i >= 0; i--) {
            heapify(arr, i);
        }
    }
    
    function heapify(arr, i) {
        let left = 2 * i + 1,
        let right = 2 * i + 2,
        let largest = i;
 
        if(left < len && arr[left] > arr[largest]) {
            largest = left;
        }
     
        if(right < len && arr[right] > arr[largest]) {
            largest = right;
        }
     
        if(largest != i) {
            swap(arr, i, largest);
            heapify(arr, largest);
        }
    }
    
    function swap(arr, i, j) {
        let temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    function heapSort(arr) {
        buildMaxHeap(arr);

        for(let i = arr.length - 1; i > 0; i--) {
            swap(arr, 0, i);
            len--;
            heapify(arr, 0);
        }
        return arr;
    }

1、两路归并排序（Merge Sort）
    
    归并排序是建立在归并操作上的一种有效的排序算法。
    归并操作使用的是分治**。
    将已有序的子序列合并，得到完全有序的序列，即先使每个子序列有序，再使子序列段间有序。
    
    1）把长度为n的输入序列分为两个长度为n/2的子序列。
    2）对这两个子序列分别采用归并排序。
    3）将两个排序好的子序列合并成一个最终的排序序列。
    
    function mergeSort(arr) {
        let len = arr.length;
        if(len < 2) return arr;
        let middle = Math.floor(len / 2);
        let left = arr.slice(0, middle);
        let right = arr.slice(middle);
        return merge(mergeSort(left), mergeSort(right));
    }   
    
    function merge(left, right) {
        let resulr = [];
        while(left.length > 0 && right.length > 0) {
            if (left[0] <= right[0]) {
                result.push(left.shift());
            } else {
                result.push(reight.shift());
            }
        }
        
        while(left.length) {
            result.push(left.shift());
        }
        
        while(right.length) {
            result.push(reight.shift());
        }
        
        return result;
    }

参考来源：
    1、《大话数据结构》
    2、极客时间-数据结构与算法之美；

算法的重要性不言而喻。

我们先来看一下算法(Algorithm)的定义：
    算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

这里我将《大话数据结构》里面的定义拿了过来，其实去维基百科上看一下，基本上一次差不多，但是维基上比较复杂。

算法具有五个特点，同时好的算法有四个设计要求：(可能有些课本不同，求同存异。)
    五个特点是：
        1）输入
        2）输出
        3）有穷性
        4）确定性
        5）可行性
        
    四个要求：
        1）正确性
        2）可读性
        3）健壮性
        4）时间效率高和存储量低
        
具体的可以自行查找，接下来我们进入主题，一个好的算法怎么去度量算法的效率？

算法的度量方法可以分为事后统计方法、事前分析估算法。

首先说说这个事后统计方法。

    这种方法主要是通过设计号的测试程序和数据，利用计算机计时器对不同算法的程序运行时间进行比较。
    其实很容易想到，一个算法都设计好了，怎么度量？当然是前面加个时间，后面加个时间，一减，不就出来了程序跑的时间了。但是，这种方式呢，有一些弊端：
        第一，要事后统计，算法得先写出来吧？如果写出来的算法耗时很高，不就白写了？
        
        第二，这个呢，玩游戏的同学肯定很清楚，一个游戏的流畅度受硬件的影响，同一个游戏，跑在最新的硬件上，基本上可以说比几年前机器要流畅。算法也可以这样想，因为处理算法的运算速度受操作系统、编译器、运行框架等等环境的影响。
        
        第三，算法的测试数据设计困难。这个好像不需要过多解释，因为算法的输入不是固定的，所以谁知道会输入什么样的测试数据呢。
        
    根据上面我们可以暂时不选择事后统计方法，要选的话也只是用来测试，毕竟算法编好了，也是需要测试的。千万不要认为事后统计方法没用了，像leetcode上面，提交能够计算出用时等数据，不就是事后统计方法嘛。

接下来我们来重点看一下事前分析估算法。

    很好解释，事前就是程序编写之前，依据统计方法对算法进行估算。
    经过分析，可以发现一个程序在计算机上运行时所消耗的时间取决于下列因素：
        1）算法采用的策略、方法。
        2）编译产生的代码质量。
        3）问题的输入规模。
        4）机器执行指令的速度。
    第一条是算法好坏的根本，第二条需要由编译器来支持，第四条要看硬件性能。所以抛开固定环境有关的，我们可以这样看：
        一个程序的运行时间，依赖于算法的好坏和问题的输入规模。
        
我们已经选好了算法效率度量的方法了，接下来我们来看看算法到底是怎么度量效率的？

同样的，先看一下算法时间复杂度的定义
    在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度，也就是算法的时间量度，记作：T(n) = O(f(n));。它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称时间复杂度。

绕的头都晕了，简而言之：一个算法运行时间(抛开环境的影响),是关于这个算法解决问题规模的函数。规模越大，运行时间或者称时间复杂度越高。
现在基本上都在使用大O记法来表示时间复杂度。

上面的定义了解一下就好了，我们来看看时间复杂度怎么分析：

    其实分析时间复杂度，只需要关注循环次数最多的代码块就好了。
    时间复杂度有两个法则：加法法则、乘法法则
    
        时间复杂度的加法法则：T(n) = T1(n) + T2(n) = O(f(n1)) + O(f(n2)) = O(MAX(f(n1),f(n2)))。
            就是说，当循环代码块是独立的，只需要看时间复杂度高的就行了。
            比如：
                let O = function(n) {
                    for(let i = 0; i < n; i++) {
                        ...
                    }
                    let j = 1
                    while (j <= n) {
                        j *= 2;
                    }
                }
            函数O里面包含两个循环，但是两个循环都是独立的，所以时间复杂度是两个循环中最大的一段循环的时间复杂度，这里是O(n),同学们可以想一下，两段循环的事件负责度都是多少。后面会有讲解。
            
        时间复杂度的乘法法则：T(n) = T1(n) * T2(n) = O(f(n1)) * O(f(n2)) = O(f(n1) * f(n2))。
            
            就是说，当循环代码块是嵌套的时候，需要将每个循环的时间复杂度相乘得到总的时间复杂度。
            比如：
                let O2 = function(n) {
                    for(let i = 0; i < n; i++) {
                        let j = 1
                        while (j <= n) {
                            j *= 2;
                        }
                    }
                }
            这里的函数O2里面也是包含两个循环，但是两个循环是嵌套在一起的，所以总的时间复杂度就等于，外层循环时间复杂*内存循环时间复杂度。这里的时间复杂度是O(nlogn)。具体每个循环怎么分析等会再说，只需要直到，外层时间复杂度O(n),内层的是O(logn)。
            
    上面是时间复杂度的两个法则，现在我们来看一下几种常见的时间复杂度具体分析。
    
    1）常量阶O(1)
    2）对数阶O(logn)
    3）线性阶O(n)
    4）线性对数阶O(nlogn)
    5）平方阶O(n^2)
    6）指数阶O(2^n)
    7）阶乘阶O(n!)
    
    是不是觉得括号里面的表达式很熟悉？没错，这就是基本初等函数表达式，如果不记得的话可以查看高数上的第一章。
    
    我们都知道，时间复杂度是算法执行时间的增长率。结合上面常见的时间复杂度表示，我们不用看下面也能推出：
        O(1) < O(logn) < O(nlogn) < O(n) < O(n^2) < O(2^n) < O(n!)
    这是根据函数的图形得出来的，可以尝试画出上述函数的图形，看一下在坐标系中的图形就能直观的感受这个含义。
    
    了解了函数的渐进增长，接下来就一个一个分析下。
    
        1）常数阶：
            就是只执行一次的语句。
            比如：
            function ab() {
                let a = 1,b = 2;     //执行一次
                a += 1;              //执行一次
                b -= 1;              //执行一次
                a = a + b;           //执行一次
            }
            上面这个函数，里面有四个执行一次的语句，实际上不管有多少这样语句，它的时间复杂度都是O(1)，而不是O(4)什么的。
            因为这些语句与问题的大小无关。这句话后面多看两个例子就懂了。
        
        2）对数阶O(logn)、线性对数阶O(nlogn):
            还记得上面那个函数嘛？
            let O2 = function(n) {
                for(let i = 0; i < n; i++) {
                    let j = 1
                    while (j <= n) {
                        j *= 2;
                    }
                }
            }
            我们分析一下。外层的先放一下，内层的函数我们拿出来就是：
                let j = 1
                while (j <= n) {
                    j *= 2;
                }
            从代码中可以看出，变量j的值从1开始取，每循环一次就乘以2。当大于n时，循环结束。还记得我们高中学过的等比数列吗？实际上，变量j的取值就是一个等比数列。如果我把它一个一个列出来，就应该是这个样子的：
                2^1 2^2 ... 2^x =n
            => x = log2^n;
            如果是 3^1 3^2 3^3 .. 3^x = n
            => x = log3^n
            但是我们知道 log3^n = log3^2 * log2^n = O(C * log2^n);
            在使用大O表示法的时候，我们可以忽略系数即O(C * f(n)) = O(f(n));
            所以 log3^n => O(log2^n)因此，在对数阶时间复杂度的表示方法里，我们忽略对数的“底”，统一表示为 O(logn)。
            
            同时我们来说一下O2这个函数，内层是O(logn);外层是下一步说到的线性阶O(n)；那根据乘法法则，总的时间复杂度是多少？就不需要说了吧。
        
        3）线性阶O(n):
            这个很好理解，比如
            for(let i = 0; i < n; i++) {
                ...
            }
            这个循环就是循环了n次，直到i = n的时候退出循环，时间复杂度就是O(n)。
            
        4）平方阶O(n^2):
            一个线性阶是O(n)，根据乘法法则，两个线性阶嵌套在一起不就是O(n * n)嘛。
            for (let i = 0; i < n; i++) {
                for (let j = 0; j < n; j++) {
                    ...
                }
            }
            这个就是平方阶O(n^2);
            
        5）O(m + n),O(m * n):
            这是拓展的，可以自己写一下时间复杂度是O(m + n),O(m * n)的代码块。

其实空间复杂度比时间复杂度好理解，时间复杂度是算法执行时间与数据规模的增长关系。空间复杂度就是算法的存储空间与数据规模的增长关系。

空间复杂度使用的没有时间复杂度多，因为现在计算机硬件的发展，人们可以更多的拿空间来换取时间。

空间复杂度为O(1):若算法执行时所需的辅助空间相对于输入数据量而言是个常数，则称次算法为原地工作，空间复杂度记为O(1)

最好时间复杂度：在最理想的情况下，执行这段代码的时间复杂度

最坏时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度

平均时间复杂度：所有情况下，求一个平均值，可以省略掉系数、低阶、常量

平均时间复杂度是所有情况最有意义的，因为它是期望的运行时。

平均时间复杂度计算就是将所有的情况相加 / 运行了多少次情况。这个后面遇到具体的算法会具体分析。