算法

算法是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。说人话：根据一定的条件，对一些数据进行计算，得到需要的结果。

算法分析

我们要计算算法时间耗费情况，首先我们得度量算法的执行时间，那么如何度量呢？

时间复杂度

事后分析估算方法：比较容易想到的方法就是我们把算法执行若干次，然后拿个计时器在旁边计时，这种事后统计的方法看上去的确不错，并且也并非要我们真的拿个计算器在旁边计算，因为计算机都提供了计时的功能。这种统计方法主要是通过设计好的测试程序和测试数据，利用计算机计时器对不同的算法编制的程序的运行时间进行比较，从而确定算法效率的高低，但是这种方法有很大的缺陷：必须依据算法实现编制好的测试程序，通常要花费大量时间和精力，测试完了如果发现测试的是非常糟糕的算法，那么之前所做的事情就全部白费了，并且不同的测试环境（硬件环境）的差别导致测试的结果差异也很大。

public static void main(String[] args) {
    long start = System.nanoTime();
    int sum = 0;
    int count = 100000;
    for (int i = 1; i <= count; i++) {
        sum += i;
    }
    System.out.println(sum);
    System.out.println("耗时" + (System.nanoTime() - start));
}

事前分析估算方法：在计算机程序编写前，依据统计方法对算法进行估算，经过总结，我们发现一个高级语言编写的程序程序在计算机上运行所消耗的时间取决于下列因素：

1. 算法采用的策略和方案；

2. 编译产生的代码质量；

3. 问题的输入规模（所谓的问题输入规模就是输入量的多少）；

4. 机器执行指令的速度；

由此可见，抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间依赖于算法的好坏和问题的输入规模。如果算法固定，那么该算法的执行时间就只和问题的输入规模有关系了。

大O记法

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

在这里，我们需要明确一个事情：执行次数=执行时间。

用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。一般情况下，随着输入规模n的增大，T(n)增长最慢的算法为最优算法。

1. 用常数1取代运行时间中的所有加法常数。

2. 在修改后的运行次数中，只保留高阶项；

3. 如果最高阶项存在，且常数因子不为1，则去除与这个项相乘的常数；

常见的大O阶

线性阶O(n)：一般含有非嵌套循环涉及线性阶，线性阶就是随着输入规模的扩大，对应计算次数呈直线增长。

//循环的时间复杂度为O(n),因为循环体中的代码需要执行n次
public static void main(String[] args) {
    int sum = 0;
    int n = 100;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    System.out.println(sum);
}

平方阶：一般嵌套循环属于这种时间复杂度。

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        sum += n;
    }
}

立方阶：一般三层嵌套循环属于这种时间复杂度。

对数阶：O(log(n))。对于对数阶，由于随着输入规模n的增大，不管底数为多少，他们的增长趋势是一样的，所以我们会忽略底数。

//由于每次i*2之后，就距离n更近一步，假设有x个2相乘后大于n，则会退出循环。
//由于是2^x=n,得到
x=log(2)n,所以这个循环的时间复杂度为O(logn);
public static void main(String[] args) {
    int i = 1;
    int n = 100;
    while (i < n) {
    // 每次循环都扩大2倍
        i = i*2;
    }
    System.out.println(i);
}

常数阶O(1)：一般不涉及循环操作的都是常数阶，因为它不会随着n的增长而增加操作次数。

它们的复杂程度从低到高依次为：O(1)<O(logn)<O(n)<O(nlogn)<O(n^2)<O(n3)<O(2^N)。

我们的算法，尽可能的追求的是O(1)，O(logn)，O(n)，O(nlogn)这几种时间复杂度，而如果发现算法的时间复杂度为平方阶、立方阶或者更复杂的，那我们可以分为这种算法是不可取的，需要优化。

最坏情况

假如有一个需求：有一个存储了n个随机数字的数组，请从中查找出指定的数字。

