冒泡排序

public class Bubble {

/*
1. 比较相邻的元素。如果前一个元素比后一个元素大，就交换这两个元素的位置。
2. 对每一对相邻元素做同样的工作，从开始第一对元素到结尾的最后一对元素。最终最后位置的元素就是最大值。
*/
    public static void sort1(Comparable[] arr){
        for (int i = arr.length - 1; i > 0 ;i -- ){ //将较大的数向后移
            for (int j = 0;j < i ;j ++ ){
                if (arr[j].compareTo(arr[j+1])>0){
                    Comparable temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }

            }
        }
    }

    public static void sort2(Comparable[] arr){ //将较小的数向前移
        for (int i = 0; i < arr.length - 1; i ++ ){
            for (int j = arr.length - 1 ; j > i ; j --){
                if(arr[j].compareTo(arr[j-1])<0){
                    Comparable temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }
            }
        }
    }

    public static void sort3(Comparable[] arr){ // 改进版 带flag
        for(int i = 0; i < arr.length - 1; i ++){
            boolean flag = false; //是否交换的标志
            for (int j = arr.length - 1; j > i ; j--){
                if(arr[j].compareTo(arr[j-1])<0){
                    Comparable temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                    flag = true;
                }
            }
            if(flag == false) //若无交换 说明已有序
                return;
        }
    }
}

image.png

选择排序

image.png

public class Select {
    public static void sort(Comparable[] arr){
        for (int i = 0; i < arr.length - 1 ; i ++){
            int min = i; // 记录最小值的下标
            for(int j = i + 1; j < arr.length ; j ++){
                if(arr[j].compareTo(arr[min])<0){
                    min = j;
                }     // 记录当前最小值
            }
            if (min != i){ // 最小值不在第i位 则交换
                Comparable t = arr[i];
                arr[i] = arr [min];
                arr[min] = t;
            }
        }
    }
}

