算法笔记

特征

• 有穷性
• 确切性
• 输入项
• 输出项
• 可行性

算法优劣评定

• 时间复杂度
• 空间复杂度
• 正确性
• 可读性
• 健壮性

时间复杂度

• O（N^3）
• O（N^2）
• O（N）
• O（NlogN） 查找二叉树
• O（logN）
• O(1)

排序算法	平均时间复杂度
冒泡排序	O(n2)
选择排序	O(n2)
插入排序	O(n2)
希尔排序	O(n1.5)
快速排序	O(N*logN)
归并排序	O(N*logN)
堆排序	O(N*logN)
基数排序	O(d(n+r))

算法分析方法

• 递归法 汉诺塔
• 穷举法 暴力密码破解法
• 贪心算法 加勒比海盗偷宝藏
• 分治法 乐毅连下齐72城二分搜索
• 动态规划法 导弹拦截
• 迭代法 超能生的兔子
• 回溯法 八皇后

排序算法

1、插入排序

    在要排序的一组数中，假定前n-1个数已经排好序，
现在将第n个数插到前面的有序数列中，
使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。

• 直接插入排序

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

• 二分插入排序

public static void binaryInsert(int[] arr) {
    for (int i = 1; i < arr.length; i++) {
        int left = 0;
        int right = i-1;
        int key = arr[i];//待插入的数据
        while(left <= right){
            int mid = (left+right)/2;
            if (key < arr[mid]) {
                right = mid -1;
            }else{
                left = mid +1;
            }
        }
        for (int j = i; j > left; j--) {
            arr[j] = arr[j-1];
        }
        arr[left] = key;
    }
}

• 希尔排序

希尔排序是非稳定排序算法.
在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。
直至增量为1,此时数据序列基本有序,最后进行插入排序。

public static void shell(int[] arr) {
    int n = arr.length;
    int h = 1;
    while(h < n/3){
        h = h*3+1;
    }
    while(h >= 1){
        for (int i = h; i < n; i++) {
            for (int j = i; j >= h && arr[j] < arr[j-h]; j-=h) {
                int tem = arr[j];
                arr[j] = arr[j-h];
                arr[j-h] = tem;
            }
        }
        h /= 3;
    }
}

2、选择排序

在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
。。。
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

• 简单选择排序

public static void choose(int[] arr){
    for (int i = 0; i < arr.length; i++) {
        for (int j = i; j < arr.length; j++) {
            if (arr[j] < arr[i]) {
                int tem = arr[i];
                arr[i] = arr[j];
                arr[j] = tem;
            }
        }
    }
}

• 堆排序

    不稳定排序
    将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
将其与末尾元素进行交换，此时末尾就为最大值。
然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
如此反复执行，便能得到一个有序序列了

public static void heap(int[] arr) {
    int n = arr.length;
    for (int i = n/2-1; i >= 0; i--) {
        //这一步不是单单地找出最大的节点，而是形成大根堆，对后面有帮助
        adjustHeap(arr,i,n);  
    }
    for (int j = n-1; j > 0; j--) {
        int tem = arr[0];
        arr[0] = arr[j];
        arr[j] = tem;

        adjustHeap(arr, 0, j);
    }
}

private static void adjustHeap(int[] arr, int parent, int length) {
    int tem = arr[parent];
    int child = 2*parent+1;  //左孩子
    while(child < length){
        if (child+1 < length && arr[child] < arr[child+1]) {//右孩子存在，并且右孩子大于左孩子
            child++;  //从左孩子切换到右孩子
        }
        if (tem > arr[child]) {
            break;  //如果当前元素大于左右孩子节点，则跳出
        }
        arr[parent] = arr[child]; //从左右孩子中选出较大的给父节点
        //把小元素向下调整
        parent = child;
        child = 2*child + 1;
    }       
    arr[parent] = tem;
}

3、交换排序

交换排序的基本方法是：两两比较待排序记录的排序码，
交换不满足顺序要求的偶对，直到全部满足位置。
常见的冒泡排序和快速排序就属于交换类排序。

• 冒泡排序

从数组中第一个数开始，依次遍历数组中的每一个数，通过相邻比较交换，每一轮循环下来找出剩余未排序数的中的最大数并”冒泡”至数列的顶端。

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

• 快速排序

1)从待排序的n个记录中任意选取一个记录（通常选取第一个记录）为分区标准;
(2)把所有小于该排序列的记录移动到左边，把所有大于该排序码的记录移动到右边，
中间放所选记录，称之为第一趟排序；
(3)然后对前后两个子序列分别重复上述过程，直到所有记录都排好序。

public static void quick(int[] arr) {
    if (arr.length > 0) {
        quick(arr,0,arr.length-1);
    }
}

private static void quick(int[] arr, int lo, int hi) {
    if (lo >= hi) {
        return;
    }
    int first = lo;
    int  last = hi;
    int key = arr[first];
    while(first < last){
        while(first < last && arr[last] >= key){
            last--;
        }
        arr[first] = arr[last];
        while(first < last && arr[first] <= key){
            first++;
        }
        arr[last] = arr[first];   
    }
    arr[first] = key;
    quick(arr, lo, first-1);
    quick(arr, first+1, hi);        
}

4、归并排序

归并排序是利用归并的思想实现的排序方法，
该算法采用经典的分治策略（分治法将问题分(divide)成一些小的问题然后递归求解，
而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。

public static void merge(int[] arr) {
    int tem[] = new int[arr.length]; 
    merge(arr,0,arr.length-1,tem);
}

private static void merge(int[] arr, int left, int right, int[] tem) {
    if (left < right) {
        int mid = (left+right)/2;
        merge(arr,left,mid,tem);
        merge(arr,mid+1,right,tem);
        mergeSub(arr,left,mid,right,tem);
    }
}

private static void mergeSub(int[] arr, int left, int mid, int right,
                             int[] tem) {
    int i = left;
    int j = mid +1;
    int third = 0;
    while(i <= mid && j <= right){
        if (arr[i] <= arr[j]) {
            tem[third++] = arr[i++];
        }else{
            tem[third++] = arr[j++];
        }           
    }
    while(i <= mid){
        tem[third++] = arr[i++];
    }
    while(j <= right){
        tem[third++] = arr[j++];
    }
    //将tem中的元素全部拷贝到原数组中
    third = 0;
    while(left <= right){
        arr[left++] = tem[third++];
    }
}

5、基数排序

基数排序是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法。
它是一种稳定的排序算法。
多关键字排序中有两种方法：最高位优先法(MSD)和最低位优先法（LSD）。

public static void radix(int[] arr) {
    if (arr.length <= 0) {
        return;
    }
    int times = 0,max=arr[0]; //times为数组中最大位数
    for (int i = 0; i < arr.length; i++) {
        if (max < arr[i]) {
            max = arr[i];
        }
    }
    while(max > 0){
        max = max/10;
        times++;
    }
    //-------------------------
    int[][]temp = new int[10][arr.length]; //数组的第一维表示可能的余数0-9
    int[]num = new int[10]; //数组num[i]用来表示该位是i的数的个数
    for (int i = 0; i < times; i++) {
        for (int j = 0; j < arr.length; j++) {
            int x = arr[j]%(int)Math.pow(10, i+1)/(int)Math.pow(10, i);
            //x 为当前数所在的当前位 0-9
            temp[x][num[x]++] = arr[j];
        }
        int t = 0;
        for (int j = 0; j < 10; j++) {
            if (num[j] != 0) {
                for(int k = 0; k < num[j]; k++){
                    arr[t++] = temp[j][k];
                }
            }
            num[j] = 0;
        }
    }
}