public static void main(String[] args) {
    int num = 1;
    int[] arr = {11, 10, 2, 4, 6, 1};
    for (int i = 0; i < arr.length; i++) {
        if (num == arr[i]) {
            System.out.println(i);
            break;
        }
    }
}

最好情况：查找的第一个数字就是期望的数字，那么算法的时间复杂度为O(1)。

最坏情况：查找的最后一个数字，才是期望的数字，那么算法的时间复杂度为O(n)。

平均情况：任何数字查找的平均成本是O(n/2)。

最坏情况是一种保证，在应用中，这是一种最基本的保障，即使在最坏情况下，也能够正常提供服务，所以，除非特别指定，我们提到的运行时间都指的是最坏情况下的运行时间。

空间复杂度

Java中常见的内存占用

1、基本数据类型内存占用：
	byte 1字节  short 2字节  int 4字节  long 8字节
	float 4字节  double 8字节
	boolean 1字节 char 2字节
2、计算机访问内存的方式都是一次一个字节
3、一个引用需要8个字节表示
	例如： Date date = new Date(),则date这个变量需要占用8个字节来表示。
4. 创建一个对象，比如new Date()，除了Date对象内部存储的数据(例如年月日等信息)占用的内存，该对象本身也有内存开销，每个对象的自身开销是16个字节，用来保存对象的头信息。
5. 一般内存的使用，如果不够8个字节，都会自动填充为8字节。
6、java中数组被被限定为对象，一般都会因为记录长度而需要额外的内存，一个原始数据类型的数组一般需要24字节的头信息(16个自己的对象开销，4字节用于保存长度以及4个填充字节)再加上保存值所需的内存。

类似于时间复杂度的讨论，一个算法的空间复杂度（Space Complexity）定义为该算法所耗费的存储空间，它也是问题规模n的函数。

算法的空间复杂度计算公式记作：S(n)=O(f(n))，其中n为输入规模，f(n)为语句关于n所占存储空间的函数。

空间复杂度（Space Complexity）是对一个算法在运行过程中临时占用存储空间大小的量度。有的算法需要占用的临时工作单元数与解决问题的规模n有关，它随着n的增大而增大，当n较大时，将占用较多的存储单元，例如快速排序和归并排序算法，基数排序就属于这种情况。

在做算法分析时，主要讨论的是时间复杂度。从用户使用体验上看，更看重的程序执行的速度。一些缓存产品（redis、memcache）和算法（基数排序）本质就是用空间换时间。

排序算法

概述

排序也称排序算法（Sort Algorithm），排序是将一组数据，依指定的顺序进行排列的过程。

1、内部排序：指将需要处理的所有数据都加载到内部存储器（内存）中进行排序。

2、外部排序法：数据量过大，无法全部加载到内存中，需要借助外部存储（文件等）进行排序。

常见的排序算法分类：

冒泡排序

冒泡排序（Bubble Sorting）的基本思想是：通过对待排序序列从前向后（从下标较小的元素开始），依次比较相邻元素的值，若发现逆序则交换，使值较大的元素逐渐从前移向后部，就象水底下的气泡一样逐渐向上冒。最终最后位置的元素就是最大值。

public static void bubbleSort(int[] arr) {
    int temp = 0; // 临时变量
    boolean flag = false; // 标识变量，表示是否进行过交换
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = 0; j < arr.length - 1 - i; j++) {
            // 如果前面的数比后面的数大，则交换
            if (arr[j] > arr[j + 1]) {
                flag = true;
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
        //System.out.println("第" + (i + 1) + "趟排序后的数组");
        //System.out.println(Arrays.toString(arr));
        if (!flag) { // 在一趟排序中，一次交换都没有发生过
            break;
        } else {
            flag = false; // 重置flag, 进行下次判断
        }
    }
}

选择排序

选择式排序也属于内部排序法，是从欲排序的数据中，按指定的规则选出某一元素，再依规定交换位置后达到排序的目的。

