一、时间复杂度（表示数据量和算法流程的关系）

一个操作如果和样本的数据量没有关系，每次都是固定时间内完成的操作，叫做常数操作。
在表达式中，只要高阶项和它的系数，不要低阶项，剩下的部分如果为f(N),则时间复杂度为O(f(N))。
比如如下计算：

for (int i = 0;i < list.size();i++){
            System.out.print(list.get(i));
        }

对于arraylist而言，内部是线性表实现，get()方法直接获取index上的值，时间复杂度是O(1)，遍历
整个集合的时间复杂度是1+1+... = O(N)
而基于链表实现的LinkedList类，只知道链表指针指向的下一个元素，所以需要通过for循环从头或尾开始查找,
当i = 0时，遍历一个数，复杂度为1；
当i = 1时，遍历两个数，复杂度为2；
...
当i = N - 1时，遍历N个数，复杂度为N；
所以，LinkedList整体时间复杂度为1+2+...+N ，0(N^2)

二、空间复杂度

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，指除去原始数据外所需要的额外空间。如果空间复杂度与数据量的大小无关，则空间复杂度大小描述为O(1)。

三、几种基础排序

https://visualgo.net/en/sorting

1、选择排序

把每个位置与其后每一个数进行比较，获取到最小的那个数，然后把它与当前位置交换。
时间复杂度0(N^2)

    public static void selectionSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        for (int i = 0; i < arr.length - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            swap(arr, i, minIndex);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

2、冒泡排序

  相邻元素之间对比，谁大谁在后。
  时间复杂度0(N^2)

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

3、插入排序

每次比较前N个数，谁大谁在后。
取最坏情况，时间复杂度0(N^2)

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

** 异或运算：无进位相加。相同为0，不同为1.
如果想交换两个数，可使用以下方式：

a = a ^ b
b = a ^ b
a = a ^ b

**

4、归并排序

是典型的分治算法，分治法是将一个问题分解成规模更小、结构相似的子问题，解决问题A，变成了解决问题A1和A2，解决问题A1变成了解决问题A11和A12。。。，一直到最小单元，当最小单元问题解决后，依次向上返回，问题A得以解决。
这里整体是一个简单的递归，左边排好序，右边排好序，然后让其整体有序。
递归行为：压栈，从最小单元依次向上返回
(图片来自网络)

image.png

    public static void mergeSort(int[] arr, int L, int r) {
        if (L == r) {
            return;
        }
        int mid = L + ((r - L) >> 1);
        mergeSort(arr, L, mid);
        mergeSort(arr, mid + 1, r);
        merge(arr, L, mid, r);
    }

    public static void merge(int[] arr, int L, int m, int r) {
        int[] help = new int[r - L + 1];
        int i = 0;
        int p1 = L;
        int p2 = m + 1;
        while (p1 <= m && p2 <= r) {
            help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
        }
        while (p1 <= m) {
            help[i++] = arr[p1++];
        }
        while (p2 <= r) {
            help[i++] = arr[p2++];
        }
        for (i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }
    }

5、堆排序

时间复杂度O(nlogn)
堆结构是用数组实现的完全二叉树结构。
完全二叉树中如果每个子树的最大值都在顶部就是大根堆，如果最小值都在顶部则是小根堆。
完全二叉树：若设二叉树的深度为h，除最后一层外，其它各层 (1～h-1) 的结点数都达到最大个数，最后一层所有的结点都从左到右排列，这就是完全二叉树。

image.png

对于一颗完全二叉树，位置i处的左节点：i2+1,右节点：i2+2，父节点：(i-1)/2. 高度：log2^N

优先队列PriorityQueue就是小根堆，保证每次弹出的都是最小值：

 PriorityQueue<Integer> queue = new PriorityQueue<>();
            queue.add(3);
            queue.add(5);
            queue.add(1);
            while (!queue.isEmpty()){
                System.out.print(queue.poll());
            }
打印结果：----1,3,5----------------

堆排序的思想：
把待排序的数组构造成一个大根堆，然后将首尾元素进行交换，此时末位置是最大值。然后将剩余的n-1个元素重新构造成大根堆，这样就得到n个元素的次小值，重复执行，直到堆的大小为0，就得到一个有序的序列。

public static void heapSort(int[] arr) {
       if (arr == null || arr.length < 2) {
           return;
       }
       //数组变成大根堆  O(n)
       for (int i = 0; i < arr.length; i++) {
           heapInsert(arr, i);
       }

       int size = arr.length;
       //交换最大值和堆中最后一个数，堆的大小变为size-1
       swap(arr, 0, --size);

       //从0位置开始，重新调整成大根堆 O(logN)
       while (size > 0) {
           heapify(arr, 0, size);
           swap(arr, 0, --size);
       }
   }

   //index位置处的值发生了变化，并且是变大，重新调整成大根堆
   public static void heapInsert(int[] arr, int index) {
       while (arr[index] > arr[(index - 1) / 2]) {
           swap(arr, index, (index - 1) /2);
           index = (index - 1)/2 ;
       }
   }

   //index位置处的值发生了变化，并且是变小，重新调整成大根堆
   public static void heapify(int[] arr, int index, int size) {
       int left = index * 2 + 1;
       while (left < size) {//index位置处是否还有子节点
           int largest = left + 1 < size  //如果有右节点
                   && arr[left + 1] > arr[left]  //右节点的值大于左节点
                   ? left + 1 : left;
           //两个孩子和父节点的值比较，最大的值的下表作为largest的值
           largest = arr[largest] > arr[index] ? largest : index;

           if (largest == index) {//如果最大的值的下标已经是父节点的位置，过程停止
               break;
           }
           //选出来的largest的位置一定不是i位置，是i位置的左右两个孩子中较大值的下标
           swap(arr, largest, index);
           index = largest;
           left = index * 2 + 1;
       }
   }

6、快速排序

快速排序是目前应用最广泛的排序算法之一，它是一般场景中大规模数据排序的首选。
partition过程：每次排序的时候设置一个基准点，将小于基准点的数全部放到基准点的左边，将大于基准点的数全部放到基准点的右边。

当前数<p，当前数和<区后一个数做交换，<区右扩，当前位置跳下一个。
当前数=p，当前位置跳下一个。
当前数>p，当前数和>区前一个交换，>区左扩，当前位置不变。

以数组的最后一个数为P，然后再把<区和>区分别进行partition

    public static void quickSort(int[] arr, int L, int r) {
        if (L < r) {
            //改进方法：随机快排，从R-L中随机选一个数，放到最后
//          swap(arr, L + (int) (Math.random() * (r - L + 1)), r);
            int[] p = partition(arr, L, r);
            //小于区
            quickSort(arr, L, p[0] - 1);
            //大于区
            quickSort(arr, p[1] + 1, r);
        }
    }

    //默认以arr[r]为区分
    //返回等于区域（左边界，右边界），所以返回一个长度为2的数组res，res[0] res[1]
    public static int[] partition(int[] arr, int L, int r) {
        int less = L - 1; //小于区右边界
        int more = r; //大于区左边界,包含最后一个数
        while (L < more) {
            if (arr[L] < arr[r]) {//默认以arr[r]做划分，当前数 < 划分值时
                swap(arr, ++less, L++);
            } else if (arr[L] > arr[r]) {
                swap(arr, --more, L);
            } else {
                L++;
            }
        }
        //在大于区域最后一个数和第一个数交换，因为最后一个数属于等于区
        swap(arr, more, r);
        return new int[] { less + 1, more };
    }

时间复杂度：最差的情况O(N^2)，比如顺序排列的数，以最后一个数做划分，每次只能确定一个数。平均时间复杂度为O（n×log（n））。

7、桶排序（不基于比较的排序）

计数排序（数据样本需要在固定范围内）

比如输入n个元素，范围是0-k的整数，统计出0-k每个元素有多少个。
好比准备k+1个桶，每出现一个数，就放进对应的桶里，每一个桶的作用就是标记每个数出现的次数。

image.png

基数排序（十进制的数）

将整数按位数切割，然后每个位数分别比较。

   public static void radixSort(int[] arr) {
       if (arr == null || arr.length < 2) {
           return;
       }
       radixSort(arr, 0, arr.length - 1, maxbits(arr));
   }

   /**
    * 最大值有几位
    * @param arr
    * @return
    */
   public static int maxbits(int[] arr) {
       int max = Integer.MIN_VALUE;
       for (int i = 0; i < arr.length; i++) {
           max = Math.max(max, arr[i]);
       }
       int res = 0;
       while (max != 0) {
           res++;
           max /= 10;
       }
       return res;
   }

   //在arr[begin..end]排序
   public static void radixSort(int[] arr, int begin, int end, int digit) {
       final int radix = 10;
       int i = 0, j = 0;

       //有多少个数就准备多少个辅助空间
       int[] bucket = new int[end - begin + 1];
       //有多少位就进出几次
       for (int d = 1; d <= digit; d++) {
           //准备10个空间，count[0]代表当前位（d）是0的数字有多少个
           //count[i]代表当前位是（0到i）的数字有多少个
           int[] count = new int[radix];

           //count[j]：d位置的j的总数
                      //统计对应位（个位、十位、百位等）的每个数字的总数
           for (i = begin; i <= end; i++) {
               j = getDigit(arr[i], d);
               count[j]++;
           }
           //累加，对于每个位数的元素i，统计出小于等于i的元素有几个
           for (i = 1; i < radix; i++) {
               count[i] = count[i] + count[i - 1];
           }
                       
           for (i = end; i >= begin; i--) {
               j = getDigit(arr[i], d);
               bucket[count[j] - 1] = arr[i];
               count[j]--;
           }
           for (i = begin, j = 0; i <= end; i++, j++) {
               arr[i] = bucket[j];
           }
       }
   }

   //获取d位置的数
   public static int getDigit(int x, int d) {
       return ((x / ((int) Math.pow(10, d - 1))) % 10);
   }

稳定性对比

稳定性是指，在排序之后，相同数的相对位置不变
稳定算法：冒泡排序、插入排序、归并排序、基数排序
不稳定算法 ：选择排序、快速排序、堆排序

稳定性的意义

如果只是简单的进行数字的排序，那么稳定性将毫无意义。
如果排序的内容仅仅是一个复杂对象的某一个数字属性，那么稳定性依旧将毫无意义
如果要排序的内容是一个复杂对象的多个数字属性，但是其原本的初始顺序毫无意义，那么稳定性依旧将毫无意义。
除非要排序的内容是一个复杂对象的多个数字属性，且其原本的初始顺序存在意义，那么我们需要在二次排序的基础上保持原有排序的意义，才需要使用到稳定性的算法，例如要排序的内容是一组原本按照价格高低排序的对象，如今需要按照销量高低排序，使用稳定性算法，可以使得想同销量的对象依旧保持着价格高低的排序展现，只有销量不同的才会重新排序。（当然，如果需求不需要保持初始的排序意义，那么使用稳定性算法依旧将毫无意义）。

各个算法对比：

image.png