排序

所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。

稳定性

假定在等待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的
通俗点说，现在有一个整形数组，里面只有三个元素? 3， 2? ，2，经过排序之后，后面两个2的相对位置不能发生改变，就可以理解为，前一个为哥哥，后一个为弟弟，排序前哥哥在前，弟弟在后，排序后，依旧如此，而不能出现弟弟在前，哥哥在后的这种顺序，一定不发生相对位置的改变就是稳定的，除此之外都是不稳定的

内部排序

数据元素全部放在内存中的排序。

外部排序

数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序
?

2.排序算法的目的是什么？

我自己的理解就是为了使这些关键字变得有序，方便某时的增删查改，或者是使这些关键字变得赏心悦目，不在混乱

3.常见的排序算法有哪些？

插入排序

直接插入排序
希尔排序（缩小增量排序）

选择排序

选择排序
堆排序

交换排序

冒泡排序
快速排序

归并排序

归并排序

提示：在代码实现部分只会呈现排序的方法，在测试的部分会附完整代码！！！

一，插入排序

1.基本思想

插入排序的基本思想就是，一个一个，挨个比较来进行排序，把我们要插入的元素插入到相应的位置
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

2.代码实现?

    //七种常见的排序算法----->插入排序
    public static void insertSort(int[] array){
        //外层循环--->取到数组中的每一个元素，进行插入
        for (int i = 1; i < array.length; i++) {
            //将元素插入到序列中
            //k表示要插入元素的值
            //end表示要移动的元素的下标
            int k = array[i];
            int end = i - 1;
            while(end >= 0 && k < array[end]){
                array[end + 1] = array[end];
                end--;
            }
            //表示要么这个元素是最小的，要么比end位置的元素大
            array[end + 1] = k;
        }
    }

3.性能分析

（1）应用场景：

有序的序列或者接近有序的序列
这个序列元素个数比较少

（2）时间复杂度：

在我所做的测试用例中，这刚好是最差情况，时间复杂度为?O(N^2)

（3）空间复杂度：

?因为是在数组本身上面做的改动，并未借助新的辅助空间? ，空间复杂度为 O(1)

（4）稳定性：

在这个上面有一个小细节：
这个判断符号是可以给成“<="的，不会影响结果，但是，会让两个相同的元素交换位置，不过，在绝大多数场景下，这个等于号是不需要的，因此，直接插入排序是稳定的?

（5）不适合使用的场景：

序列不有序，最差情况下刚好是需要序列的逆序
数据量较大或很大

4.测试

public class Sort1 {
    //七种常见的排序算法----->插入排序
    public static void insertSort(int[] array){
        //外层循环--->取到数组中的每一个元素，进行插入
        for (int i = 1; i < array.length; i++) {
            //将元素插入到序列中
            //k表示要插入元素的值
            //end表示要移动的元素的下标
            int k = array[i];
            int end = i - 1;
            while(end >= 0 && k < array[end]){
                array[end + 1] = array[end];
                end--;
            }
            //表示要么这个元素是最小的，要么比end位置的元素大
            array[end + 1] = k;
        }
    }
    //为了比较数组排序前后的变化
    public static void print(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] array = {9,8,7,6,5,4,3,2,1,0};
        print(array);
        insertSort(array);
        print(array);
    }
}

二，希尔排序（缩小增量排序）

1.基本思想

对于希尔排序来说，他也是插入排序的一种优化算法，对于更加无序，数据量大的序列，起到了很好地作用
利用gap来确定，每个元素之间的间隔，把这些个元素先排成有序的，对于整个序列来说，他也成功的比较有序
以此类推，当每次gap--的时候，代表着循环少了一次，也代表着，序列更加的倾向于有序，不再是很无序，让很庞杂的数据趋于有序的这种规范
当最后一次gap = 1的时候，实际上就是一次插入排序，只不过在这次排序中，需要交换的数据已经只需要很小的交换量了，大大的提高了插入排序对于大数据的排序速度

2.代码实现?

    //七种常见的排序算法 ----> 希尔排序
    public static void shellSort(int[] array) {
        int gap = 3;
        //循环的趟数，直到gap为0的时候
        while (gap > 0) {
            //与插入排序一样的思路，这次是增加了间隔，为了减小相应的排序难度
            for (int i = 1; i < array.length; i++) {
                int k = array[i];
                int end = i - gap;

                while(end >= 0 && k < array[end]){
                    array[end + gap] = array[end];
                    end -= gap;
                }

                array[end + gap] = k;
            }
            gap--;
        }
    }