排序原理：每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引；交换第一个索引处和最小值所在的索引处的值。

public static void selectSort(int[] arr) {
    for (int i = 0; i < arr.length - 1; i++) {
		//假定下标为i的值为最小值
        int minIndex = i;
        int min = arr[i];
        for (int j = i + 1; j < arr.length; j++) {
            if (min > arr[j]) { // 说明假定的最小值，并不是最小
                min = arr[j]; // 重置min
                minIndex = j; // 重置minIndex
            }
        }

        // 将最小值，放在arr[0], 即交换
        if (minIndex != i) {
            arr[minIndex] = arr[i];
            arr[i] = min;
        }

        //System.out.println("第"+(i+1)+"轮后~~");
        //System.out.println(Arrays.toString(arr));
    }
}

插入排序

插入排序（Insertion sort）是一种简单直观且稳定的排序算法。插入排序的工作方式非常像人们排序一手扑克牌一样。开始时，我们的左手为空并且桌子上的牌面朝下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。

排序原理：把所有的元素分为两组，已经排序的和未排序的；找到未排序的组中的第一个元素，向已经排序的组中进行插入；倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位。

public static void insertSort(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        //定义待插入的数
        int insertVal = arr[i];
        int insertIndex = i - 1; // 即arr[1]的前面这个数的下标

        // 给insertVal 找到插入的位置
        // 1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界
        // 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
        // 3. 就需要将 arr[insertIndex] 后移
        while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
            arr[insertIndex + 1] = arr[insertIndex];// arr[insertIndex]
            insertIndex--;
        }
        // 当退出while循环时，说明插入的位置找到, insertIndex + 1
        //判断是否需要赋值
        if (insertIndex + 1 != i) {
            arr[insertIndex + 1] = insertVal;
        }

        //System.out.println("第"+i+"轮插入");
        //System.out.println(Arrays.toString(arr));
    }
}

希尔排序

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称缩小增量排序。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

// 希尔排序时，对有序序列在插入时采用交换法
public static void shellSort(int[] arr) {
    int count = 0;
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < arr.length; i++) {
            // 遍历各组中所有的元素(共gap组), 步长gap
            for (int j = i - gap; j >= 0; j -= gap) {
                // 如果当前元素大于加上步长后的那个元素，说明交换
                if (arr[j] > arr[j + gap]) {
                    int temp = arr[j];
                    arr[j] = arr[j + gap];
                    arr[j + gap] = temp;
                }
            }
        }
        //System.out.println("希尔排序第" + (++count) + "轮 =" + Arrays.toString(arr));
    }
}

//对交换式的希尔排序进行优化,移位法
public static void shellSort2(int[] arr) {
    // 增量gap, 并逐步的缩小增量
    for (int gap = arr.length / 2; gap > 0; gap /= 2) {
        // 从第gap个元素，逐个对其所在的组进行直接插入排序
        for (int i = gap; i < arr.length; i++) {
            int j = i;
            int temp = arr[j];
            if (arr[j] < arr[j - gap]) {
                while (j - gap >= 0 && temp < arr[j - gap]) {
                    //移动
                    arr[j] = arr[j-gap];
                    j -= gap;
                }
                //当退出while后，就给temp找到插入的位置
                arr[j] = temp;
            }
        }
    }
}

归并排序

归并排序是建立在递归操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

分治（divide-and-conquer）策略：将问题分（divide）成一些小的问题然后递归求解，而治（conquer）的阶段则将分的阶段得到的各答案”修补“在一起，即分而治之。

排序原理：

1. 尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止；

2. 将相邻的两个子组进行合并成一个有序的大组；

3. 不断的重复步骤2，直到最终只有一个组为止。

public class MergetSort {
    public static void main(String[] args) {
        int arr[] = { 8, 4, 5, 7, 1, 3, 6, 2 };
        int temp[] = new int[arr.length]; //归并排序需要一个额外空间
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println("归并排序后=" + Arrays.toString(arr));
    }

