# 算法的5个特点

1.有穷性
2.确定性(确定的执行流程或者确定的尝试流程)
3.可行性
4.输入
5.输出

# 选择排序

双层循环，内层循环完成后获取最小值，内层循环每次将最小值放到i位置。
0-i之间认为是有序，i-n之间是原始数据，从i-n之间选择最小的元素放到index为i的地方。

不稳定的排序

```Java
private static void selectionSort(int[] arr) {
    if (arr == null || arr.length < 2) {
        return;
    }

    int length = arr.length;
    int tmp;
    for (int i = 0; i < length; i++) {
        int index = i;
        for (int j = i; j < length; j++) {
            // 小于号避免位置交换
            index = arr[j] < arr[index] ? j : index;
        }
        if (index == i) {
            continue;
        }
        tmp = arr[i];
        arr[i] = arr[index];
        arr[index] = tmp;
    }
}
```

# 冒泡排序

双层循环，内层循环两两交换，内层循环完成后将最大值冒泡到最右边。
外层循环index从大到小，内层循环index从小到大。

稳定排序

```Java
private static void bubbleSort(int[] arr){
    int length = arr.length;
    if (arr == null || length < 2) {
        return;
    }

    int tmp;
    for (int i = length - 1; i >= 0; i--) {
        for (int j = 0; j < i; j++) {
            if (arr[j + 1] < arr[j]) {
                tmp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = tmp;
            }
        }
    }
}
```

# 插入排序

每次获取原始数据最前面的那个元素交换到左侧已经有序的数组。
双层循环，外层循环每次递增并获取i，内层循环使用i挨个和0-1的数据比较并交换。如果i比i-1大或者内层循环到了最左侧则终止循环。

稳定排序

```Java
private static void insertSort(int[] arr){
    int length = arr.length;
    if (arr == null || length < 2) {
        return;
    }
    int tmp;
    for (int i = 0; i < length; i++) {
        for (int j = i; j > 0; j--) {
            if (arr[j - 1] > arr[j]) {
                tmp = arr[j - 1];
                arr[j - 1] = arr[j];
                arr[j] = tmp;
            } else {
                break;
            }

        }
    }
}
```

不基于比较的排序，也叫桶排序。对数据样本有要求，但是特定场景可以做到O(N)时间复杂度，基于比较的排序最好能做到O(N*logN)
计数排序 需要指定上下限
基数排序 非负、能用十进制理解的样本

排序的稳定性
稳定排序    冒泡、插入、归并
不稳定排序  选择、快排、堆排序、希尔

|序号|名称   |时间复杂度             |额外空间复杂度|稳定性|
|:-----     |:-----                |:-----|:-----|:-----|:-----| :-----| ----: | :----: |
|1|选择排序  |O(N^2^)               |O(1)         |无|
|2|冒泡排序  |O(N^2^)               |O(1)         |有|
|3|插入排序  |O(N^2^)               |O(1)         |有|
|4|归并排序  |O(N$\times$ $\log$N)  |O(N)         |有|
|5|随机快排  |O(N$\times$ $\log$N)  |O($\log$N)   |无|
|6|堆排序    |O(N$\times$ $\log$N)  |O(1)         |无|
|7|计数排序  |O(N)                  |O(M)         |有|
|8|基数排序  |O(N)                  |O(N)         |有|
|9|希尔排序  |                  |         ||

* 不基于比较的排序，对样本数据有严格要求，不容易改写
* 基于比较的排序，只要规定好两个样本怎么比较大小就可以直接复用
* 基于比较的排序，时间复杂度的极限是O(N$\times$ $\log$N)
* 时间复杂度O(N$\times$ $\log$N)、额外空间复杂度低于O(N)、且稳定的基于比较的排序是不存在的
* 为了绝对的速度选择快排、为了省空间选堆排序、为了稳定性选归并

工程上的改进

* 考虑稳定性，Arrays.sort，基础类型使用快排，有比较器使用归并排序。
* 充分利用O(N$\times$ $\log$N)和O(N^2^)排序各自的优势，O(N^2^)排序的常数项小，在数据样本不大(比如小于60)的时候是比O(N$\times$ $\log$N)要快的。

单链表回文
L1、L2、L3、L4、L5、L6、L7、R1、R2、R3、R4、R5、R6、R7变成L1、R7、L2、R6、L3、R5、L4、R4、L5、R3、L6、R2、L7、R1

单链表找中间节点
单链表荷兰国旗问题
给定表头，将节点数据按照小于、等于、大于K连接