3.性能分析

（1）应用场景：

在我看来，正如基本思想当中说的，希尔排序就是在插入排序的基础上，对于不能在大数据或数据不趋近于有序时的优化算法，使得插入排序更加的完善

（2）时间复杂度：

希尔排序的时间复杂度一直是耐人寻味的，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定（以下片段取自《数据结构(C语言版)》--- 严蔚敏）

因此可以近似的认为希尔排序的时间复杂度为O(n ^ (3/2))

（3）空间复杂度：

因为希尔排序是插入排序算法的一种优化，因此，希尔排序的空间复杂度也为O(1)

（4）稳定性：

相比于插入排序，希尔排序加入gap这个参数，使得每个元素并不是逐一比较的，他是按照所给的gap为区间进行挨个比较的，因此，存在相同元素改变相对位置的情况，因此，是不稳定的

（5）不适合使用的场景：

无序或者不趋近于有序的序列
数据量巨大的情况下

4.测试

public class Sort2 {
    //七种常见的排序算法 ----> 希尔排序
    public static void shellSort(int[] array) {
        int gap = 3;
        //循环的趟数，直到gap为0的时候
        while (gap > 0) {
            //与插入排序一样的思路，这次是增加了间隔，为了减小相应的排序难度
            for (int i = 1; i < array.length; i++) {
                int k = array[i];
                int end = i - gap;

                while(end >= 0 && k < array[end]){
                    array[end + gap] = array[end];
                    end -= gap;
                }

                array[end + gap] = k;
            }
            gap--;
        }
    }

    //为了方便看到排序前后数组的变化
    public static void print(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] array = {9,8,7,6,5,4,3,2,1,0};
        print(array);
        shellSort(array);
        print(array);
    }
}

三，选择排序

1.基本思想

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完
在元素集合array[i]--array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个（第一个）元素交换
在剩余的array[i]--array[n-2]（array[i+1]--array[n-1]）集合中，重复上述步骤，直到集合剩余1个元素

2.代码实现?

基础版本

    //七种常见排序算法 ---->选择排序
    //基本思想就是在相应的数组中寻找最大的，当排完一次最后一个元素的位置向前走直到最后只剩一个元素
    public static void selectSort(int[] array){
        //进行的趟数
        int end = array.length - 1;
        while(end >= 0){
            //对找到的最大元素进行标记，初始值给为0，每次从最开始的位置开始寻找
            int pos = 0;
            //进行查找最大元素的过程
            for (int i = 0; i <= end; i++) {
                if(array[pos] < array[i]){
                    pos = i;
                }
            }
            //判断pos的位置是否在即将要放的位置，如果不是，就进行交换
            if(pos != end){
                int temp = array[pos];
                array[pos] = array[end];
                array[end] = temp;
            }
            end--;
        }
    }

优化版本

优化版本的关键在于，充分运用寻找的那个过程，既然，在基础版本里寻找了最大的元素，我们考虑是也一起寻找最小的元素，只不过在交换时，需要考虑一下最小的元素是否在最大元素需要交换的位置，其余的思想全部一致

    //选择排序的优化---->其思想就是把找最大的过程效益最大化，既然都已经找最大的了，最小的也直接一起找，只不过交换的位置有所不同
    public static void selectSortOp(int[] array){
        int end = array.length - 1;
        while(end >= 0){
            int maxPos = 0;
            int minPos = 0;
            for (int i = 0; i <= end ; i++) {
                if(array[maxPos] < array[i]){
                    maxPos = i;
                }

                if(array[minPos] > array[i]){
                    minPos = i;
                }
            }

            //进行比较
            if(maxPos != end){
                int temp = array[maxPos];
                array[maxPos] = array[end];
                array[end] = temp;
            }

            //此时要注意，如果最小的元素在最后一个位置，当进行最大元素的交换后，最小的元素已经不在对应的位置了
            if(minPos == end){
                minPos = maxPos;
            }
            if(minPos != 0){
                int temp = array[minPos];
                array[minPos] = array[0];
                array[0] = temp;
            }

            end--;
        }
    }

3.性能分析

（1）应用场景：

直接选择排序思想非常好理解，但是效率不是很好，很少使用

（2）时间复杂度：

两层循环嵌套形式，并且它的两层循环必须走满，因此，时间复杂度为O(N ^ 2)