    //分+合方法
    public static void mergeSort(int[] arr, int left, int right, int[] temp) {
        if(left < right) {
            int mid = (left + right) / 2; //中间索引
            //向左递归进行分解
            mergeSort(arr, left, mid, temp);
            //向右递归进行分解
            mergeSort(arr, mid + 1, right, temp);
            //合并
            merge(arr, left, mid, right, temp);

        }
    }

    /**
     * 合并的方法
     * @param arr 排序的原始数组
     * @param left 左边有序序列的初始索引
     * @param mid 中间索引
     * @param right 右边索引
     * @param temp 做中转的数组
     */
    public static void merge(int[] arr, int left, int mid, int right, int[] temp) {

        int i = left; // 初始化i, 左边有序序列的初始索引
        int j = mid + 1; //初始化j, 右边有序序列的初始索引
        int t = 0; // 指向temp数组的当前索引

        //(一)先把左右两边(有序)的数据按照规则填充到temp数组
        //直到左右两边的有序序列，有一边处理完毕为止
        while (i <= mid && j <= right) {//继续
            //如果左边的有序序列的当前元素，小于等于右边有序序列的当前元素
            //即将左边的当前元素，填充到 temp数组
            //然后 t++, i++
            if(arr[i] <= arr[j]) {
                temp[t] = arr[i];
                t += 1;
                i += 1;
            } else { //反之,将右边有序序列的当前元素，填充到temp数组
                temp[t] = arr[j];
                t += 1;
                j += 1;
            }
        }

        //(二)把有剩余数据的一边的数据依次全部填充到temp
        while( i <= mid) { //左边的有序序列还有剩余的元素，就全部填充到temp
            temp[t] = arr[i];
            t += 1;
            i += 1;
        }

        while( j <= right) { //右边的有序序列还有剩余的元素，就全部填充到temp
            temp[t] = arr[j];
            t += 1;
            j += 1;
        }
        
        //(三)将temp数组的元素拷贝到arr
        t = 0;
        int tempLeft = left; //
        //第一次合并 tempLeft = 0 , right = 1 //tempLeft = 2  right=3 // tempLeft=0 right=3
        //最后一次 tempLeft = 0  right = 7
        while(tempLeft <= right) {
            arr[tempLeft] = temp[t];
            t += 1;
            tempLeft += 1;
        }
    }
}

快速排序

快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

排序原理：

1. 首先设定一个分界值，通过该分界值将数组分成左右两部分；

2. 将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；

3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组也就排序好了。

切分原理：

1. 把一个数组切分成两个子数组的基本思想：

2. 找一个基准值，用两个指针分别指向数组的头部和尾部；

3. 先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；

4. 再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；

5. 交换当前左边指针位置和右边指针位置的元素；

6. 重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。

public static void quickSort(int[] arr,int left, int right) {
    int l = left; //左下标
    int r = right; //右下标
    //pivot 中轴值
    int pivot = arr[(left + right) / 2];
    int temp = 0; //临时变量，作为交换时使用
    //while循环的目的是让比pivot 值小放到左边
    //比pivot 值大放到右边
    while (l < r) {
        //在pivot的左边一直找,找到大于等于pivot值,才退出
        while (arr[l] < pivot) {
            l += 1;
        }
        //在pivot的右边一直找,找到小于等于pivot值,才退出
        while (arr[r] > pivot) {
            r -= 1;
        }
        //如果l >= r说明pivot 的左右两的值，已经按照左边全部是
        //小于等于pivot值，右边全部是大于等于pivot值
        if (l >= r) {
            break;
        }

        //交换
        temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;

        //如果交换完后，发现这个arr[l] == pivot值 相等 r--， 前移
        if (arr[l] == pivot) {
            r -= 1;
        }
        //如果交换完后，发现这个arr[r] == pivot值 相等 l++， 后移
        if (arr[r] == pivot) {
            l += 1;
        }
    }

    // 如果 l == r, 必须l++, r--, 否则为出现栈溢出
    if (l == r) {
        l += 1;
        r -= 1;
    }
    //向左递归
    if (left < r) {
        quickSort(arr, left, r);
    }
    //向右递归
    if (right > l) {
        quickSort(arr, l, right);
    }
}

