算法学习笔记（一）复杂度和简单排序算法

算法学习笔记是根据牛客网左神课程讲到的知识点，按自己目前的理解归纳整理的，如果文章中出现错误，欢迎指出并交流。虽然思路和方法相同，但为了巩固知识点加深印象，涉及的代码将用Java和JavaScript各自实现一遍。

一. 时间复杂度与额外空间复杂度

（1）常数操作：和样本数量无关，每次都花费固定时间的操作。

（2）时间复杂度：算法流程中的重要指标，度量常数操作的数量，用O（读作big O）来表示。首先要对算法流程足够熟悉，看流程中进行了多少次的常数操作，再总结出相应的常数操作数量的表达式。针对这个表达式，只看高阶项，并且忽略高阶项的常数项，假设此时得到的式子为f(n)，那么时间复杂度就是O(f(n))。

对于上述描述，我的理解是时间复杂度是一个度量算法执行时间的指标，而衡量算法的执行时间可以通过常数操作的次数来进行，执行次数和样本规模n有关，因此可以总结出常数操作数量表达式。而随着n也就是问题规模的扩大，只有最高阶项会对结果影响巨大，高阶项的系数的影响也几乎可以忽略，这就得到了O(f(n))了。同一问题的算法比较优劣时可以将函数f(n)作为重要标准。如果这个指标相同，可以再通过实验比对效率。这时的差异就在于之前忽略掉的常数项，它往往是通过实验比较的，除非特别熟悉可以直接理论分析比较。

（3）额外空间复杂度：空间复杂度用来衡量算法运行过程中需要临时占用的储存空间大小。去掉和问题要求相关的数据结构，看是否还需要额外的数据结构并存储数据。如果只是需要有限的几个变量，那么额外空间复杂度就是O(1)。如何理解去除和问题要求相关的数据结构呢？比如给定一个数组，题目要求返回一个拷贝的新数组，因为运行过程中用到的新数组正是要返回的内容，所以空间复杂度依然是O(1)。

二. 选择排序(Selection sort)与复杂度分析

（1）基本原理：从待排序的数据中选出最大值（最小值），排列在序列的最前面；对后面的序列进行相同的步骤，直到所有的数据排列完毕。

（2）详解：假设有n个元素，a[0]到a[n-1]，第一次是选出a[0]到a[n-1]中的最大值（最小值），将它排列在a[0]的位置；第二次比较出a[1]到a[n-1]中的最大值（最小值），将它排列在a[1]的位置；以此类推，直到排序结束。因为每次都是从待排序元素中选出最大值（最小值）排在前面，所以叫做选择排序。

如果排序过程中遇到两个相同的元素，排序前后能保证着两个相同元素位置不变的排序方式是稳定的，反之就是不稳定的。选择排序是不稳定的排序方法。

（假设C为均摊到每个位置的数的常数操作次数）

a[0] …… a[n-1] N个数 C*N

a[1] …… a[n-1] N-1 C*(N-1)

a[2] …… a[n-1] N-2 C*(N-2)

…… …… ……

a[n-1] 1 C*1

将常数操作次数相加：CN + C(N-1) + C(N-2) + … + C = C(aN^2 + bN + k)，其中C, a, b, k均为常数（aN^2 + bN + k为等差数列求和公式）。其中高阶项为acN^2，忽略常数项ac，得到时间复杂度O(n^2)。空间复杂度O(1)。

Java