（3）空间复杂度：

没有借助于辅助空间。因此空间复杂度为O(1)

（4）稳定性：

因为，每次都是循环都不是挨个交换，因此是不稳定的

4.测试

两个版本的代码均在一起，并且测试均通过，因此，测试结果只放一个

package day20211112;

public class Sort3 {
    //七种常见排序算法 ---->选择排序
    //基本思想就是在相应的数组中寻找最大的，当排完一次最后一个元素的位置向前走直到最后只剩一个元素
    public static void selectSort(int[] array){
        //进行的趟数
        int end = array.length - 1;
        while(end >= 0){
            //对找到的最大元素进行标记，初始值给为0，每次从最开始的位置开始寻找
            int pos = 0;
            //进行查找最大元素的过程
            for (int i = 0; i <= end; i++) {
                if(array[pos] < array[i]){
                    pos = i;
                }
            }
            //判断pos的位置是否在即将要放的位置，如果不是，就进行交换
            if(pos != end){
                int temp = array[pos];
                array[pos] = array[end];
                array[end] = temp;
            }
            end--;
        }
    }

    //选择排序的优化---->其思想就是把找最大的过程效益最大化，既然都已经找最大的了
    //最小的也直接一起找，只不过交换的位置有所不同
    public static void selectSortOp(int[] array){
        int end = array.length - 1;
        while(end >= 0){
            int maxPos = 0;
            int minPos = 0;
            for (int i = 0; i <= end ; i++) {
                if(array[maxPos] < array[i]){
                    maxPos = i;
                }

                if(array[minPos] > array[i]){
                    minPos = i;
                }
            }

            //进行比较
            if(maxPos != end){
                int temp = array[maxPos];
                array[maxPos] = array[end];
                array[end] = temp;
            }

            //此时要注意，如果最小的元素在最后一个位置
            //当进行最大元素的交换后，最小的元素已经不在对应的位置了
            if(minPos == end){
                minPos = maxPos;
            }
            if(minPos != 0){
                int temp = array[minPos];
                array[minPos] = array[0];
                array[0] = temp;
            }

            end--;
        }
    }
    public static void print(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] array = {9,8,7,6,5,4,3,2,1,0};
        print(array);
        //selectSort(array);
        selectSortOp(array);
        print(array);
    }
}

四，堆排序

1.基本思想

堆是一个完全二叉树，每个结点最多只有两个孩子，堆排序便是借助了优先级队列的特性，如果要升序---->建大堆，如果要降序------>建小堆
首先是对堆本身进行向下调整，进而对每次调整的元素（堆顶元素）来进行向下调整，并对有效元素个数进行相应的减少，是为了不让当前最大或者最小的元素再来进行调整，以此类推

2.代码实现?

    //七种常见排序算法----->堆排序
    //堆排序的思想就是按照堆删除的思想来完成
    //向下调整
    public static void shiftDown(int[] array,int size,int parent){
        int child = parent * 2 + 1;
        while(child < size){
            if(child  + 1 < size && array[child] < array[child + 1]){
                child = child + 1;
            }

            if(array[parent] < array[child]){
                int temp = array[parent];
                array[parent] = array[child];
                array[child] = temp;

                parent = child;
                child = parent * 2 + 1;
            }else{
                return;
            }
        }
    }
    
    //实现堆排序的方法
    public static void heapSort(int[] array){
        int size = array.length;
        int parent = ((array.length - 2) >> 1);
        //对堆里的非叶子结点进行排序，使得交换时的堆除了堆顶元素，均为有序的堆
        for (int root = parent; root >= 0; root--) {
            //从第一个非叶子结点进行向下调整
            shiftDown(array,size,root);
        }

        int end = size - 1;
        while(end != 0){
            //交换第一个和最后一个元素
            int temp = array[0];
            array[0] = array[end];
            array[end] = temp;
            //从堆中删除一个元素后进行调整
            shiftDown(array,end,0);
            end--;
        }
    }

3.性能分析

（1）应用场景：

对于堆来说，只要让堆本身有序，是可以让效率更高的

（2）时间复杂度：

