一、简单排序

1.1Comparable接口介绍

需求：
1.定义一个学生类Student，具有年龄age和姓名username两个属性，并通过Comparable接口提供比较规则；
2.定义测试类Test，在测试类Test中定义测试方法Comparable getMax（Comparable c1, Comparable c2）完成测试

package algorithm.sort;
//1.定义一个学生类Student，具有年龄age和姓名username两个属性，并通过Comparable接口提供比较规则；
public class Student implements Comparable<Student>{
    private String username;
    private int age;
    public String getUsername() {
        return username;
    }
    public void setUsername(String username) {
        this.username = username;
    }
    public int getAge() {
        return age;
    }
    public void setAge(int age) {
        this.age = age;
    }
    @Override
    public String toString() {
        return "Student{" +
                "username='" + username + '\'' +
                ", age=" + age +
                '}';
    }
    @Override
    public int compareTo(Student o) {
        return this.getAge() - o.getAge();
    }
}

package algorithm.test;
import algorithm.sort.Student;
//2.定义测试类Test，在测试类Test定义测试方法Comparable getMax(Comparable c1, Comparable c2)完成测试
public class TestComparable {
    public static void main(String[] args){
//        创建两个Student对象，并调用getMax方法，完成测试
        Student s1 = new Student();
        s1.setUsername("张三");
        s1.setAge(18);
        Student s2 = new Student();
        s2.setUsername("李四");
        s2.setAge(20);
        Comparable max = getMax(s1, s2);
        System.out.println(max);
    }
    public static Comparable getMax(Comparable c1, Comparable c2){
        int result = c1.compareTo(c2);
// 如果result<0，则c1比c2小
//如果result>0, 则c1比c2大；
//如果result==0, 则c1和c2一样大
        if(result >= 0){
            return c1;
        }else{
            return c2;
        }
    }
}

1.2 冒泡排序（时间复杂度O(n2)）

排序原理：

比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。
对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大
值。

类名	Bubble
构造方法	Bubble()
成员方法	1.private static boolean greater(Comparable v, Comparable w) 判断响铃元素大小 2.private static void exch(Comparable[] a, int i, int j)交换数组内相邻元素 3.public static void sort(Comparable[] a):对数组进行排序

package algorithm.sort;
public class Bubble {
//    1.判断大小
    private static boolean greater(Comparable v, Comparable w){
//        result>0 则v>w
        return v.compareTo(w) > 0;
    }
//    2.交换位置
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
//    3.对数组内的元素排序
//  双重for循环 1.外层循环控制数据对比轮数  2.内层循环控制每轮对比次数
    public static void sort(Comparable[] a){
        for(int i = a.length - 1; i > 0 ; i--){
            for(int j = 0; j < i; j++){
                if (greater(a[j], a[j+1])){
                    exch(a, j, j+1);
                }
            }
        }
    }
}

