排序的简单理解（下）

4.交换排序

基本思想：所谓交换，就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置

交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

4.1 冒泡排序

冒泡排序（Bubble Sorting）即：通过对待排序的序列从前往后，依次比较相邻元素的值，若发现逆序则交换位置，使较大的元素逐渐移动到后部

4.1.1 算法分析

下面的分析以将序列{2, 9, 7, 10, 30}从小到大排序为例！

其基本思想就是，在每一趟排序最终实现将该趟得到的最大的数移到序列的最后端，

核心操作就是通过比较相邻两个元素实现，当相邻的两个元素逆序的时候，我们就交换它们。

第1趟排序：
第1趟排序共比较了4次，将最大的数30冒泡到了序列的尾部。

第2趟排序：
        由于第一趟排序已经将最大是数30给冒泡到了最末端，因此在本次排序中，不需要再比较最后一个元素，故此本趟共比较了3次，将子序列（前四个元素）中最大的数10（整个序列中倒数第二大的数）冒泡到了子序列的尾端（原序列的倒数第二个位置）。

第3趟排序：
        在第三趟排序时，同理，倒数两个元素位置已经确定，即第一、第二大的数已经排好位置，只需要再将倒数第三大的数确认即可。故比较2次，实现倒数第三大的数9的位置确定。

第4趟排序：
        在第四趟排序时，只有第一、第二个元素的位置还不确定，只需要比较一次，若逆序，则交换即可。到此，排序算法完成，原序列已经排序成为一个递增的序列！

小结

一共进行了数组大小-1次趟排序，即外层循环arr.length-1次；
每趟排序进行了逐趟减小次数的比较，即内层循环arr.length-i-1次，i从0依次增加。

4.1.2 代码实现

详细代码如下：

/**
     * @version 1.0
     * 冒泡排序
     */
        public static void main(String[] args) {
            int[] array = {2,9,7, 10, 30};
            //排序前
            System.out.println("排序前:" + Arrays.toString(array));
            //冒泡排序
            for (int i = 0; i < array.length - 1; i++) {
                System.out.println("第" + (i+1) + "趟排序开始!");
                for (int j = 0; j < array.length - i - 1; j++) {
                    //如果前面的数比后面的数大，则交换
                    if(array[j] > array[j+1]){
                        //交换
                        int temp = array[j];
                        array[j] = array[j+1];
                        array[j+1] = temp;
                    }
                    System.out.println("------第" + (j+1) + "趟排序: " + Arrays.toString(array));
                }
                System.out.println("第" + (i+1) + "趟排序完成: " + Arrays.toString(array));
                System.out.println("================================================");
            }

            //输出排序后的结果
            System.out.println("排序后:" + Arrays.toString(array));
        }

结果展示：

排序前:[2, 9, 7, 10, 30]
第1趟排序开始!
------第1趟排序: [2, 9, 7, 10, 30]
------第2趟排序: [2, 7, 9, 10, 30]
------第3趟排序: [2, 7, 9, 10, 30]
------第4趟排序: [2, 7, 9, 10, 30]
第1趟排序完成: [2, 7, 9, 10, 30]
================================================
第2趟排序开始!
------第1趟排序: [2, 7, 9, 10, 30]
------第2趟排序: [2, 7, 9, 10, 30]
------第3趟排序: [2, 7, 9, 10, 30]
第2趟排序完成: [2, 7, 9, 10, 30]
================================================
第3趟排序开始!
------第1趟排序: [2, 7, 9, 10, 30]
------第2趟排序: [2, 7, 9, 10, 30]
第3趟排序完成: [2, 7, 9, 10, 30]
================================================
第4趟排序开始!
------第1趟排序: [2, 7, 9, 10, 30]
第4趟排序完成: [2, 7, 9, 10, 30]
================================================
排序后:[2, 7, 9, 10, 30]

进程已结束,退出代码0

4.1.3 算法的不足及优化

我们仔细观察一下我们上述数组在进行冒泡法时每一个外循环后的结果：

我们发现其实在第一次外循环结束之后，我们的当前数组已经完成了冒泡法整个算法的最终结果，但是由于我们的算法规定，它依旧要跑array.length-1次外循环，故此我们需要完成代码的优化，当我们的数组提前完成排序后，就要提前结束外循环，终止我们的冒泡排序；

我们可以发现一个无序的数组在经过冒泡算法的排序之后，这些元素的位置在最后都是固定的，每一次的内循环，相应的元素可以理解为都是往那个自己最终的位置上跑，但是当一次内循环之后，发现我们当前的元素位置和该次内循环开始之前的元素位置一样，没有发生变化，这时候我们可以确认我们的元素都已经到达了自己的最终位置，可以提前终止冒泡算法，不在进行其他的外循环；