public static void selectionSort(int[] arr) {
        // 如果数组为null或者数组内元素长度小于等于1
        if(arr==null || arr.length<=1) {
            return;
        }
        for(int i=0; i<arr.length; i++) {
            // minIndex存放待排序的序列中最小值的下标
            int minIndex = i;
            for(int j=i+1; j<arr.length; j++) {
                if(arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 将选出的最小值与此序列中最前面的数交换位置
            int tem = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = tem;
        }
    }

JavaScript

function selectionSort(arr){
      if(arr==null || arr.length<=1){
        return;
      }
      for(var i=0; i<arr.length; i++){
        var minIndex = i;
        for(var j=i+1; j<arr.length; j++){
          if(arr[j] < arr[minIndex]){
            minIndex = j;
          }
        }
        var tem = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = tem;
      }
    }

三. 冒泡排序(Bubble sort)与复杂度分析

（1）基本原理：每次比较相邻的两个元素，如果顺序与题目要求排列顺序（比如从大到小，从小到大，首字母A-Z…）不相符就交换位置，那么最后一个位置上就是走访过的数据的极值（最小值，最大值，首字母为Z…）。重复走访未排序过的数列，直到排列完毕。

（2）详解：假设要求从小到大对一组数据进行排列。首先比较相邻的元素，如果第二个数比第一个数小就交换位置；对每组相邻的数据都进行上述操作，直到比较完最后一对，此时最后一个位置上的就是这组数据中的最大值；将除了最后一个数的序列重复上述步骤；每次都排除最后一个已经排好序的元素，重复进行操作，直到所有元素都排好位置。因为每一次都会将现有数据的最大值“浮”到顶端，因此称为冒泡排序。冒泡排序是稳定的排序方法。

假设有n个数，a[0]到a[n-1]，第一次走访比较a[0]到a[n-1]，结束后最大值位于a[n-1]；第二次走访比较a[0]到a[n-2]，结束后最大值位于a[n-2]……以此类推，直到排序完毕。同样假设假设均摊到每个位置的数的常数操作次数为C，与上述选择排序相同，提取C后的式子可以利用等差数列求和公式。同样得到时间复杂度为O(n^2)。空间复杂度O(1)。

Java

public static void bubbleSort(int[] arr) {
       if(arr==null || arr.length<=1) {
           return;
       }
       for(int e=arr.length-1; e>0; e--) {
           for(int i=0; i<e; i++) {
               if(arr[i]>arr[i+1]) {
                   int tem = arr[i];
                   arr[i] = arr[i+1];
                   arr[i+1] = tem;
               }
           }
       }
    }

JavaScript

function bubbleSort(arr){
      if(arr==null || arr.length<=1){
        return;
      }
      for(var e=arr.length-1; e>0; e--){
        for(var i=0; i<e; i++){
          if(arr[i]>arr[i+1]){
            var tem = arr[i];
            arr[i] = arr[i+1];
            arr[i+1] = tem;
          }
        }
      }
    }

四. 插入排序(Insertion sort)与复杂度分析

(1) 基本原理：将未被排序的元素与前面的有序序列元素从后向前比较，并插入到正确的位置。

(2) 详解：假设将一个数组中的数从小到大排列。第一次进行时，将第一个元素视为已排序元素，第二个元素一直到末尾元素都是未排序元素，比较第二个元素与第一个元素的大小，如果第二个比第一个大，就不改变位置，反之插入到第一个元素的前面；第二次，将前两个元素视为已排序元素，第三个到末尾的是未排序序列，如果比前一个大，就不改变位置，反之插入到前一个元素的前面，再与第一个元素比较，看是否需要插入到第一个元素之前；以此类推，每个将要进行排序的未排序元素都与前面的元素比较，插入到合适的位置，如果两个数相同就排在相等元素的后面。由于每次要把将排序的元素插入到前面合适的位置，就把这种方法称为插入排序，像插入一张扑克牌一样。这种排序也是稳定的方式。

这种排序方式的时间复杂度与实际的数据状况有关，如果一开始就是有序的一组数，那么每次只需要和前面的一个元素进行比较，那么就是O(N)；如果一开始是逆序的一组数，每次都要将待排序元素与已排序的所有元素比较，插入到最前面，此时就是O(N^2)；根据规定，需要按照最差情况计算时间复杂度，因此插入排序的时间复杂度也是O(N^2)，空间复杂度O(1)。在O(N^2)的排序算法中，插入排序是最好的，因为不一定每次都是逆序的最差情况。

Java

public static void insertionSort(int[] arr) {
       if(arr==null || arr.length<=1) {
           return;
       }
       for(int i=1; i<arr.length; i++) {
           for(int j=i-1; j>=0 && arr[j]>arr[j+1]; j--) {
               int tem = arr[j+1];
               arr[j+1] = arr[j];
               arr[j] = tem;
           }
       }
    }

JavaScript

function insertionSort(arr){
      if(arr==null || arr.length<=1){
        return;
      }
      for(var i=1; i<arr.length; i++){
        for(var j=i-1; j>=0 && arr[j]>arr[j+1]; j--){
          var tem = arr[j];
          arr[j] = arr[j+1];
          arr[j+1] = tem;
        }
      }
    }