note/algorithm/2、算法.md

算法的5个特点

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

选择排序

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

不稳定的排序

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从小到大。

稳定排序

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大或者内层循环到了最左侧则终止循环。

稳定排序

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连接