为了面试，时隔一年不得不重新复习数据结构与算法，这次重新复习很有收获，以前在上课总有不清晰的知识，通过这次手写一遍和敲一遍代码，以前不清晰的知识都变得清晰了，果然学编程还是得多敲代码，多敲代码，多敲代码，也要多总结，多总结，多总结。
这个文章只是总结笔记，有错误请指出，谢谢。

   这里要讲排序，所以肯定会在元素之间进行比较，而Java提供了一个接口Comparable就是用来定义排序规则的,封装类都实现了该接口，所以Integer等封装类有排序规则，自定义的类也可以实现Comparable来拥有排序规则

时间复杂度: O(N`2)

稳定性: 稳定

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

需求

排序前：{4,5,6,3,2,1}

排序后：{1,2,3,4,5,6}

排序原理：

1. 比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。

2. 对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值。

import java.util.Arrays;

//冒泡排序 大的往后放（交换位置） 从0开始往后比较
//时间复杂度 O(N`2)
public class Bubble {

    //将数组a排序 a={4,5,6,3,2,1}
    public static void sort(Comparable[] a){
        //每次循环 忽略上次的 最后一位 4,5,6,3,2,1>4,5,3,2,1, 6 忽略6
        for(int i=a.length-1;i>0; i--){
            for(int j=0;i>j;j++){
                if(greater(a[j],a[j+1])){ //6,3 返回true
                    exch(a,j,j+1); //6,3 3,6
                }
            }
        }
    }

    //比较v元素是否大于W元素
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0; //6-3>0 返回true
    }

    //数组元素i和j交换  6,3
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i]; //6
        a[i] = a[j]; //3
        a[j] = t; //6
    }

    //测试
    public static void main(String[] args) {
        //封装类 Integer 已经实现Comparable接口 的比较规则
        Integer[] a={4,5,6,3,2,1};
        Bubble.sort(a);
        System.out.println(Arrays.toString(a));
    }

}

时间复杂度: O(N`2)

稳定性: 不稳定

选择排序是一种更加简单直观的排序方法。

需求：

排序前：{4,6,8,7,9,2,10,1}

排序后：{1,2,4,5,7,8,9,10}

排序原理：

1. 每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引处的值，则假定其他某个索引出的值为最小值，最后可以找到最小值所在的索引；

2. 交换第一个索引处和最小值所在的索引处的值；

import java.util.Arrays;

//选择排序
/*
1.假定当前索引的值是最小值 minIndex=i
2.往后比较 找到比当前的值小的索引，
3.则该索引为当前最小值  minIndex=j
4.重复这3个步骤，j<a.length 找到最小值
5.交换第一位和最小值得位置
 */
public class Selection {
    //将数组a排序 a={4,6,8,7,9,2,10,1}
    //如第一轮遍历找到 最小值1 1,6,8,7,9,2,10,4 忽略1 从后一位遍历
    //如第一轮遍历找到 最小值2 1,6,8,7,9,2,10,4 忽略2 从后一位遍历 ...
    public static void sort(Comparable[] a){
        for(int i=0;i<=a.length-2;i++){
            int minIndex = i; //假定当前索引的值是最小值
            //往后比较 找到比当前的值小的索引  j<a.length 找到最小值 1
            for(int j = i+1;j<=a.length-1;j++){
                if(greater(a[i],a[j])){ //4>2  2>1  则该索引为当前最小值  minIndex=j
                    minIndex = j;
                }
            }
            //当前第一位的4和当前的最小值1交换位置
            exch(a,i,minIndex); 
        }
    }

    //比较v元素是否大于W元素
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0;  //4-2>0 2-1>0 返回true
    }

    //数组元素i和j交换  4,1
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i]; //4
        a[i] = a[j]; //1
        a[j] = t; //4
    }

    //测试
    public static void main(String[] args) {
        //封装类 Integer 已经实现Comparable接口 的比较规则
        Integer[] a={4,6,8,7,9,2,10,1} ;
        Selection.sort(a);
        System.out.println(Arrays.toString(a));
    }

}

时间复杂度: O(N`2)