建堆的时间复杂度为O(n),调整堆的时间复杂度为O(n logn),总的时间复杂度为O(nlogn）

（3）空间复杂度：

堆也没有借助辅助空间，因此，堆排序的空间复杂度也为O(1)

（4）稳定性：

在进行堆排序时，没有挨个进行排序，只是进行了首尾元素的互换，因此也是不稳定的

（5）不适合使用的场景：

都适合，与数据是否趋近有序，影响不大

4.测试

public class Sort4 {
    //七种常见排序算法----->堆排序
    //堆排序的思想就是按照堆删除的思想来完成
    //向下调整
    public static void shiftDown(int[] array,int size,int parent){
        int child = parent * 2 + 1;
        while(child < size){
            if(child  + 1 < size && array[child] < array[child + 1]){
                child = child + 1;
            }

            if(array[parent] < array[child]){
                int temp = array[parent];
                array[parent] = array[child];
                array[child] = temp;

                parent = child;
                child = parent * 2 + 1;
            }else{
                return;
            }
        }
    }

    //实现堆排序的方法
    public static void heapSort(int[] array){
        int size = array.length;
        int parent = ((array.length - 2) >> 1);
        //对堆里的非叶子结点进行排序，使得交换时的堆除了堆顶元素，均为有序的堆
        for (int root = parent; root >= 0; root--) {
            //从第一个非叶子结点进行向下调整
            shiftDown(array,size,root);
        }

        int end = size - 1;
        while(end != 0){
            //交换第一个和最后一个元素
            int temp = array[0];
            array[0] = array[end];
            array[end] = temp;
            //从堆中删除一个元素后进行调整
            shiftDown(array,end,0);
            end--;
        }
    }

    //打印排序前后的变化
    public static void print(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
      int[] array = {9,8,7,6,5,4,3,2,1,0};
      print(array);
      heapSort(array);
      print(array);
    }
}

五，冒泡排序

1.基本思想

冒泡排序的基本思想很好理解，所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动

2.代码实现?

    //七种常用排序算法 ----> 冒泡排序
    //冒泡排序实际上就是挨个比较，将最大或最小的元素向后搬移
    public static void bubbleSort(int[] array){
        int size = array.length;
        //需要冒泡的趟数
        for (int i = 0; i < size - 1; i++) {
            //需要对数组进行比较
            for (int j = 0; j < size - 1; j++) {
                if(array[j] > array[j + 1]){
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

3.性能分析

（1）应用场景：

也没有很适合的场景，数据量小是可以考虑使用的，时间复杂度太高，但是很容易理解

（2）时间复杂度：

因为是要挨个比较，并且每层循环都需要走满，才能将序列变得有序，因此时间复杂度为O(N^2)

（3）空间复杂度：

只在原来的数组上进行交换，没有借助于辅助空间，冒泡排序的空间复杂度为O(1)

（4）稳定性：

因为需要挨个进行比较，且挨个进行交换，因此冒泡排序是稳定的

（5）不适合使用的场景：

数据量较大时，时间复杂度已经随之水涨船高了，不考虑使用

4.测试

public class Sort5 {
    //七种常用排序算法 ----> 冒泡排序
    //冒泡排序实际上就是挨个比较，将最大或最小的元素向后搬移
    public static void bubbleSort(int[] array){
        int size = array.length;
        //需要冒泡的趟数
        for (int i = 0; i < size - 1; i++) {
            //需要对数组进行比较
            for (int j = 0; j < size - 1; j++) {
                if(array[j] > array[j + 1]){
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }
    public static void print(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] array = {9,8,7,6,5,4,3,2,1,0};
        print(array);
        bubbleSort(array);
        print(array);
    }
}

六，快速排序

1.基本思想

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复过程，直到所有元素都排列在相应位置上为止

2.代码实现?

方法一：Hoare版本（提出快排思想的大佬）

    //方法一：Hoare法
    //基本思路：让begin在最左侧，让end在最右侧，当基准值选在最右侧时
    //begin先走，当遇到第一个比基准值大的元素，停下来
    //end再走，当遇到第一个比基准值小的停下来
    //两个元素进行交换，当这一趟循环走完时，begin和end在同一位置
    //只需用将此时的begin或end和数组最后的一个元素进行交换，就可以让基准值在中间位置
    public static int partition1(int[] array,int left,int right){
        int index = getMidIndex(array,left,right);
        if(index != right - 1){
            swap(array,index,right - 1);
        }
        int key = array[right - 1];
        int begin = left;
        int end = right - 1;

        while(begin < end){
            //基准值取在右侧，因此begin先走，找比基准值大的元素
            while(begin < end && array[begin] <= key){
                begin++;
            }
            //end再走，找比基准值小的，并停下来
            while(begin < end && array[end] >= key){
                end--;
            }
            //如果begin和end在同一个位置就不用交换了
            if(begin != end){
                swap(array,begin,end);
            }
        }
        //当begin和end走到同一个位置时，和此时数组的最后一个元素交换位置
        swap(array,begin,right - 1);
        return begin;
    }

方法二：挖坑法

    //方法二：挖坑法
    //基本思想：先将基准值处的值取出并标记，取名为“挖坑”
    //从begin开始，当遇到一个比基准值大的元素，就放到这个坑的位置
    //因此，begin此时也是一个坑，就让end从最后一个元素的进行查找
    // 如果遇到一个比基准值小的，就放到之前begin的位置以此类推
    // 直到begin和end相遇，就之前标记的基准值放到这个位置

    public static int partition2(int[] array,int left,int right){
        int index = getMidIndex(array,left,right);
        if(index != right - 1){
            swap(array,index,right - 1);
        }
        int key = array[right - 1];
        int begin = left;
        int end = right - 1;
        while(begin < end){
            //寻找比基准值大的元素，当遇到比基准值大的元素时，停下来
            while(begin < end && array[begin] <= key){
                begin++;
            }
            //判断是否begin和end相等，如果不相等，就交换
            if (begin < end){
                array[end] = array[begin];
            }
            //寻找比基准值小的元素，当遇到比基准值小的元素时，停下来
            while(begin < end && array[end] >= key){
                end--;
            }

            if(begin < end){
                array[begin] = array[end];
            }
        }
        //此时已经找完了，就让begin处放上标记值
        array[begin] = key;
        return begin;
    }

?方法三：快慢引用

    //方法三：前后指针法（在Java中并没有指针这一说，就是引用）
    public static int partition(int[] array,int left,int right){
        int index = getMidIndex(array,left,right);
        if(index != right - 1){
            swap(array,index,right - 1);
        }
        int key = array[right - 1];
        int cur = left;
        int prev = cur - 1;

        while(cur < right){
            if(array[cur] < key && ++prev != cur){
                swap(array,cur,prev);
            }
            cur++;
        }

        if(++prev != right - 1){
            swap(array,prev,right - 1);
        }
        return prev;
    }

方法四：非递归的思想解决

    //方法四：非递归算法
    //非递归算法的本质就是省去了要递归的过程，转而将要递归所要的东西
    //保存在了栈当中，即就是左右边界的条件
    public static void quickSortNonr(int[] array,int left,int right){
        Stack<Integer> s = new Stack<>();
        s.push(left);
        s.push(right);

        while(!s.empty()){
            right = s.pop();
            left = s.pop();
            if(right - left > 1){
                int div = partition1(array, left, right);
                //将区间分为了[left,div)和[div + 1,right)
                s.push(div + 1);
                s.push(right);
                s.push(left);
                s.push(div);
            }

        }
    }

3.性能分析

（1）应用场景：

和上面的排序算法最大的不同是，数据越无序越好，快速排序的时间复杂度就会降低，效率越高

（2）时间复杂度：

快速排序的时间复杂度是O(NlogN)
但是这是最好情况下，如果是最坏情况下，它的时间复杂度是O(N ^ 2)?

什么情况下是快排是最差情况：

快排的应用场景最好是无序的，也就是说越混乱越好，为什么别的排序算法基本都是越有序越好呢（也不一定，但肯定不是越无序越好）；从快速排序的算法思想上分析，快排时间复杂度的根本在于我们选择的基准值，基准值越趋向于这一组数据的中间数值，那么它的排序效率就越高

我们可以假设，此时我们取到了一组数据，它接近有序，并且我们运气不好取到了最大或者最小的元素，每次在进行分割时，左侧或者右侧永远只有一个元素，那么，它的分割场景就类似于一棵递增顺序（或者递减）查找树，它要么只有左子树，要么只有右子树（见下图）
那假如，这一组数据是无序的并且我们的运气好，每次取到的基准值都比较靠近相应的中间数值，那么它的递归图像，就像是一棵二叉平衡树，那么这就是两种时间复杂度了，（见下图1）
我们能做的就是，尽可能的取到靠近的中间数值的那个元素当做基准值，那么它的时间复杂度就会稳定在最最优情况下

解决办法：

三数取中法:(这个方法的目的就是为了避免取到最大或者最小的数据，让时间复杂度变高）

    //三数取中法(找中间数值的下标）
    public static int getMidIndex(int[] array,int left,int right){
        int mid = left + ((right - left) >> 1);

        //判断三个数当中最大的一个数
        if(array[left] < array[right - 1]){
            //比最小的小，返回left
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right - 1]){
                //比最大的大，返回right - 1；
                return right - 1;
            }else{
                return mid;
            }
        }else{
            if(array[mid] < array[right - 1]){
                return right - 1;
            }else if(array[mid] > array[left]){
                return left;
            }else{
                return mid;
            }
        }
    }

?图1：

图2：

（3）空间复杂度：

快速排序的空间复杂度为O(logN）

如果数据量太大，造成栈溢出时的解决办法：

当递归到一定程度时，就不让他进行递归了，让它进行直接插入排序

从标准库中可以看出来时怎么处理的

?这段话的意思是：如果要排序的数组长度小于此常量，则插入排序优先于快速排序

（4）稳定性：

因为是交换排序，并且有间隔交换，因此是不稳定的

（5）不适合使用的场景：

快排的不适合场景就是这组数据接近有序或者有序

4.测试

（测试均已通过，只放一次运行结果）

package day20211112;

import java.util.Stack;

public class Sort6 {
    //七种常见排序算法 ----> 快速排序（快排）


    //方法四：非递归算法
    //非递归算法的本质就是省去了要递归的过程，转而将要递归所要的东西
    //保存在了栈当中，即就是左右边界的条件
    public static void quickSortNonr(int[] array,int left,int right){
        Stack<Integer> s = new Stack<>();
        s.push(left);
        s.push(right);

        while(!s.empty()){
            right = s.pop();
            left = s.pop();
            if(right - left > 1){
                int div = partition1(array, left, right);
                //将区间分为了[left,div)和[div + 1,right)
                s.push(div + 1);
                s.push(right);
                s.push(left);
                s.push(div);
            }

        }
    }
    //方法三：前后指针法（在Java中并没有指针这一说，就是引用）
    public static int partition(int[] array,int left,int right){
        int index = getMidIndex(array,left,right);
        if(index != right - 1){
            swap(array,index,right - 1);
        }
        int key = array[right - 1];
        int cur = left;
        int prev = cur - 1;

        while(cur < right){
            if(array[cur] < key && ++prev != cur){
                swap(array,cur,prev);
            }
            cur++;
        }

        if(++prev != right - 1){
            swap(array,prev,right - 1);
        }
        return prev;
    }
    //方法二：挖坑法
    //基本思想：先将基准值处的值取出并标记，取名为“挖坑”
    //从begin开始，当遇到一个比基准值大的元素，就放到这个坑的位置
    //因此，begin此时也是一个坑，就让end从最后一个元素的进行查找
    // 如果遇到一个比基准值小的，就放到之前begin的位置以此类推
    // 直到begin和end相遇，就之前标记的基准值放到这个位置

    public static int partition2(int[] array,int left,int right){
        int index = getMidIndex(array,left,right);
        if(index != right - 1){
            swap(array,index,right - 1);
        }
        int key = array[right - 1];
        int begin = left;
        int end = right - 1;
        while(begin < end){
            //寻找比基准值大的元素，当遇到比基准值大的元素时，停下来
            while(begin < end && array[begin] <= key){
                begin++;
            }
            //判断是否begin和end相等，如果不相等，就交换
            if (begin < end){
                array[end] = array[begin];
            }
            //寻找比基准值小的元素，当遇到比基准值小的元素时，停下来
            while(begin < end && array[end] >= key){
                end--;
            }

            if(begin < end){
                array[begin] = array[end];
            }
        }
        //此时已经找完了，就让begin处放上标记值
        array[begin] = key;
        return begin;
    }

    //方法一：Hoare法
    //基本思路：让begin在最左侧，让end在最右侧，当基准值选在最右侧时
    //begin先走，当遇到第一个比基准值大的元素，停下来
    //end再走，当遇到第一个比基准值小的停下来
    //两个元素进行交换，当这一趟循环走完时，begin和end在同一位置
    //只需用将此时的begin或end和数组最后的一个元素进行交换，就可以让基准值在中间位置
    public static int partition1(int[] array,int left,int right){
        int index = getMidIndex(array,left,right);
        if(index != right - 1){
            swap(array,index,right - 1);
        }
        int key = array[right - 1];
        int begin = left;
        int end = right - 1;

        while(begin < end){
            //基准值取在右侧，因此begin先走，找比基准值大的元素
            while(begin < end && array[begin] <= key){
                begin++;
            }
            //end再走，找比基准值小的，并停下来
            while(begin < end && array[end] >= key){
                end--;
            }
            //如果begin和end在同一个位置就不用交换了
            if(begin != end){
                swap(array,begin,end);
            }
        }
        //当begin和end走到同一个位置时，和此时数组的最后一个元素交换位置
        swap(array,begin,right - 1);
        return begin;
    }
    //快速排序的方法主体
    public static void quickSort(int[] array,int left,int right){
        if(right - left > 1){
            //对元素进行分割
            int div = partition(array,left,right);
            //左侧[left,div)
            quickSort(array,left,div);
            //右侧[div + 1,right)
            quickSort(array,div + 1,right);
        }
    }

    //三数取中法(找中间数值的下标）
    public static int getMidIndex(int[] array,int left,int right){
        int mid = left + ((right - left) >> 1);

        //判断三个数当中最大的一个数
        if(array[left] < array[right - 1]){
            //比最小的小，返回left
            if(array[mid] < array[left]){
                return left;
            }else if(array[mid] > array[right - 1]){
                //比最大的大，返回right - 1；
                return right - 1;
            }else{
                return mid;
            }
        }else{
            if(array[mid] < array[right - 1]){
                return right - 1;
            }else if(array[mid] > array[left]){
                return left;
            }else{
                return mid;
            }
        }
    }
    //交换方法
    public static void swap(int[] array,int left,int right){
        int temp = array[left];
        array[left] = array[right];
        array[right] = temp;
    }

    //打印数组元素，排序前后的是否有序
    public static void print(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] array = {9,8,7,6,5,4,3,2,1,0};
        print(array);
        //quickSort(array,0,array.length);
        quickSortNonr(array,0,array.length);
        print(array);
    }
}

七，归并排序

1.基本思想

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

2.代码实现?

方法一：递归的思想

    //方法一：递归的思想
    //基本思想：就是利用不断递归，借用辅助空间让原数组一部分先有序，在复制到原数组当中去
    public static void mergeDate(int[] array,int left,int mid,int right,int[] temp){
        //这可以看做是两个数组
        //这是第一个数组的边界 begin1 end1
        int begin1 = left;
        int end1 = mid;

        //这是第二个数组的边界 begin2 end2
        int begin2 = mid;
        int end2 = right;

        //这是临时数组的且我们需要的边界的起始下标
        int index = left;

        //对两个数组进行的元素进行合并
        while(begin1 < end1 && begin2 < end2){
            if(array[begin1] <= array[begin2]){
                temp[index] = array[begin1];
                index++;
                begin1++;
            }else{
                temp[index] = array[begin2];
                index++;
                begin2++;
            }
        }

        //判断是哪个数组先排完（上面的合并过程并不能保证每一个数组都是均等的）
        while(begin1 < end1){
            temp[index] = array[begin1];
            index++;
            begin1++;
        }
        while(begin2 < end2){
            temp[index] = array[begin2];
            index++;
            begin2++;
        }
    }
    
    //递归实现归并排序的方法体
    private static void mergeSort(int[] array,int left,int right,int[] temp){
        //判断是否满足条件（只有一个元素时，默认时有序的）
        if(right - left > 1){
            //找中间元素的下标
            int mid = left + ((right - left) >> 1);
            //将原数组分为了两部分[left,mid) 和 [mid,right)

            //进行左半部分的递归
            mergeSort(array,left,mid,temp);

            //进行右半部分的递归
            mergeSort(array,mid,right,temp);

            //开始进行归并
            mergeDate(array,left,mid,right,temp);
            //将临时数组当中的元素往原数组当中拷贝
            System.arraycopy(temp,left,array,left,right - left);
        }
    }

    //对归并排序方法体进行包装一下
    public static void mergeSort(int[] array){
        int[] temp = new int[array.length];
        mergeSort(array,0,array.length,temp);
    }

方法二：利用循环解决

    //方法二：非递归形式
    //循环的思想就是利用一个gap，充当递归分割的过程，从单个元素开始，一直到最后一个结束
    //以此类推，直到将数组只能分为两个之后结束
    public static void mergeSortNonr(int[] array){
        int size = array.length;
        //创建一个临时数组
        int[] temp = new int[size];

        int gap = 1;
        while (gap < size){
            for(int i = 0;i < size;i += 2 * gap){
                int left = i;
                int mid = left + gap;
                int right = mid + gap;

                //如果mid大于size，说明已经到数组最后一个元素之外了
                if(mid >= size){
                    mid = size;
                }
                //如果right大于size，说明已经到数组最后一个元素之外了
                if(right >= size){
                    right = size;
                }

                //进行合并
                mergeDate(array,left,mid,right,temp);
            }

            //将临时数组中的元素拷贝到原数组当中
            System.arraycopy(temp,0,array,0,size);

            gap *= 2;
        }
    }

3.性能分析

（1）应用场景：

归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题

（2）时间复杂度：

归并排序的空间复杂度和快速排序的最优情况类似，只是减少基准值的那一部分，因此它的时间复杂度也为O(N * logN)

（3）空间复杂度：

因为借用了一段和原数组大小相等的空间，因此空间复杂度也为O(N)

（4）稳定性：

?在这个地方，我们添加了等于号，意思就是，当两个值相等时，那么，我们先取第一个数组当中的值，因此并未改变原有的顺序，所以是稳定的

4.测试

public class Sort7 {
    //七种常见排序算法 ----> 归并排序

    //方法二：非递归形式
    //循环的思想就是利用一个gap，充当递归分割的过程，从单个元素开始，一直到最后一个结束
    //以此类推，直到将数组只能分为两个之后结束
    public static void mergeSortNonr(int[] array){
        int size = array.length;
        //创建一个临时数组
        int[] temp = new int[size];

        int gap = 1;
        while (gap < size){
            for(int i = 0;i < size;i += 2 * gap){
                int left = i;
                int mid = left + gap;
                int right = mid + gap;

                //如果mid大于size，说明已经到数组最后一个元素之外了
                if(mid >= size){
                    mid = size;
                }
                //如果right大于size，说明已经到数组最后一个元素之外了
                if(right >= size){
                    right = size;
                }

                //进行合并
                mergeDate(array,left,mid,right,temp);
            }

            //将临时数组中的元素拷贝到原数组当中
            System.arraycopy(temp,0,array,0,size);

            gap *= 2;
        }
    }

    //方法一：递归的思想
    //基本思想：就是利用不断递归，借用辅助空间让原数组一部分先有序，在复制到原数组当中去
    public static void mergeDate(int[] array,int left,int mid,int right,int[] temp){
        //这可以看做是两个数组
        //这是第一个数组的边界 begin1 end1
        int begin1 = left;
        int end1 = mid;

        //这是第二个数组的边界 begin2 end2
        int begin2 = mid;
        int end2 = right;

        //这是临时数组的且我们需要的边界的起始下标
        int index = left;

        //对两个数组进行的元素进行合并
        while(begin1 < end1 && begin2 < end2){
            if(array[begin1] <= array[begin2]){
                temp[index] = array[begin1];
                index++;
                begin1++;
            }else{
                temp[index] = array[begin2];
                index++;
                begin2++;
            }
        }

        //判断是哪个数组先排完（上面的合并过程并不能保证每一个数组都是均等的）
        while(begin1 < end1){
            temp[index] = array[begin1];
            index++;
            begin1++;
        }
        while(begin2 < end2){
            temp[index] = array[begin2];
            index++;
            begin2++;
        }
    }

    //递归实现归并排序的方法体
    private static void mergeSort(int[] array,int left,int right,int[] temp){
        //判断是否满足条件（只有一个元素时，默认时有序的）
        if(right - left > 1){
            //找中间元素的下标
            int mid = left + ((right - left) >> 1);
            //将原数组分为了两部分[left,mid) 和 [mid,right)

            //进行左半部分的递归
            mergeSort(array,left,mid,temp);

            //进行右半部分的递归
            mergeSort(array,mid,right,temp);

            //开始进行归并
            mergeDate(array,left,mid,right,temp);
            //将临时数组当中的元素往原数组当中拷贝
            System.arraycopy(temp,left,array,left,right - left);
        }
    }

    //对归并排序方法体进行包装一下
    public static void mergeSort(int[] array){
        int[] temp = new int[array.length];
        mergeSort(array,0,array.length,temp);
    }

    //打印数组元素，排序前后的是否有序
    public static void print(int[] array){
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
    public static void main(String[] args) {
        int[] array = {9,8,7,6,5,4,3,2,1,0};
        print(array);
        //mergeSort(array);
        mergeSortNonr(array);
        print(array);
    }
}