基数排序

基数排序（radix sort）属于“分配式排序”（distribution sort），又称”桶子法”（bucket sort）或bin sort，顾名思义，它是通过键值的各个位的值，将要排序的元素分配至某些“桶”中，达到排序的作用。基数排序属于效率高的稳定性排序法，是桶排序的扩展。

基数排序是1887年赫尔曼-何乐礼发明的。它是这样实现的：将整数按位数切割成不同的数字，然后按每个位数分别比较。

思想：将所有待比较数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列。

public static void radixSort(int[] arr) {
    //得到数组中最大的数的位数
    int max = arr[0]; //假设第一数就是最大数
    for (int i = 1; i < arr.length; i++) {
        if (arr[i] > max) {
            max = arr[i];
        }
    }
    //得到最大数是几位数
    int maxLength = (max + "").length();
    
    //定义一个二维数组，表示10个桶, 每个桶就是一个一维数组
    //说明
    //1. 二维数组包含10个一维数组
    //2. 为了防止在放入数的时候，数据溢出，则每个一维数组(桶)，大小定为arr.length
    //3. 明确，基数排序是使用空间换时间的经典算法
    int[][] bucket = new int[10][arr.length];

    //为了记录每个桶中，实际存放了多少个数据,定义一个一维数组来记录各个桶的每次放入的数据个数
    //比如：bucketElementCounts[0] , 记录的就是 bucket[0] 桶的放入数据个数
    int[] bucketElementCounts = new int[10];
    for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
        //(针对每个元素的对应位进行排序处理)， 第一次是个位，第二次是十位，第三次是百位..
        for (int j = 0; j < arr.length; j++) {
            //取出每个元素的对应位的值
            int digitOfElement = arr[j] / n % 10;
            //放入到对应的桶中
            bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
            bucketElementCounts[digitOfElement]++;
        }
        //按照这个桶的顺序(一维数组的下标依次取出数据，放入原来数组)
        int index = 0;
        //遍历每一桶，并将桶中是数据，放入到原数组
        for (int k = 0; k < bucketElementCounts.length; k++) {
            //如果桶中，有数据，我们才放入到原数组
            if (bucketElementCounts[k] != 0) {
                //循环该桶即第k个桶(即第k个一维数组), 放入
                for (int l = 0; l < bucketElementCounts[k]; l++) {
                    //取出元素放入到arr
                    arr[index++] = bucket[k][l];
                }
            }
            //第i+1轮处理后，需要将每个 bucketElementCounts[k] = 0 ！！！！
            bucketElementCounts[k] = 0;

        }
        //System.out.println("第"+(i+1)+"轮，对个位的排序处理 arr =" + Arrays.toString(arr));
    }
}

说明：

1. 基数排序是对传统桶排序的扩展，速度很快。

2. 基数排序是经典的空间换时间的方式，占用内存很大，当对海量数据排序时，容易造成OutOfMemoryError。

3. 基数排序是稳定的。（注：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中,r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的）

4. 有负数的数组，我们不用基数排序来进行排序，如果要支持负数，参考：https://code.i-harness.com/zh-CN/q/e98fa9

常见排序算法对比

稳定：如果a原本在b前面，而a=b，排序之后a仍然在b 的前面
不稳定：如果a原本在b的前面，而a=b，排序之后a可能会出现在b的后面
内排序：所有排序操作都在内存中完成
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行
时间复杂度：一个算法执行所耗费的时间
空间复杂度：运行完一个程序所需内存的大小
n：数据规模
k：”桶”的个数
In-place：不占用额外内存
Out-place：占用额外内存