稳定性的意义：如果一组数据只需要一次排序，则稳定性一般是没有意义的，如果一组数据需要多次排序，稳定性是有意义的。例如要排序的内容是一组商品对象，第一次排序按照价格由低到高排序，第二次排序按照销量由高到低排序，如果第二次排序使用稳定性算法，就可以使得相同销量的对象依旧保持着价格高低的顺序展现，只有销量不同的对象才需要重新排序。这样既可以保持第一次排序的原有意义，而且可以减少系统开销。

1.3 七大基于比较的排序-总览

二. 插入排序💭

2.1 🌼直接插入排序🌼

整个区间被分为：有序区间? 无序区间；

每次选择无序区间的第一个元素，在有序区间内选择合适的位置插入。

?代码实现：

   public static void insertSort(long[] array) {
        // 一共要取多少个元素来进行插入过程（无序区间里有多少个元素）
        for (int i = 0; i < array.length - 1; i++) {
            // 有序区间 [0, i]  至少在 i == 0 的时候得有一个元素
            // 无序区间 [i + 1, n)

            // 先取出无序区间的第一个元素，记为 k
            long k = array[i + 1];

            // 从后往前，遍历有序区间
            // 找到合适的位置退出
            // 所谓合适的位置，就是第一次 k >= array[j] 的位置
            int j;
            for (j = i; j >= 0 && k < array[j]; j--) {
                array[j + 1] = array[j];        // 将不符合条件的数据往后般一格
            }

            array[j + 1] = k;
        }
    }

性能分析：

时间复杂度

最坏情况：O(n^2)----数组逆序的情况下

最好情况：O(n)----数组有序的情况下

特点：越有序越快

空间复杂度：O(1)

稳定性：比较是从有序序列的末尾开始，也就是想要插入的元素和已经有序的最大者开始比起，如果比它大则直接插入在其后面，否则一直往前找直到找到它该插入的位置。如果碰见一个和插入元素相等的，那么把要插入的元素放在相等元素的后面。所以，相等元素的前后顺序没有改变，从原无序序列出去的顺序就是排好序后的顺序，所以插入排序是稳定的。

2.2 🌼希尔排序🌼

希尔排序法(Shell Sort)又称缩小增量法。

希尔排序法的基本思想是：先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

当?gap > 1?时都是预排序，目的是让数组更接近于有序。当?gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。希尔排序本身是直接插入排序的一种优化。

?代码实现：

public static void shellSort(int[] array) {
    int gap = array.length;
    while (gap > 1) {
       insertSortGap(array, gap);
       gap = (gap / 3) + 1; // OR gap = gap / 2;
    }
    insertSortGap(array, 1);
}
private static void insertSortGap(int[] array, int gap) {
    for (int i = 1; i < array.length; i++) {
       int v = array[i];
       int j = i - gap;
       for (; j >= 0 && array[j] > v; j -= gap) {
           array[j + gap] = array[j];
       }
       array[j + gap] = v;
   }
}

性能分析：

时间复杂度

最坏情况：O(n^2)----比较难构造

最好情况：O(n)----数组有序的情况下

空间复杂度：O(1)

稳定性：不稳定

三. 选择排序?

3.1 🌻直接选择排序🌻

每一次从无序区间选出最大（或最小）的一个元素，存放在无序区间的最后（或最前），直到全部待排序的数据元素排完。

??代码实现：

public static void selectSort(int[] array){
   for(int i = 0;i < array.length - 1;i++){
       //无序区间:[0,array.length - i)
       //有序区间：[array.length  i,array.length)
       int max = 0;
       for (int j = 1;j < array.length - i;j++){
           if(array[j] > array[max]){
              max = j;
           }
       }
       int t = array[max];
       array[max] = array[array.length - i - 1];
       array[array.length - i - 1] = t;
    }
}

性能分析：

时间复杂度：O(n^2)

空间复杂度：O(1)

稳定性：不稳定

3.2 🌻堆排序🌻

基本原理也是选择排序，只是不在使用遍历的方式查找无序区间的最大(或最小)的数，而是通过堆来选择无序区间的最大(或最小)的数。

注意： 排升序要建大堆；排降序要建小堆。

??代码实现：

public class HeapSort {
    public static void sort(int []arr){
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }

    }

    /**
     * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
     * @param arr
     * @param i
     * @param length
     */
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }

    /**
     * 交换元素
     * @param arr
     * @param a
     * @param b
     */
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

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

性能分析：

时间复杂度：O(n * log(n))

空间复杂度：O(1)

稳定性：不稳定

四. 交换排序🌞

4.1 🌷冒泡排序🌷

在无序区间，通过相邻数的比较，将最大的数冒泡到无序区间的最后，持续这个过程，直到数组整体有序。

?代码实现：

public class bubbleSort {
    public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            boolean isSorted = true;
            for (int j = 0; j < array.length - i - 1; j++) {
                // 相等不交换，保证稳定性
                if (array[j] > array[j + 1]) {
                    heapSort.swap(array, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted) {
                break;
            }
        }
    }
}

性能分析：

时间复杂度

最坏情况：O(n^2)----数据逆序

最好情况：O(n)----数据有序

空间复杂度：O(1)

稳定性：稳定

4.2?🌷快速排序🌷

1. 从待排序区间选择一个数，作为基准值(pivot)；

2. Partition: 遍历整个待排序区间，将比基准值小的（可以包含相等的）放到基准值的左边，将比基准值大的（可以包含相等的）放到基准值的右边；

3. 采用分治思想，对左右两个小区间按照同样的方式处理，直到小区间的长度 == 1，代表已经有序，或者小区间的长度 == 0，代表没有数据。

?代码实现：