稳定性: 稳定

插入排序（Insertion sort）是一种简单直观且稳定的排序算法。

插入排序的工作方式非常像人们排序一手扑克牌一样。开始时，我们的左手为空并且桌子上的牌面朝下。然后，我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置，我们从右到左将它与已在手中的每张牌进行比较。

需求：

排序前：{4,3,2,10,12,1,5,6}

排序后：{1,2,3,4,5,6,10,12}

排序原理：

1. 把所有的元素分为两组，已经排序的和未排序的；

2. 找到未排序的组中的第一个元素，向已经排序的组中进行插入；

3. 倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位；

import java.util.Arrays;

//插入排序
/*
    循环,比较当前值和后一位比较，如果当前值比后一位大，则交换位置，否则位置不变,跳出循环
    {4,3,2,10,12,1,5,6}
    4>3大交换位置  4>2大交换位置 4<10 位置不变 10<12  位置不变  ...
 */
public class Insertion {
    //将数组a排序 a={4,3,2,10,12,1,5,6}
    public static void sort(Comparable[] a){
        for(int i=1;i<a.length;i++){
            for(int j=i;j>0;j--){
                if(greater(a[j-1],a[j])){ //当前值和后一位比较 4>3
                   exch(a,j-1,j);  //4,3 交换位置
                }else{
                    break; //否则，位置不变，跳出循环
                }
            }
        }
    }

    //比较v元素是否大于W元素
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0; //4-3>0 返回true
    }

    //数组元素i和j交换  4,3
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i]; //4
        a[i] = a[j]; //3
        a[j] = t; //4
    }

    //测试
    public static void main(String[] args) {
        //封装类 Integer 已经实现Comparable接口 的比较规则
        Integer[] a={4,3,2,10,12,1,5,6} ;
        Insertion.sort(a);
        System.out.println(Arrays.toString(a));
    }

}

时间复杂度: O(n^s) ,1<s<2

稳定性:不稳定

希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。

需求：

排序前：{9,1,2,5,7,4,8,6,3,5}

排序后：{1,2,3,4,5,5,6,7,8,9}

排序原理：

1. 选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；

2. 对分好组的每一组数据完成插入排序；

3. 减小增长量，最小减为1，重复第二步操作。

package com.mai.myAlgorithm.sort;
//希尔排序

import java.util.Arrays;

public class Shell1 {

    //对数组a中的元素进行排序 a={9,1,2,5,7,4,8,6,3,5}
    public static void sort(Comparable[] a){
        //1.根据数组a的长度，确定增长量h的初始值；
        int h = a.length/2;

        /* 
           第一次循环 h=5 索引 0 和 5 1和 6 2和 7... 比较 如果后面小于前面 则交换位置
           第二次循环 h=2 索引 0 和 2 1 和 3  2 和 4... 比较 如果后面小于前面 则交换位置
           第三次循环 h=1 索引 0 和 1 1 和 2  2 和 3... 比较 如果后面小于前面 则交换位置
        */
        while (h>=1) {
            for (int j = 0; j < a.length - h; j++) { //10-5 =5 10-2=8 10-1=9
                //  0 和 5 1和 6 2和 7... 比较 9>4 返回true 1<8 false
                if (greater(a[j], a[j + h])) { 
                    exch(a, j, j + h);  //交换
                }
            }
            h = h / 2; //减小h的值 5 2 1
        }
    }

    //比较v元素是否大于W元素
    private static boolean greater(Comparable v,Comparable w){
        return v.compareTo(w)>0; //9-4>0 返回true 1-8 返回false
    }