选择排序的时间复杂度分析：
选择排序使用了双层for循环，其中外层循环完成了数据交换，内层循环完成了数据比较，所以我们分别统计数据交换次数和数据比较次数：
数据比较次数：(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;
数据交换次数：N-1
时间复杂度：N^{2/2-N/2+（N-1）=N}2/2+N/2-1;
根据大O推导法则，保留最高阶项，去除常数因子，时间复杂度为O(N^2);

插入排序

排序原理：
1.把所有的元素分为两组，已经排序的和未排序的；
2.找到未排序的组中的第一个元素，向已经排序的组中进行插入；
3.倒叙遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待插入元素放到这个位置，其他的元素向后移动一位；

image.png

public class Insert {
    public static void sort(Comparable[] arr){
        for (int i = 1; i < arr.length ; i ++ ){
            // 当前元素为arr[i] 依次和前面的元素比较 找到一个小于等于arr[i]的元素
            for (int j = i; j > 0 ; j -- ){ // 有序表中 从后往前查找
                if(arr[j-1].compareTo(arr[j])>0){ // 在前面的有序表中找到合适的位置插入
                    Comparable t = arr[j];
                    arr[j] = arr [j-1];
                    arr[j-1] = t;
                }
            }
        }
    }
}

插入排序的时间复杂度分析
插入排序使用了双层for循环，其中内层循环的循环体是真正完成排序的代码，所以，我们分析插入排序的时间复杂度，主要分析一下内层循环体的执行次数即可。
最坏情况，也就是待排序的数组元素为{12,10,6,5,4,3,2,1}，那么：
比较的次数为：
(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2;
交换的次数为：
(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)(N-1)/2=N^2/2-N/2;
总执行次数为：
(N^2/2-N/2)+(N2/2-N/2)=N^2-N;
按照大O推导法则，保留函数中的最高阶项那么最终插入排序的时间复杂度为O(N^2).

希尔排序

排序原理：
1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；
2.对分好组的每一组数据完成插入排序；
3.减小增长量，最小减为1，重复第二步操作。

image.png

增长量 h的确定：增长量h的值每一固定的规则，我们这里采用以下规则：

int h=1
while(h<5){
  h=2h+1；//3,7
}
//循环结束后我们就可以确定h的最大值；
//h的减小规则为：
  h=h/2

public class Shell {
    public static void sort(Comparable[] arr){
        int N = arr.length; // 增量h的最大值 增量递增
        int h = 1;
        while (h < N / 2 ){
            h = h * 2 + 1;
        }
        // 当增量h小于1 排序结束
        while (h >= 1){
            // 找到待插入的元素arr[i]
            // 把 arr[i]插入到arr[i-2h] arr[i - 3h] ... 序列中
            for (int i = h ; i < N ; i ++){
                //arr[j] 就是待插入元素 依次和arr[j-h] arr[j-2h] .. 比较 若 arr[j]小 那么交换位置 反之 arr[j]大 则插入完成
                for(int j = i ; j >= h ; j-=h ){
                    if(arr[j-h].compareTo(arr[j])>0){
                        Comparable t = arr[j];
                        arr[j] = arr [j-h];
                        arr[j-h] = t;
                    }else{
                        break;
                    }
                }
            }
            h /= 2;
        }
    }
}

归并排序

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

image.png

public class Merge {
    private static Comparable[] assist; //辅助数组
    public static void sort(Comparable[] arr){
        assist = new Comparable[arr.length];
        int low = 0;
        int high = arr.length - 1;
        sort(arr,low,high);
    }

    // low 到 high 的元素进行排序
    private static void sort(Comparable[] arr, int low, int high){
        if(high <= low) return;
        int mid = low + (high - low) / 2;
        // 对 low 到 mid 之间的元素进行排序
        sort(arr, low, mid);
        // 对 mid+1 到 high 之间的元素进行排序
        sort(arr,mid+1,high);
        // 对 low - mid , mid - high 这组数据进行归并
        merge(arr, low, mid, high);
    }

    // 对数组中 low - mid 为一组 mid+1 - high 为一组 对两组数组进行归并
    private static void merge(Comparable[] arr, int low, int mid, int high){
        // low 到 mid 这组数据和 mid+1 到 high 这组数据归并到辅助数组assist对应的索引处
        int i = low; //定义一个指针，指向assist数组中开始填充数据的索引
        int p1 = low; //定义一个指针，指向第一组数据的第一个元素
        int p2 = mid + 1; //定义一个指针，指向第二组数据的第一个元素
        //比较左边小组和右边小组中的元素大小，哪个小，就把哪个数据填充到assist数组中
        while (p1 <= mid && p2 <= high) {
            if (arr[p1].compareTo(arr[p2])<0) {
                assist[i++] = arr[p1++];
            } else {
                assist[i++] = arr[p2++];
            }
        }

        //上面的循环结束后，如果退出循环的条件是p1<=mid，则证明左边小组中的数据已经归并完毕，如果退出循环的条件是p2<=high,则证明右边小组的数据已经填充完毕；
        //所以需要把未填充完毕的数据继续填充到assist中
        // 下面两个循环，只会执行其中的一个
        while(p1<=mid){
            assist[i++]=arr[p1++];
        }
        while(p2<=high){
            assist[i++]=arr[p2++];
        }
        //到现在为止，assist数组中，从low到high的元素是有序的，再把数据拷贝到a数组中对应的索引处
        for (int index=low;index<=high;index++){
            arr[index]=assist[index];
        }
    }
}

假设元素的个数为n，那么使用归并排序拆分的次数为log2(n),所以共log2(n)层，那么使用log2(n)替换上面32^3中的3这个层数，最终得出的归并排序的时间复杂度为：log2(n) 2^(log2(n))=log2(n)*n,根据大O推导法则，忽略底数，最终归并排序的时间复杂度为O(nlogn);
归并排序的缺点：
需要申请额外的数组空间，导致空间复杂度提升，是典型的以空间换时间的操作。

快速排序

排序原理：
1.首先设定一个分界值，通过该分界值将数组分成左右两部分；
2.将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于或等于分界值，而右边部分中各元素都大于或等于分界值；
3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

image.png

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

public class Quick {
    public static void sort(Comparable[] a){
        int low = 0;
        int high = a.length - 1;
        sort(a,low,high);
    }
    private static void sort(Comparable[] a,int low, int high){
        if(high<=low) return;
        // low - high 进行划分
        int partition = partition(a, low , high);
        sort(a,low,partition-1);
        sort(a,partition+1,high);
    }

    private static int partition(Comparable[] a, int low, int high){
        Comparable pivot = a[low];
        while (low < high){
            while(low < high && a[high].compareTo(pivot)>0 ) --high;
            a[low] = a [high];
            while (low < high && a[low].compareTo(pivot)<0 ) ++ low;
            a[high] = a[low];
        }
        a[low] = pivot; // 枢轴元素放到最终位置
        return low;// 存放枢轴的位置
    }
}

快速排序时间复杂度分析：
快速排序的一次切分从两头开始交替搜索，直到left和right重合，因此，一次切分算法的时间复杂度为O(n),但整个快速排序的时间复杂度和切分的次数相关。
最优情况：每一次切分选择的基准数字刚好将当前序列等分。
如果我们把数组的切分看做是一个树，那么上图就是它的最优情况的图示，共切分了 logn次，所以，最优情况下快速排序的时间复杂度为O(nlogn);
最坏情况：每一次切分选择的基准数字是当前序列中最大数或者最小数，这使得每次切分会有一个子组，那么总共就得切分n次，所以，最坏情况下，快速排序的时间复杂度为O(n^2);

稳定性

常见排序算法的稳定性：
冒泡排序：
只有当arr[i]>arr[i+1]的时候，才会交换元素的位置，而相等的时候并不交换位置，所以冒泡排序是一种稳定排序算法。
选择排序:
选择排序是给每个位置选择当前元素最小的,例如有数据{5(1)，8 ，5(2)， 2， 9 },第一遍选择到的最小元素为2，所以5(1)会和2进行交换位置，此时5(1)到了5(2)后面，破坏了稳定性，所以选择排序是一种不稳定的排序算法。
插入排序：
比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么把要插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。
希尔排序：
希尔排序是按照不同步长对元素进行插入排序 ,虽然一次插入排序是稳定的，不会改变相同元素的相对顺序，但在不同的插入排序过程中，相同的元素可能在各自的插入排序中移动，最后其稳定性就会被打乱，所以希尔排序是不稳定的。
归并排序：
归并排序在归并的过程中，只有arr[i]<arr[i+1]的时候才会交换位置，如果两个元素相等则不会交换位置，所以它并不会破坏稳定性，归并排序是稳定的。
快速排序：
快速排序需要一个基准值，在基准值的右侧找一个比基准值小的元素，在基准值的左侧找一个比基准值大的元素，然后交换这两个元素，此时会破坏稳定性，所以快速排序是一种不稳定的算法。