package algorithm.test;
import algorithm.sort.Bubble;
import java.util.Arrays;
public class TestBubble {
    public static void main(String[] args) {
        Integer[] arr = {4,3,7,9,1};
        Bubble.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

1.3选择排序(时间复杂度O(n2))

排序原理：（外层循环进行交换，内层循环寻找当前轮中最小值所在的索引）
1.每一次遍历的过程中，都假定第一个索引处的元素是最小值，和其他索引处的值依次进行比较，如果当前索引处的值大于其他某个索引处的值，则假定某个索引处的值为最小值，最后可以找到最小值所在的索引
2.交换第一个索引处和最小值所在的索引处的值

类名	Selection
构造方法	Selection()
成员方法	1.private static boolean greater(Comparable v, Comparable w) 判断响铃元素大小 2.private static void exch(Comparable[] a, int i, int j)交换数组内相邻元素 3.public static void sort(Comparable[] a):对数组进行排序

package algorithm.sort;

public class Selection {
//    1.比较大小
    private static boolean greater(Comparable v, Comparable w){
        return v.compareTo(w)>0;
    }
//    2.交换两个元素的位置
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
//   3.排序
    public static void sort(Comparable[] a){
        for(int i=0; i<a.length - 1; i++){
            int min_index = i;
            for (int j =i+1; j<a.length; j++){
//                if (greater(a[i], a[j])){
//                    exch(a, i, j);
//                }
                if(greater(a[min_index], a[j])){
                    min_index = j;
                }
            }
//            交换最小元素所在索引
            exch(a, i, min_index);
        }
    }
}

package algorithm.test;

import algorithm.sort.Selection;

import java.util.Arrays;

public class TestSelection {
    public static void main(String[] args) {
        Integer[] arr = {4,6,8,7,9,2,10,1};
        Selection.sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}

1.4 插入排序(时间复杂度O(n2))

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

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

排序原理：
1.将所有元素分成两组，一组已经排序，一组未排序的
2.未排序的元素从索引1开始，一直到最末尾元素，即a.length
3.倒序索引已经排序好的元素，和未排序的元素进行比较，如果比未排序的元素大则交换，直到交换到比它小的元素，说明结束，跳出循环即可

package algorithm.sort;

public class Insertion {
//    1.判断大小
    private static boolean greater(Comparable v, Comparable w){
        return v.compareTo(w)>0;
    }
//    2.交换位置
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
//    3.插入排序
    public static void sort(Comparable[] a){
//        1.会分成两组，一组已排序的，一组未排序的
//        2.找到未排序的组中的第一个元素，向已排序中的进行插入
//        3.倒序遍历已经排序的元素，依次和待插入的元素进行比较，比待插入元素大就进行交换,比待插入元素小则结束跳出循环即可
        for(int i=1; i<a.length; i++){
            for (int j=i; j>0; j--){
                if(greater(a[j-1], a[j])){
                    exch(a, j-1, j);
                }else {
                    break;
                }
            }
        }

    }
}

package algorithm.test;

import algorithm.sort.Insertion;

import java.io.PrintWriter;
import java.util.Arrays;

public class TestInsertion {
    public static void main(String[] args) {
        Integer[] a = {4,3,2,10,12,1,5,6};
        Insertion.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

二、高级排序

2.1希尔排序

希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。
排序原理：
1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；2.对分好组的每一组数据完成插入排序；3.减小增长量，最小减为1，重复第二步操作。

package algorithm.sort;

public class Shell {
//    1.比较大小
    private static boolean greater(Comparable v, Comparable w){
        return v.compareTo(w)>0;
    }
//    2.交换
    private static void exch(Comparable[] a, int i, int j){
        Comparable temp;
        temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
//    1.选定一个增长量h，按照增长量h数据分组的依据，对数据进行分组
//    2.对分好组的每一组数据完成插入排序
//    3.减少增长量，最小减为1，重复第二步操作
    public static void sort(Comparable[] a){
//        1.确定增长量h的值
        int h = 1;
        while (h < a.length/2){
            h = 2*h + 1;
        }
//        2.希尔排序
//        当增长量小于1，排序结束
        while(h>=1){
// 2.2 找到待插入的元素,每次分组后第一个待插入的元素都是h
            for(int i = h; i < a.length; i ++){
                for (int j = i; j>=h; j -=h){
//                    a[j]就是待插入元素，依次和a[j - h], a[j - 2h]...a[j - 3h]比较，如果a[j]小则交换，否则结束
                    if(greater(a[j-h], a[j])){
                        exch(a, j-h, j);
                    }else {
                        break;
                    }

                }

            }
//      2.1减小h的值
        h = h /2;
        }

    }
}

package algorithm.test;
import algorithm.sort.Insertion;

import java.util.Arrays;

public class TestShell {
    public static void main(String[] args) {
        Integer[] a = {9,1,2,5,7,4,8,6,3,5};
        Insertion.sort(a);
        System.out.println(Arrays.toString(a));
    }
}

2.2 归并排序（时间复杂度（O（nlog(n)）））

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

成员变量	private static Comparable[] assit:完成归并操作需要的辅助数组
成员方法	1.public static void sort(Comparable[] a):对数组内的元素进行排序 2.private static void sort(Comparable[]a, int lo, int hi):对数组a中从索引lo到索引hi之间的元素进行排序 3.private static void merge(Comparable[] a, int lo, int mid, int hi):从索引lo到索引mid为一个子组，从索引mid+1到索引hi为另一个子组，把数组a中的这两个子组的数据合并成一个有序的大组（从索引lo到索引hi） 4.private static boolean less(Comparable v, Comparable w):判断v是否小于w 5.private static void exch(Comparable[] a, int i ,int j):交换a数组中，索引i和索引j处的值

成员变量

private static Comparable[] assit:完成归并操作需要的辅助数组

成员方法

1.public static void sort(Comparable[] a):对数组内的元素进行排序
2.private static void sort(Comparable[]a, int lo, int hi):对数组a中从索引lo到索引hi之间的元素进行排序
3.private static void merge(Comparable[] a, int lo, int mid, int hi):从索引lo到索引mid为一个子组，从索引mid+1到索引hi为另一个子组，把数组a中的这两个子组的数据合并成一个有序的大组（从索引lo到索引hi）
4.private static boolean less(Comparable v, Comparable w):判断v是否小于w
5.private static void exch(Comparable[] a, int i ,int j):交换a数组中，索引i和索引j处的值

对于merge函数的执行流程：

package algorithm.sort;

public class Merge {
//    归并需要的辅助数组
    private static Comparable[] assist;
//    比较v元素是否小于W元素
    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 temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }
//    对数组中元素进行排序
    public static void sort(Comparable[] a){
//        1.初始化辅助数组assit
        assist = new Comparable[a.length];
//        2.定义一个lo变量，和hi变量，分别记录数组中最小的索引和最大的索引
        int lo = 0;
        int hi = a.length - 1;
//        3.调用sort重载方法完成数组
        sort(a, lo, hi);
    }
//    对数组a从lo到hi的元素进行排序
    private static void sort(Comparable[] a, int lo, int hi){
//        做安全性校验
//        递归函数的出口，hi=lo，说明已经分到了每组都只有1个数
        if(hi<=lo){
            return;
        }
//       对lo到hi之间的数据分成两个组
        int mid = lo + (hi - lo)/2;
//        分别对每一组数据进行排序
        sort(a, lo, mid);
        sort(a, mid+1, hi);
//        再把两个组中的数据进行归并
        merge(a, lo, mid, hi);
    }
//    对数组中，从lo到mid为一组，从mid+1到hi为一组，对这两组数据进行归并
    private static void merge(Comparable[] a, int lo, int mid, int hi){
//        1.定义三个指针
       int i = lo;// 定义一个指针，指向assist数组归并到辅助数组assit对应的索引处
       int p1 = lo;//定义一个指针，指向第一组数组的第一个元素
       int p2 = mid + 1;//定义一个指针，指向第二组数据的第一个元素
//        2.遍历，移动p1和p2指针，比较对应索引处的值，找出小的那个，放到辅助数组的索引处
        while(p1<=mid&&p2<=hi){
            if (less(a[p1],a[p2])){
                assist[i++] = a[p1++];
            }else{
                assist[i++] = a[p2++];
            }
        }
//        3.遍历，如果p1指针没有走完，那么顺序移动p1指针，把对应的元素放到辅助数组的对应索引处
        while (p1<=mid){
            assist[i++] = a[p1++];
        }
//        3.2遍历，如果p2的指针没有走完，那么顺序移动p2指针，把对应的元素放到辅助数组的对应索引处
        while (p2<=hi){
            assist[i++] = a[p2++];
        }
//        4.把辅助数组中的元素拷贝到原数组中
        for (int index=lo; index <= hi; index++){
            a[index] = assist[index];
        }
    }
}

package algorithm.test;
import algorithm.sort.Bubble;
import algorithm.sort.Merge;

import java.util.Arrays;

public class TestMerge {
    public static void main(String[] args) {
        Integer[] arr = {8, 4, 5, 7, 1, 3, 6, 2};
        Merge.sort(arr);
        System.out.println(Arrays.toString(arr));
    }

}

2.3快速排序

它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一
部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序
过程可以递归进行，以此达到整个数据变成有序序列
排序原理：
1.首先设定一个分界值，通过该分界值将数组分成左右两部分；
2.将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于
或等于分界值，而右边部分中各元素都大于或等于分界值；
3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两
部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当
左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

成员方法

1.public static void sort(Comparable[] a):对数组内的元素进行排序
2.private static void sort(Comparable[]a, int lo, int hi):对数组a中从索引lo到索引hi之间的元素进行排序
3.private static int partition(Comparable[] a, int lo, int hi):对数组a中，从索引lo到索引hi之间的元素进行分组，并返回分组界限对应的索引（从索引lo到索引hi）
4.private static boolean less(Comparable v, Comparable w):判断v是否小于w
5.private static void exch(Comparable[] a, int i ,int j):交换a数组中，索引i和索引j处的值

主要步骤：切分：
把一个数组切分成两个子数组的基本思想：
1.找一个基准值，用两个指针分别指向数组的头部和尾部；
2.先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；
3.再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；
4.交换当前左边指针位置和右边指针位置的元素；
5.重复2,3,4步骤，直到左边指针的值大于右边指针的值停止

package algorithm.sort;

public class Qucik {
    public static void sort(Comparable[] a){
        int lo = 0;
        int hi = a.length -1 ;
        sort(a, lo, hi);
    }
    private static void sort(Comparable[]a, int lo, int hi){
        if (lo>=hi){
            return;
        }
//        对a数组中从lo到hi的元素进行切分
        int partition = partition(a, lo, hi);
//        对左边分组进行排序
        sort(a, lo, partition - 1);
//        对右边分组进行排序
        sort(a, partition+1, hi);
    }
    private static int partition(Comparable[]a, int lo,int hi){
//        1.找到基准值
        Comparable key = a[lo];
//        2.定义两个指针，left指向lo，right指向hi的后面一个元素
        int left = lo;
        int right = hi + 1;
//        3.进行切分
        while(true){
//            先从右向左扫描，直到扫描到第一个比key小的元素，停止扫描
            while(less(key, a[--right])){
                if (right<=lo){
                    break;
                }
            }
//            再从左向右扫描，直到扫描到第一个比key大的元素，停止扫描
            while (less(a[++left],key)){
                if (left>=right){
                    break;
                }
            }
//            如果left>=right则停止循环，否则交换left和right的位置的值
            if(left>=right){
                break;
            }else {
                exch(a,left,right);
            }
        }
        //            交换最后right索引出和基准值所在的索引处的值
        exch(a, lo, right);
        return right;
    }
    private static boolean less(Comparable v, Comparable w){
        return v.compareTo(w)<0;
    }
    private static void exch(Comparable[] a,int i,int j){
        Comparable temp = a[i];
        a[i] = a[j];
        a[j] = temp;

    }
}

三、排序的稳定性

稳定性的定义：
数组arr中有若干元素，其中A元素和B元素相等，并且A元素在B元素前面，如果使用某种排序算法排序后，能够保
证A元素依然在B元素的前面，可以说这个该算法是稳定的。