    //数组元素i和j交换  9,4
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i]; //9
        a[i] = a[j]; //4
        a[j] = t; //9
    }
    
    //测试
    public static void main(String[] args) {
        //封装类 Integer 已经实现Comparable接口 的比较规则
        Integer[] a={9,1,2,5,7,4,8,6,3,5};
        Shell1.sort(a);
        System.out.println(a.length);
        System.out.println(Arrays.toString(a));
    }

}

时间复杂度: O(nlogn)

稳定性:稳定

归并排序需要额外的数组空间

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

需求：
排序前：{8,4,5,7,1,3,6,2}
排序后：{1,2,3,4,5,6,7,8}
排序原理：
1.尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止。
2.将相邻的两个子组进行合并成一个有序的大组；
3.不断的重复步骤2，直到最终只有一个组为止

import java.util.Arrays;

//归并排序
public class Merge {

    //辅助数组 归并排序需要额外的数组空间
   private static Comparable[] assist;

    // 对数组a中的元素进行排序 a={8, 4, 5, 7, 1, 3, 6, 2};
    public static void sort(Comparable[] a){
        //初始化 辅助数组
        assist = new Comparable[a.length];
        int lo = 0;  //左指针
        int hi =a.length-1; //右指针

        //调用sort重载方法完成数组a中，从索引lo到索引hi的元素的排序（整个数组排序）
        sort(a,lo,hi);

    }

    //对数组a中从lo到hi的元素进行排序  a={8, 4, 5, 7, 1, 3, 6, 2}
    private static void sort(Comparable[] a,int lo,int hi){
        //做安全性校验；
        if(hi<=lo){
            return;
        }
        //对lo到hi之间的数据进行分为两个组 分组
        int mid = lo + (hi-lo)/2;  //mid 0+(7-0)/2 = 3

        //分别对每一组数据进行 排序 （递归）
        /*
        第一次左边的数组 8, 4, 5, 7
        第二次  左边的数组 8, 4, 右边的 5, 7
        第三次 ...
        */
        sort(a,lo,mid);
        sort(a,mid+1,hi); //右边的数组 1, 3, 6, 2 同左边的一样分组

        //再把两个组中的数据进行归并 合并
        merge(a,lo,mid,hi);

    }

    // 对数组中，从lo到mid为一组，从mid+1到hi为一组，对这两组数据进行归并
    private static void merge(Comparable[] a,int lo,int mid, int hi){
        //定义三个指针
        int i = lo; //辅助数组下标
        int p1=lo; //辅助数组左指针 0 -> 1 2 3 
        int p2=mid+1; //辅助数组中间往右的指针 4-> 5 6 7

        //遍历，移动p1指针和p2指针，比较对应索引处的值，找出小的那个，放到辅助数组的对应索引处
        /*
            a={8, 4, 5, 7, 1, 3, 6, 2}
            最后一步合并的两组 4578 和 1236
            i=0  p1=0 p2=4 hi=7
            i++ 先复值再自增
         */
        while (p1<=mid && p2<=hi){
            //a[0]=4>a[4]=1 false 4>2 false 4>3 false 4<6 true  5<6 true 7>6 false
            if(less(a[p1],a[p2])){
                assist[i++] = a[p1++];  //4<6 4 5
            }else{
                assist[i++] = a[p2++]; //assist[0]=a[4]=1 2 3 6 右边的数组走完了 退出循环
            }
        }

        //遍历，如果左边的数组没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处
        while (p1<=mid){
            assist[i++] = a[p1++];
        }

        //遍历，如果右边边的数组没有走完，那么顺序移动p2指针，把对应的元素放到辅助数组的对应索引处
        while (p2<=hi){
            assist[i++] = a[p2++];
        }

        //把辅助数组中的元素拷贝到原数组中
        for(int index=lo;index<=hi;index++){
            a[index]=assist[index];
        }

    }

    //比较v元素是否小于w元素 4-1>0 返回false
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w)<0; 
    }

    //测试
    public static void main(String[] args) {
        //封装类 Integer 已经实现Comparable接口 的比较规则
        Integer[] a = {8, 4, 5, 7, 1, 3, 6, 2};
        Merge.sort(a);
        System.out.println(a.length);
        System.out.println(Arrays.toString(a));
    }
}