public class quickSort {
    public static void quickSort(long[] array) {
        quickSortRange(array, 0, array.length - 1);
    }

    // 为了代码书写方便，我们选择使用左闭右闭的区间表示形式
    // 让我们对 array 中的从 from 到 to 的位置进行排序，其他地方不用管
    // 其中，from，to 下标的元素都算在区间的元素中
    // 左闭右闭的情况下，区间内的元素个数 = to - from + 1;
    private static void quickSortRange(long[] array, int from, int to) {
        if (to - from + 1 <= 1) {
            // 区间中元素个数 <= 1 个
            return;
        }

        // 挑选中区间最右边的元素 array[to]
        // array[to] 还是 array[to - 1] 还是 array[array.length] 还是 array[array.length - 1] 呢？
        int pi = partitionMethodA(array, from, to);
        // 小于等于 pivot 的元素所在的区间如何表示 array, from, pi - 1
        // 大于等于 pivot 的元素所在的区间如何表示 array, pi + 1, to

        // 按照分治算法的思路，使用相同的方式，处理相同性质的问题，只是问题的规模在变小
        quickSortRange(array, from, pi - 1);    // 针对小于等于 pivot 的区间做处理
        quickSortRange(array, pi + 1, to);   // 针对大于等于 pivot 的区间做处理
    }

    /**
     * 以区间最右边的元素 array[to] 最为 pivot，遍历整个区间，从 from 到 to，移动必要的元素
     * 进行分区
     * @param array
     * @param from
     * @param to
     * @return 最终 pivot 所在的下标
     */
    private static int partitionMethodA(long[] array, int from, int to) {
        // 1. 先把 pivot 找出来
        long pivot = array[to];
        // 2. 通过定义 left 和 right 两个下标，将区间划分出来
        int left = from;
        int right = to;
        // [from, left)   都是 <= pivot 的
        // [left, right)  都是未参与比较的
        // [right, to]    都是 >= pivot 的

        // 循环，保证每个元素都参与了和 pivot 的比较
        // 也就是，只要 [left, right) 区间内还有元素，循环就应该继续
        while (left < right) {
//        while (right - left > 0) {
            // 先让左边进行比较

            // 随着 left 在循环过程中一直在 left++，请问 left < right 的条件能一定保证么
            // 不一定，所以，我们时刻进行 left < right 条件的保证
            // 并且，只有在 left < right 成立的情况下，array[left] 和 pivot 的比较才有意义
            // left < right && array[left] <= pivot 的顺序不能交换
            while (left < right && array[left] <= pivot) {
                left++;
            }
            // 循环停止时，说明 array[left] > pivot

            while (left < right && array[right] >= pivot) {
                right--;
            }
            // 循环停止时，说明 array[right] < pivot

            // 两边都卡住时，交换 [left] 和 [right] 位置的元素
            long t = array[left];
            array[left] = array[right];
            array[right] = t;
        }

        // 说明 left == right，说明 [left, right) 区间内一个元素都没有了
        // 所有元素都和 pivot 进行过比较了，然后都在各自应该的位置上了
        // 并且 array[left] 一定是 >= pivot 的第一个元素（不给大家证明了）
        long t = array[to];
        array[to] = array[left];
        array[left] = t;

        // 返回 pivot 最终所在下标
        return left;
    }

    public static void main(String[] args) {
        long[] array = {-1, -1, -1, -1, 8, 7, 6, 5, 4, 3, 2, 1, -1, -1, -1 };

        int pi = partitionMethodA(array, 4, 11);
        System.out.println(pi);
    }
}

性能分析：

时间复杂度

最好情况：O(n * log(n))

平均情况：O(n * log(n))

最坏情况：O(n^2)

空间复杂度：最好 = 平均 =?O(log(n))；最坏 =?O(n)

稳定性：不稳定

五. 归并排序🌈

5.1 🌺归并排序🌺

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

可以看到这种结构很像一棵完全二叉树，本文的归并排序我们采用递归去实现（也可采用迭代的方式去实现）。分阶段可以理解为就是递归拆分子序列的过程，递归深度为log2n。

再来看看治阶段，我们需要将两个已经有序的子序列合并成一个有序序列，比如上图中的最后一次合并，要将[4,5,7,8]和[1,2,3,6]两个已经有序的子序列，合并为最终序列[1,2,3,4,5,6,7,8]，来看下实现步骤。

??代码实现：

public class mergeSort {
    private static void merge(int[] array, int low, int mid, int high) {
        int i = low;
        int j = mid;
        int length = high - low;
        int[] extra = new int[length];
        int k = 0;

        // 选择小的放入 extra
        while (i < mid && j < high) {
            // 加入等于，保证稳定性
            if (array[i] <= array[j]) {
                extra[k++] = array[i++];
            } else {
                extra[k++] = array[j++];
            }
        }

        // 将属于元素放入 extra
        while (i < mid) {
            extra[k++] = array[i++];
        }

        while (j < high) {
            extra[k++] = array[j++];
        }

        // 从 extra 搬移回 array
        for (int t = 0; t < length; t++) {
            // 需要搬移回原位置，从 low 开始
            array[low + t] = extra[t];
        }
    }

    public static void mergeSort(int[] array) {
        mergeSortInternal(array, 0, array.length);
    }
    // 待排序区间为 [low, high)
    private static void mergeSortInternal(int[] array, int low, int high) {
        if (low >= high - 1) {
            return;
        }

        int mid = (low + high) / 2;
        mergeSortInternal(array, low, mid);
        mergeSortInternal(array, mid, high);

        merge(array, low, mid, high);
    }
}

性能分析：

时间复杂度：O(n * log(n))

空间复杂度：O(n)

稳定性：稳定