插入排序

简单插入排序

从第一个元素开始，该元素可以认为已经被排序；
取出下一个元素，在已经排序的元素序列中从后向前扫描；
如果该元素（已排序）大于新元素，将该元素移到下一位置；
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
将新元素插入到该位置；

时间复杂度：平均复杂度为O(n^2)，最好情况O(n)，最坏情况O(n^2)
空间复杂度：O(n)
稳点性：稳定

public class InsertSort {
    public static void insertSort(int[] data){
        int len = data.length-1;
        int i,j;
        //从1开始，第0位只有一个数，认为是有序的
        for(i=1; i<=len; i++){
            int compare = data[i];
            for(j=i-1; j>=0; j--){
                if(compare > data[j]){
                    break;
                }else {
                    data[j+1] = data[j];
                }
            }
            //跳出循环后j自减了一次，所以要加1
            data[j+1] = compare;
        }
    }
    public static void main(String[] args) {
        int[] data = new int[]{8,6,12,45,78,2,36,54};
        insertSort(data);
        System.out.println(Arrays.toString(data));
    }
}

希尔排序

在插入排序的基础上，先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

选择一个增量序列t1，t2，…，tk
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

时间复杂度：平均复杂度为O(n^2)，最好情况O(n)，最坏情况O(n^2)
空间复杂度：O(n)
稳点性：不稳定

public class ShellSort {
    public static void shellSort(int[] data){
        int len = data.length-1;
        int i,j;
        for(int n=len/2; n>=1; n=n/2){
            //与插入排序相比，i=1换成i=n
            for(i=n; i<=len; i++){
                int compare = data[i];
                //j--换成 j-=n
                for(j=i-n; j>=0; j=j-n){
                    if(compare > data[j]){
                        break;
                    }else {
                        //j+1换成j+n
                        data[j+n] = data[j];
                    }
                }
                //j+1换成j+n
                data[j+n] = compare;
            }
        }
    }
    public static void main(String[] args) {
        int[] data = {9,6,4,24,35,7,31,26};
        shellSort(data);
        System.out.println(Arrays.toString(data));
    }
}

选择排序

简单选择排序

选择排序是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小元素，然后与未排序序列的起始元素交换位置。剩余未排序序列重复以上操作

初始状态：数组data[len]未排序，有序序列为空，无序序列从数组第一个元素到最后一个元素
经过第i轮排序(i=1,2,3…n-1)，当前有序区和无序区分别为data(0..i-1)和data(i…len）从data(i…len)中选出最小的元素与data[i]交换位置
n-1趟结束，数组排序完成

时间复杂度：平均复杂度为O(n^2)，最好情况O(n^2)，最坏情况O(n^2)
空间复杂度：O(n)
稳点性：不稳定

public class SelectSort {
    public static void selectSort(int[] data){
        int len = data.length-1;
        int i,j;
        for(i=0; i<=len; i++){
            int min = i;
            for(j=i+1; j<=len; j++){
                if(data[j] < data[min]){
                    //更新最小下标
                    min = j;
                }
            }
            //元素互换
            int temp = data[i];
            data[i] = data[min];
            data[min] = temp;
        }
    }
    public static void main(String[] args) {
        int[] data = new int[]{8,6,12,45,78,2,36,54};
        selectSort(data);
        System.out.println(Arrays.toString(data));
    }
}

冒泡排序

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较相邻的两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

比较相邻的元素，如果第一个比第二个大，就交换它们两个；
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
针对所有的元素重复以上的步骤，除了最后一个

时间复杂度：平均复杂度为O(n^2)，最好情况O(n^2)，最坏情况O(n^2)
空间复杂度：O(n)
稳点性：不稳定

public class BubbleSort {
    public static void bubbleSort(int[] data){
        int len = data.length-1;
        int i,j;
        //记录尾部已排好序的元素个数
        for(i=0; i<len; i++){
            for(j=0; j<len-i; j++){
                if(data[j] > data[j+1]){
                    int temp = data[j];
                    data[j] = data[j+1];
                    data[j+1] = temp;
                }
            }
        }
    }
    public static void main(String[] args) {
        int[] data = new int[]{8,6,12,45,78,2,36,54};
        bubbleSort(data);
        System.out.println(Arrays.toString(data));
    }
}

快速排序

快速排序的基本思想：选取一个基准数，通过不断交换，以基准数为中心分成两个序列，基准数左边的序列均比基准数小，基准数右边的序列均比基准数大。对这两个序列又选取一个基准数继续上述操作

从数列中挑出一个元素作为基准数
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边），在这个分区退出之后，该基准就处于数列的中间位置
递归地把小于基准值元素的子序列和大于基准值元素的子序列进行上述操作

时间复杂度：平均复杂度为O(nlogn)，最好情况O(nlogn)，最坏情况O(n^2)
空间复杂度：O(n)
稳点性：不稳定

public class QuickSort {
    public static void quickSort(int[] data, int left, int right){
        //区第一个数为基准数
        int base = data[left];
        int ll = left;
        int rr = right;
        //终止条件 ll=rr
        while(ll < rr){
            //找到第一个比base小的数，跳出循环
            while (ll<rr && data[rr] >= base){
                rr--;
            }
            //与基准数交换位置
            if(ll<rr){
                int temp = data[rr];
                data[rr] = data[ll];
                data[ll] = temp;
                ll++;
            }
            while(ll<rr && data[ll] <= base){
                ll++;
            }
            if(ll < rr){
                int temp = data[ll];
                data[ll] = data[rr];
                data[rr] = temp;
                rr--;
            }
            //开始尾递归
            if(left < ll){
                quickSort(data, left, ll-1);
            }
            if(right > rr){
                quickSort(data, rr+1, right);
            }
        }
    }
    public static void main(String[] args) {
        int[] data = new int[]{8,6,12,45,78,2,36,54};
        quickSort(data, 0, data.length-1);
        System.out.println(Arrays.toString(data));
    }
}

归并排序

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

把长度为n的输入序列分成两个长度为n/2的子序列；
对这两个子序列分别采用归并排序；
将两个排序好的子序列合并成一个最终的排序序列。

时间复杂度：平均复杂度为O(nlogn)，最好情况O(nlogn)，最坏情况O(nlogn)
空间复杂度：O(2n)
稳点性：稳定

public class MegerSort {
    public static void main(String[] args) {
        int[] data = {9,6,4,24,35,7,31,26};
        int n = data.length;
        megerSort(data,0,n-1);
        System.out.println(Arrays.toString(data));
    }
    public static void megerSort(int[] data, int left, int right){
        if(left < right){
            int mid = (left + right) / 2;
            megerSort(data, left, mid);
            megerSort(data, mid+1, right);
            meger(data, left, mid, right);
        }
    }
    public static void meger(int[] data, int left, int mid, int right){
        int[] temp = new int[data.length];
        int point1 = left;
        int point2 = mid+1;
        int loc = left;
        while (point1 <= mid && point2 <= right){
            if(data[point1] < data[point2]){
                temp[loc] = data[point1];
                point1 ++;
                loc ++;
            }else {
                temp[loc] = data[point2];
                point2 ++;
                loc ++;
            }
        }
        while (point1 <= mid){
            temp[loc++] = data[point1++];
        }
        while (point2 <= right){
            temp[loc++] =  data[point2++];
        }
        for(int i = left; i<=right; i++){
            data[i] = temp[i];
        }
    }
}