算法（Java）

一、排序

1.简单选择排序（O(n*n)）

【思路】找出数组中最小的元素，将其与第一个元素交换位置，然后再在剩下的元素中找出最小的元素，并与数组的第二个元素交换位置。

【特点】

原地排序，不稳定。
运行时间和输入无关。一个已经有序的数组和一个元素随机排列的数组所用的时间一样。
移动数据最少。交换次数和数组大小是线性关系，每次交换都有一个元素位于正确的位置。

import java.util.Arrays;
public class SelectSort {
    /**
     * 简单选择排序
     * @param a
     */
    public static void sort(int[] a) {
        for(int i =0;i<a.length;i++) {
            int minIndex = i;
            for(int j=i+1;j<a.length;j++) {
                if(a[minIndex]>a[j]) {
                    minIndex = j;
                }
            }
            if(a[i]>a[minIndex]) {
                int temp = a[i];
                a[i] = a[minIndex];
                a[minIndex] = temp;
            }
            System.out.println("第"+(i+1)+"次："+Arrays.toString(a));
        }
    }
    public static void main(String[] args) {
        int[] a = {9,8,7,5,4,2,1};
        System.out.println("排序前:"+Arrays.toString(a));
        sort(a);
    }
}
输出：
排序前:[9, 8, 7, 5, 4, 2, 1]
第1次：[1, 8, 7, 5, 4, 2, 9]
第2次：[1, 2, 7, 5, 4, 8, 9]
第3次：[1, 2, 4, 5, 7, 8, 9]
第4次：[1, 2, 4, 5, 7, 8, 9]
第5次：[1, 2, 4, 5, 7, 8, 9]
第6次：[1, 2, 4, 5, 7, 8, 9]
第7次：[1, 2, 4, 5, 7, 8, 9]

2.插入排序（O(n*n)）

【特点】

原地排序，稳定。
插入排序所需的时间与输入的元素的初始顺序有关。

import java.util.Arrays;
public class InsertSort {
    /**
     * 插入排序
     * @param a
     */
    public static void sort(int[] a) {
        for(int i = 1;i<a.length;i++) {
            for(int j=0;j<i;j++) {
                if(a[j]>a[i]) {
                    int temp = a[i];
                    for(int k = i;k>0;k--) {
                        exch(a,k,k-1);
                    }
                    a[j] = temp;
                    break;
                }
            }
            System.out.println("第"+(i)+"次："+Arrays.toString(a));
        }
    }
    public static void  exch(int[]a ,int i,int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
    public static void main(String[] args) {
        int[] a = {9,8,7,5,4,2,2,1};
        System.out.println("排序前："+Arrays.toString(a));
        sort(a);
    }
}

输出：
排序前：[9, 8, 7, 5, 4, 2, 1]
第1次：[8, 9, 7, 5, 4, 2, 1]
第2次：[7, 8, 9, 5, 4, 2, 1]
第3次：[5, 7, 8, 9, 4, 2, 1]
第4次：[4, 5, 7, 8, 9, 2, 1]
第5次：[2, 4, 5, 7, 8, 9, 1]
第6次：[1, 2, 4, 5, 7, 8, 9]

3.冒泡排序（O(n*n)）

【思路】遍历数组，若相邻的两个元素大小顺序不对，交换这两个元素的位置。

【特点】

稳定。
每次冒泡，会有一个数字位于正确的位置。

import java.util.Arrays;
public class BubbleSort {
    /**
     * 冒泡排序
     * @param a
     */
    public static void sort(int[] a) {//大数从数组后面冒出
        for(int i = a.length-1;i>0;i--) {
            for(int j = 0;j<i;j++) {
                if(a[j]>a[j+1]) {
                    int temp = a[j];
                    a[j] = a[j+1];
                    a[j+1] = temp;
                }
            }
            System.out.println("第"+(a.length-i)+"次："+Arrays.toString(a));
        }
    }
public static void sort1(int[] a) {//小数从数组前面冒出
        for(int i = 0;i<a.length;i++) {
            for(int j = a.length-1;j>i;j--) {
                if(a[j]<a[j-1]) {
                    int temp = a[j];
                    a[j] = a[j-1];
                    a[j-1] = temp;
                }
            }
            System.out.println("第"+(i+1)+"次："+Arrays.toString(a));
        }
    }
    public static void main(String[] args) {
        int[] a = {9,8,7,5,4,2,2,1};
        System.out.println("排序前："+Arrays.toString(a));
        sort(a);
    }
}
输出：
排序前：[9, 8, 7, 5, 4, 2, 2, 1]
第1次：[8, 7, 5, 4, 2, 2, 1, 9]
第2次：[7, 5, 4, 2, 2, 1, 8, 9]
第3次：[5, 4, 2, 2, 1, 7, 8, 9]
第4次：[4, 2, 2, 1, 5, 7, 8, 9]
第5次：[2, 2, 1, 4, 5, 7, 8, 9]
第6次：[2, 1, 2, 4, 5, 7, 8, 9]
第7次：[1, 2, 2, 4, 5, 7, 8, 9]

4.希尔排序

【特点】

不稳定。

package com.paixu;
import java.util.Arrays;
public class ShellSort {
    /**
     * 希尔排序
     * @param a
     */
    public static void sort(int[] a) {
        int h = 1;
        int l = a.length;
        while(h<l/3)
            h = h*3+1;
        while(h>=1) {
            for(int i=h;i<l;i++) {
                for(int j=i;j>=h;j--) {
                    if(a[j]<a[j-h]) {
                        int temp = a[j];
                        a[j] = a[j-h];
                        a[j-h] = temp;
                    }
                }
            }
            System.out.println("h="+(h)+"："+Arrays.toString(a));
            h = h/3;
        }
    }
    public static void main(String[] args) {
        int[] a = {9,8,7,5,4,2,2,1};
        System.out.println("排序前："+Arrays.toString(a));
        sort(a);
    }
}
输出：
排序前：[9, 8, 7, 5, 4, 2, 2, 1]
h=4：[4, 2, 2, 1, 9, 8, 7, 5]
h=1：[1, 2, 2, 4, 5, 7, 8, 9]

5.归并（Merge）排序（N*logN）

需要额外的空间，稳定。

【】自顶向下和自底向上

6.快速排序（N*logN）

分治，将一个数组分成两个子数组，将其独立排序。

【思想】以数组第一个元素（key）对元素进行拆分，设置左右指针，分别从左边找到第一个大于key的元素下表，从右边找出第一个大于key的元素下表，交换其位置，最后将key插入到其位置。然后修改key。

归并排序数组是等分的，快排，切分的位置取决于数组的内容。

【特点】

• 不稳定。
• 每次切分就有一个元素处在正确的位置上。

import java.util.Arrays;
public class QuickSort {
    /**
     * 快排
     * @param args
     */