所以最终的解决方案就是我们设置一个flag标志位，来判断当前内循环前后数组的元素有没有发生顺序的变化，优化代码如下图所示；

 public static void main(String[] args) {
        int[] array = {5, 1, 2, 3, 4};
        //排序前
        System.out.println("排序前:" + Arrays.toString(array));

        boolean flag = false; //用于标记是否进行了交换，true则说明进行了交换，false表示无

        //冒泡排序
        for (int i = 0; i < array.length - 1; i++) {
            System.out.println("第" + (i+1) + "趟排序开始!");
            for (int j = 0; j < array.length - i - 1; j++) {
                //如果前面的数比后面的数大，则交换
                if(array[j] > array[j+1]){
                    //交换
                    flag = true; //标记进行了交换
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
                System.out.println("------第" + (j+1) + "趟排序: " + Arrays.toString(array));
            }
            System.out.println("第" + (i+1) + "趟排序完成: " + Arrays.toString(array));
            System.out.println("================================================");
            if (!flag){
                //如果没有进行交换则直接退出，说明排序已经完成
                break;
            }else {
                //回退
                flag = false;
            }
        }
        //输出排序后的结果
        System.out.println("排序后:" + Arrays.toString(array));
    }

测试结果：

如图所示，经过优化后，我们相比于之前的代码，减少了两次内循环，提前结束了冒泡算法，大大的节省了时间资源；

4.1.4 冒泡排序的特性总结

1、冒泡排序是一种非常容易理解的排序

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

        空间复杂度：O(1)

        稳定性：稳定

2、什么时候最快？
        当输入的数据已经是正序时，我们的内循环和外循环的执行次数比较少；

4.2 快速排序

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

4.2.1 算法分析（递归）

        快速排序算法通过多次比较和交换来实现排序，其排序流程如下：
        (1)首先设定一个分界值，通过该分界值将数组分成左右两部分。
        (2)将大于或等于分界值的数据集中到数组右边，小于分界值的数据集中到数组的左边。此时，左边部分中各元素都小于分界值，而右边部分中各元素都大于或等于分界值。
        (3)然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
        (4)重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。

        下面来举例来详细的分析：

首先，我们会把数组中的一个数当作基准数，然后从两边进行检索。

其次，按照如下步骤进行：

1、先从右边检索比基准数小的
2、再从左边检索比基准数大的
3、一旦检索到，就停下，并将检索到的两个元素进行交换
4、重复上述步骤，直到检索相遇，则替换基准数，并更新区间，递归进行，最终序列会变得有序

接下来就以{6，1，8，0，2，9，5，3，7}为例详细来分析一下步骤，具体分析一下第一趟排序：以6为基准数的步骤：

1、红色块标识基准数，left、right初始位置如图所示

2、right不断向左移动，寻找比基准数6小的数，如图所示，找到了3

3、此时left开始移动，不断向右移动，寻找比基准数大的数，找到了8，这时，left、right都找到了对应的数，进行交换：

4、right继续向左寻找比基准数6小的数，找到后停止移动，此时left继续向右寻找比基准数大的数，当left与right都找到对应的数后，再次将二者的数值进行交换。

5、重复上述步骤，一直到left与right相遇，二者共同指向了5的位置，则将基准数与该位置的数进行交换，这样就可以观察到，6的左边都是比6小的，右边都是比6大的。

6、该过程需要递归进行，直到序列有序。即以5为基准数，递归6左边的区间，再以9为基数递归6右边的区间，反复进行，直到left >right退出。

4.2.2 代码实现

冒泡法代码如下：

public static void quickSort(int[] arr, int left, int right) {
            //边界条件
            if (left > right){
                return;
            }

            //定义基准数和左右指针
            int l = left;
            int r = right;
            int base = arr[left];

            //循环，将比基准数小的放在左边，比基准数大的放在右边
            while (l != r){
                //先从右边找比基准数小的，停下
                while (arr[r] >= base && l < r){
                    r--;
                }
                //从左边找比基准数大的，停下
                while (arr[l] <= base && l < r){
                    l++;
                }
                //此时已经找到对应的l 和 r，进行交换
                int temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
            }
            //至此，基准数两边都按照需要排好了，只需要将基准数与lr相遇的位置进行交换
            arr[left] = arr[l];
            arr[l] = base;
            //打印中间结果
            System.out.println(Arrays.toString(arr));
            //先向左找
            quickSort(arr, left, r-1);
            //向右递归
            quickSort(arr, l+1, right);
        }

测试代码：

public static void main(String[] args) {
     int[] arr = {6,1,8,0,2,9,5,3,7};
     quickSort(arr, 0, arr.length-1);
     System.out.println("排序后: " + Arrays.toString(arr));
}

测试结果：

4.2.3 快速排序非递归实现

思路：

建立一个栈

先让一组数据的起点入栈

再让一组数据的终点出栈

然后两次出栈，分别作为该数据的起点与终点

然后经过我们上面所写的方法进行排序后

再将两组数据进行入栈

以此循环直到栈为空

代码实现：

    //快速排序递归实现
    public int[] quickSortPlus(int[] array) {
        int[] arr = Arrays.copyOf(array,array.length);
        Deque<Integer> stack = new LinkedList<>();
        int left = 0;
        int right = array.length-1;
        int pivot = 0;
        stack.push(left);
        stack.push(right);
        while (!stack.isEmpty()) {
            right= stack.pop();
            left = stack.pop();
            pivot = partition(arr,left,right);
            if(pivot > left+1) {
                stack.push(left);
                stack.push(pivot-1);
            }
            if(pivot < right-1) {
                stack.push(pivot+1);
                stack.push(right);
            }
        }
        return arr;
    }
    private  int partition(int[] array,int left,int right) {
        int tmp = array[left];
        while (left < right) {
            while (left< right && array[right] >= tmp) {
                right--;
            }
            array[left] = array[right];
            while (left< right && array[left] <= tmp) {
                left++;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
    }

4.2.4 特性总结

1. 快速排序整体的综合性能和使用场景都是比较好的，所以才敢叫快速排序

2. 时间复杂度： O(N*logN)

3. 空间复杂度：O(logN)

4. 稳定性：不稳定

5. 归并排序

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

5.1算法分析

合并相邻有序子序列

...以此类推

...

...

如果当其中的一个子序列全部转移到temp数组中时，另外未空的子序列的元素直接全部按当前顺序移入到temp中即可。

5.2 代码实现

代码部分：

static int count = 0;
        public static void main(String[] args) {
            int[] arr = {10, 6, 7, 1, 3, 4, 2,9};
            int[] temp = new int[arr.length];
            mergeSort(arr, 0, arr.length - 1, temp);
            System.out.println("归并排序后: arr[] = " + Arrays.toString(arr));
        }

        //归并排序
        public static void mergeSort(int[] arr, int left, int right, int[] temp){
            if (left < right){
                int mid = left - (left - right) / 2;
                //向左递归分解
                mergeSort(arr, left, mid, temp);
                //向右递归分解
                mergeSort(arr, mid + 1, right, temp);
                //排序 合并
                merge(arr, left, mid, right, temp);
            }
        }
        /**
         * 合并的方法
         * @param arr  排序的原始数组
         * @param left  左边有序序列的初始索引
         * @param mid  中间索引
         * @param right  右边索引
         * @param temp  中转数组
         */
        public static void merge(int[] arr, int left, int mid, int right, int[] temp){
            int i = left; //初始化i，左边有序序列的初始索引
            int j = mid + 1; //初始化j，右边有序序列的初始索引
            int t = 0; //指向temp数组的当前索引
            //先把左右两边有序数据按照规则填充到temp数组，直到左右两边有一边处理完毕
            while (i <= mid && j <= right){
                if (arr[i] <= arr[j]){
                    temp[t] = arr[i];
                    t++;
                    i++;
                }else {
                    temp[t] = arr[j];
                    t++;
                    j++;
                }
            }
            //把剩余的一方依次填充到temp数组
            while (i <= mid){ //左边序列还有剩余的元素
                temp[t++] = arr[i++];
            }
            while (j <= right){ //右边序列还有剩余的元素
                temp[t++] = arr[j++];
            }
            //将temp数组的元素拷贝到arr
            //拷贝每次小序列
            t = 0;
            int tempLeft = left;
            while (tempLeft <= right){
                arr[tempLeft++] = temp[t++];
            }
            count++;
            System.out.println("第" + count + "次合并: arr[] = " + Arrays.toString(arr));
        }

测试结果展示：

分析：

{10, 6, 7, 1, 3, 4, 2,9}被拆分成了{10, 6}{7, 1}{3, 4}{2, 9}：

第一次合并：{6, 10}有序
第二次合并：{1, 7}有序
第三次合并: {1， 6， 7， 10}有序
第四次合并：{3, 4}有序
第五次合并：{2, 9}有序
第六次合并: { 2，3，4，9}有序
第七次合并：{1，2，3，4，6，7，9,10}有序