【数据结构-之八大排序(下)，冒泡排序，快速排序，挖坑法，归并排序】

🌈个人主页：努力学编程’
⛅个人推荐：基于java提供的ArrayList实现的扑克牌游戏 |C贪吃蛇详解
⚡学好数据结构，刷题刻不容缓：点击一起刷题
🌙心灵鸡汤：总有人要赢，为什么不能是我呢

hello,这里提前祝大家五一快乐，每天都能快快乐乐，并且每天都能学到东西。

我们今天继续顺着上次没有说完的排序算法，这里简单复习一下，我们根据每种排序的方式不同，大致上将常见的排序算法分为选择排序，插入排序，交换排序，归并排序。今天就大家学习我们剩下的两个大类，交换排序和归并排序。

🌈交换排序

⚡冒泡排序

冒泡排序算法的原理如下：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

这里也给大家一个动图，帮助大家理解：

public static void bubbleSort(int[] array) {
        for (int i = 0; i < array.length-1; i++) {
            boolean flg = false;
            for (int j = 0; j < array.length-1-i; j++) {
                if(array[j] > array[j+1]) {
                    swap(array,j,j+1);
                    flg = true;
                }
            }
            
            //时间复杂度为：O(N)
            if(!flg) {
                break;
            }
        }
    }

总体来说呢，冒泡排序是这几种排序中最简单的一种排序，容易理解，代码的逻辑也没有那么复杂，唯一需要提醒大家的，就是两个for循环里面的循环结束条件的判断，这里需要着重强调！！！

1. 冒泡排序是一种非常容易理解的排序
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：稳定

⚡快速排序

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

// 假设按照升序对array数组中[left, right)区间中的元素进行排序
void QuickSort(int[] array, int left, int right)
{
if(right - left <= 1)
return;
// 按照基准值对array数组的 [left, right)区间中的元素进行划分
int div = partion(array, left, right);
// 划分成功后以div为边界形成了左右两部分 [left, div) 和 [div+1, right)
// 递归排[left, div)
QuickSort(array, left, div);
// 递归排[div+1, right)
QuickSort(array, div+1, right);
}

这里我们可以根据不的基准值，将快速排序划分为两个版本Hoare版本，和挖坑法。

⛅Hoare法
Hoare法是指在对数组进行排序时，定义两个变量，与一个在单子循环中不变的key值，右值先动找比key小的数字，找到后左值动，找比key大的数字，后进行交换以完成对数组的排序。

 private static int partitionHoare(int[] array,int left,int right) {
        int i = left;
        int tmp = array[left];
        while (left < right) {
            //array[right] >= tmp  这里能不能 不取等于号
            //不能，自己排序会发现这里取等号排序会混乱
            // right--; 为什么先走右边
            //先走左边会把数值大的元素换到数组的右边
            while (left < right && array[right] >= tmp) {
                right--;
            }
            while (left < right &&  array[left] <= tmp) {
                left++;
            }
            swap(array,left,right);
        }
        //left 和 right 相遇了
        swap(array,left,i);
        return left;
    }

⚡挖坑法

我们上面讲过了Hoare法，其实在一般的快速排序的构成中，我们默认它底层的其实逻辑使用的挖坑法。所以我们这里着重给大家介绍一下挖坑法。

• 定义两个指针，一个在左，一个在右，
• 每次遍历的时候我们都以左边的值为基准值
• 分别利用for循环找到左边和右边需要调整的位置
• 然后交换左右两边需要调整的值
• 交换到最后，我们需要把left和right相遇的位置的值设置为基准值
• 最后返回这个基准值

 private static 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;
    }

好了，我们这里对实现的挖坑法做一点测试。

⚡归并排序

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

这里我们使用的分而治之的方法，去求解的时候，分相对来说是比较简单的，我们使用递归的方法可以很快的对数组进行分组，然后，我们在合并数组的时候，整个过程邢队来说是比较麻烦的，我们需要先对元素进行排序，然后，申请一块新的数组将已经排好序的元素放到申请的数组当中，然后递归整个过程。

这里也罢代码给大家，仔细看一下注释标注的地方，会有很大收获。

public static void mergeSort(int[] array) {
        mergeSortFun(array,0,array.length-1);
    }

    public static void mergeSortFun(int[] array,int left,int right) {
        if(left >= right) {// >
            return;
        }
        int mid = (right+left) / 2;
        mergeSortFun(array,left,mid);
        mergeSortFun(array,mid+1,right);
        //合并
        merge(array,left,mid,right);
    }
    private static void merge(int[] array,int left,
                              int mid,int right) {
        //这里申请一块新的数组 存放排好序元素
        int[] tmp = new int[right-left+1];
        int k = 0;
        int s1 = left;
        int e1 = mid;
        int s2 = mid+1;
        int e2 = right;
        //定义整个存放元素过程的限制条件
        while (s1 <= e1 && s2 <= e2) {
            if(array[s1] <= array[s2]) {
                tmp[k++] = array[s1++];
            }else {
                tmp[k++] = array[s2++];
            }
        }
        //走到这里，可能是左边的数组已经排完了  
        //我们就把右边所有的元素是直接放到数组当中
        //当右边已经拍完之后，
        //我们需要将左边还剩的元素直接放到数组当中。
        while (s1 <= e1) {
            tmp[k++] = array[s1++];
        }
        while (s2 <= e2) {
            tmp[k++] = array[s2++];
        }
        //走到这里 相当于tmp数组 当中 所有的元素 都有序了
        //接下来把tmp数组的内容 拷贝到array数组当中
        for (int i = 0; i < k; i++) {
        //这里的array()里面的元素索引要加上left,拷贝到原数组
        //
            array[i+left] = tmp[i];
        }
    }

归并排序总结
1.归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
2. 时间复杂度：O(N*logN)
3. 空间复杂度：O(N)
4. 稳定性：稳定

🌕海量数据的排序问题

外部排序：排序过程需要在磁盘等外部存储进行的排序
前提：内存只有 1G，需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下，所以需要外部排序，而归并排序是最常用的外部排序

• 先把文件切分成 200 份，每个 512 M
• 分别对 512 M 排序，因为内存已经可以放的下，所以任意排序方式都可以
• 进行 2路归并，同时对 200 份有序文件做归并过程，最终结果就有序了

归并排序多用于海量输数据的使用，在整个过程中，我们将海量数据，分成很多一份份的，将每一小份数据单独处理，最后将所有的小数据块进行合并，完成海量数据的处理！！！

🌕一图带你了解所有排序算法的时间复杂度，和使用场景

好了，今天就分享到这里，感谢你的阅读！！！