时间复杂度

最优时间复杂度: O(nlogn)

最坏时间复杂度: O(N`2)

平均时间复杂度: O(nlogn)

稳定性: 不稳定

    快速排序是对冒泡排序的一种改进。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

需求：

排序前:{6, 1, 2, 7, 9, 3, 4, 5, 8}

排序后:{1, 2, 3, 4, 5, 6, 7, 8, 9}

排序原理：

1. 首先设定一个分界值，通过该分界值将数组分成左右两部分；

2. 将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；

3. 然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

4. 重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

   
   

切分原理：

把一个数组切分成两个子数组的基本思想：

1. 找一个基准值，用两个指针分别指向数组的头部和尾部；

2. 先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；

3. 再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；

4. 交换当前左边指针位置和右边指针位置的元素；

5. 重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。

   
   

import java.util.Arrays;

//快速排序
public class Quick {

    //对数组内的元素进行排序 a={6, 1, 2, 7, 9, 3, 4, 5, 8}
    public static void sort(Comparable[] a){
        //定义数组的左右指针调用重载的sort方法排序整个数组
        int lo = 0;
        int hi = a.length-1;
        sort(a,lo,hi);

    }

    //对数组a中从索引lo到索引hi之间的元素进行排序 ,先分组，再排序
    private static void sort(Comparable[] a,int lo,int hi){
        //安全性校验
        if(hi<=lo){
            return;
        }

        //需要对数组中lo索引到hi索引处的元素进行分组（左子组和右子组）；
        int partition = partition(a,lo,hi); //返回的是分组的分界值所在的索引，分界值位置变换后的索引

        //让左子组有序
        sort(a,lo,partition-1);  // partition = 5 2

        //让右子组有序
        sort(a,partition+1,hi); // partition =  5 7

    }

    // a={6, 1, 2, 7, 9, 3, 4, 5, 8}
    //对数组a中，从索引 lo到索引 hi之间的元素进行分组，并返回分组界限对应的索引
    private static int partition(Comparable[] a,int lo,int hi){
        //确定分界值
        Comparable key = a[lo];  // a[0]=6

        //定义两个指针，分别指向待切分元素的最小索引处和最大索引处的下一个位置
        int left = lo ; //0
        int right = hi+1; //9

        //++i 先自增再复值

        //切分
        while(true) {
            //先从右往左扫描，移动right指针，找到一个比分界值小的元素，停止退出循环
            while (less(key, a[--right])) {  //6-8 key-a[--right]>=0 false 退出循环
                if (right == lo) {  // 安全性校验 安心左右指针相遇，退出循环
                    break;
                }
            }

            //再从左往右扫描，移动left指针，找到一个比分界值大的元素，停止退出循环
            while (less(a[++left], key)) { //1-6 key-a[--right]<0  2-6  true  7-6  false 退出循环
                if (left == hi) {  //安全性校验 左右指针相遇，退出循环
                    break;
                }
            }
            //判断 left>=right,如果是，则证明元素扫描完毕，结束循环，如果不是，则交换元素即可
            if (left >= right) {
                break;
            } else {
                exch(a, left, right);
            }
        }

        //交换分界值
        exch(a,lo,right);

        return right; //返回值

    }


    //比较v元素是否小于w元素1-6<0 true
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w)<0; 
    }

    //数组元素i和j交换
    private static void exch(Comparable[] a,int i,int j){
        Comparable t = a[i]; 
        a[i] = a[j]; 
        a[j] = t; 
    }


    //测试
    public static void main(String[] args) {
        //封装类 Integer 已经实现Comparable接口 的比较规则
        Integer[] a = {6, 1, 2, 7, 9, 3, 4, 5, 8};
        Quick.sort(a);
        System.out.println(Arrays.toString(a));
    }
}