    public static void main(String[] args) {  
        int[] a = {30,25,24,31,28,46,20,40};  
        System.out.println(Arrays.toString(a));  
        quickSort(a);  
        System.out.println(Arrays.toString(a));  
    }  
    public static void quickSort(int[] a) {  
        if(a.length>0) {  
            quickSort(a, 0 , a.length-1);  
        }  
    }  
    public static void quickSort(int[] a,int low,int high) {
        if(low>high)//跳出递归
            return;
        int key = a[low];
        int i = low;
        int j = high;
        int temp = i;
        while(i<j) {
            while(i<j&&a[j] > key) {
                j--;                
            }
            a[i] = a[j];
            temp = i;
            while(i<j&&a[i] <= key) {
                //必须等于且i<j
                i++;
            }
            a[j] = a[i];
            temp = j;
        }
        a[temp] =key;
        System.out.println(Arrays.toString(a));
        quickSort(a,low,i-1);//key左边快排
        quickSort(a,i+1,high);//key右边快排
    }
    
}
输出：
[30, 25, 24, 31, 28, 46, 20, 40]
[20, 25, 24, 28, 30, 46, 31, 40]
[20, 25, 24, 28, 30, 46, 31, 40]
[20, 24, 25, 28, 30, 46, 31, 40]
[20, 24, 25, 28, 30, 46, 31, 40]
[20, 24, 25, 28, 30, 46, 31, 40]
[20, 24, 25, 28, 30, 40, 31, 46]
[20, 24, 25, 28, 30, 31, 40, 46]
[20, 24, 25, 28, 30, 31, 40, 46]
[20, 24, 25, 28, 30, 31, 40, 46]

---

堆排序（完全二叉树，可以用数组实现而不需要指针）

不稳定。

• 大根堆：父节点都大于等于它的两个儿子结点。
• 小根堆：父节点都小于等于它的两个儿子结点。

    int a[];
    int n = 0;// 数组下标0不使用
    public Duipaixu(int maxN){
        a = new int[maxN+1]; 
    }
    public void exch(int i,int j) {
        int k = a[i];
        a[i] = a[j];
        a[j] = k;
    }
    public void insert(int k) {
        a[++n] = k;
        swim(n);
    }
    public void del(int index) {//k是数组下表
        exch(index,n--);
        sink(index);
    }
    public boolean compare(int i,int j) {
        if(a[i]>a[j])
            return false;
        else return true;
    }
    public void swim(int k){//上浮
        while(k>1&&compare(k/2,k)) {
            exch(k/2,k);
            k = k/2;
        }
    }
    public void sink(int k) {//下沉
        while(2*k<n) {
            int j = 2*k;
            if(j<n&&compare(j,j+1)) {
                j++;
            }
            exch(k,j);
            k = j;
        }
    }
    public void print() {// 输出
        int hang = 2;
        for(int i = 1;i<=n;i++) {
            System.out.print(a[i]+" ");
            if(i == hang-1) {
                hang = hang*2;
                System.out.println();
            }
        }
    }
}

---

二、查找

1.二分查找（时间复杂度O(logN)）

        int l0 = 0; 
        int ln = arr.length-1;
        while (l0<=ln) {
            int mid = l0+(ln-l0)/2;
            System.out.println(l0+"  "+mid+" "+ln);
            if(arr[mid] > key) {
                ln = mid-1;
            }
            else if (arr[mid] < key) {
                l0 = mid+1;
            }
            else return mid;
        }
        return -1;
    }

public static int BinarySearch(int[] a,int key,int low,int high) {// 递归实现
        int mid = low+(high-low)/2;
        if(a[mid]==key) {
            return mid;
        }
        else if(a[mid]>key) {
            return DiguiBinary(a,key,low,mid-1);
        }
        else return DiguiBinary(a,key,mid+1,high);
    }

2.二叉排序树（时间复杂度O(logN)）

---

树

3.B树

B树是一种多路搜索树，主要用在文件系统和数据库系统，文件系统和数据库主要存储在磁盘，B树就是为了降低磁盘I/O次数。

二叉排序树深度是logN，所以时间复杂度是O(logN)，要降低复杂度，就要降低树的深度。它是一种平衡多路查找树。

---

B+树（查找两个值之间的多个元素时）

索引都是排好序的。

• 只有最底层的节点（叶子节点）才保存信息。
• 其它节点（非叶子结点）只是在搜索中用来指引到正确节点的。
• 结点个数多了一倍
• 叶子结点跟后续叶子结点是连接的，
• 插入和删除操作的时间复杂度是 O(log(N)) 。