Java常见排序基础 - 中

在 Java常见排序基础 - 上 中主要介绍了冒泡排序、选择排序、插入排序三种基础排序，本篇文章主要介绍的是 快速排序、归并排序。

快速排序：

首先看下什么是快速排序，快速排序（Quicksort）是对冒泡排序的一种改进。快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以 递归 进行，以此达到整个数据变成有序序列。以上概念来自百度百科。

对于 “通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小”，简单的理解可以这样的：在数组中找一个支点 ( 支点可以是数组中的任意位置，但是这个支点一般是数组的中心位置 )，经过一趟排序后，支点左边的数都要比支点小，支点右边的数都要比支点大。

假设现在有这样一个数组：int arr[ ] = { 1,4,5,62,2,7,8,6,9,14 };

经过一趟排序之后，如果我选择数组中间的数作为支点：7(任意的)，那么第一趟排序后的结果是这样的：{1,4,5,6,2,7,8,62,9,14}，那么，1,4,5,6,2,7 则是第一趟排序的左边，7,8,62,9,14则是第一趟排序的右边。既然现在确定好了第一趟排序的结果，那么现在只需要对第一趟排序的左边在寻找一个支点，继续对这里进行逻辑判断排序、以此类推，这样就最终实现了支点左边的数比支点小，支点右边的数比支点大

前面说到，快速排序整个排序过程都可以 递归 进行，但是构成递归需必须具备两个条件：首先，子问题须与原始问题为同样的事，且更为简单（这里的意思就是找支点 、对支点左右侧进行逻辑判断）；其次不能无限制地调用本身，须有个出口，化简为非递归状况处理。

那么下面我们就一步步的完成快速排序：

首先，我们定义一个数组，假设它的支点是数组的中间，那么计算数组的中间值只需要知道数组最后一个索引即可（因为第一个索引是0），于是，我们就有了以下代码：

快速排序 - 1

既然我们知道了数组的支点，就可以对其进行判断了，判断的步骤简单点理解 就是 arr[支点]与arr[索引]的具体大小判断，由于这里局部变量定义的left与right，分别是数组的最小索引以及数组的最大索引，也就是arr[0]和arr[ arrLength - 1]。因此，为了让快速排序进行判断的话 只需要数组最小索引不断累加、最大索引不断累减、依次判断。只要 累加之后的最小索引和累减之后的最大索引 次数不一致即可一直让其在内部判断。那么什么时候让最小索引不断累加，什么时候让最大索引不断累减？理论上来说就是支点左边的数值比支点小，即可让其自增；支点右侧的数值比支点大，则让其自减。所以，最后可以这样写：

快速排序

值得注意的是，快速排序是一种不稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。关于快速排序的内容就介绍到这里。

---

归并排序：

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

归并排序过程如下：

比较 a [ i ] 和 b [ j ] 的大小，若 a [ i ] ≤ b [ j ]，则将第一个有序表中的元素 a [ i ] 复制到 r [ k ] 中，并令 i 和 k 分别加上1；否则将第二个有序表中的元素 b [ j ] 复制到r [ k ]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。归并排序的算法我们通常用递归实现，先把待排序区间 [ s,t ] 以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[ s,t ]。

归并操作的工作原理如下：

第一步：申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列

第二步：设定两个指针，最初位置分别为两个已经排序序列的起始位置

第三步：比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置

重复步骤3直到某一指针超出序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

归并排序的演算过程：

假设现在有两个已排好顺序的数组：int [ ] arr1 = {2, 7, 8} 、int [ ] arr2 = {1, 4, 9}

还有一个大数组来装载它们 int  [ ] arr = new int [6] ；

步骤一：

那么，首先将两个数组的值进行比较，谁的值比较小，谁就放入大数组！

比较步骤：拿出arr1[0]和arr2[0]进行比较，显然是arr2[0]比较小，因此将arr2[0]放入大数组中，同时arr2指针往后一格（也就是 +1，累加） ，所以，现在目前为止arr = {1}

步骤二：

接着，拿arr1 [0] 和arr2 [1] 进行比较，arr1[0]较小，将arr1[0]放入大数组中，同时arr1指针往后一格

所以，现在目前为止arr = {1,2}

步骤三：

然后，拿arr1[1] 和arr2[1] 进行比较，显然是arr2[1] 比较小，将arr2[1] 放入大数组中，同时arr2指针往后一格

所以，目前arr = {1,2,4}

…以此类推…

到最后，我们会将两个已排好序的数组变成一个已排好序的数组，也就是 arr = {1,2,4,7,8,9}；至此，整个演算过程结束。

可能你会说，既然归并排序的前提是需要两个已经排好顺序的数组，但是一般没有两个已经排好顺序的数组给我们，因为排序的本质就是解决错综复杂的大小关系，那这个算法是不是有点本末倒置的刚？

其实不是，下面我们继续分析。假设现在有这样一个数组：  int [ ] arr = {2, 7, 8, 1, 4, 9} ;

如果要对此数组做归并排序，首先就可以用arr [3]，也就是元素为1的那个地方分开。然后用一个指针L指向arr[0]，一个指针M指向arr[3]，用一个指针R指向arr[5](数组最后一位)。有了指针的帮助，我们就可以将这个数组切割成是两个有序的数组了（操作的方式就可以和上面一样了）。但实际开发中中，数组一般是顺序错乱的，类似这样一个数组：int [ ] arrays = { 9, 2, 5, 1, 3, 2, 9, 5, 2, 1, 8 } ；如果遇到这种情况我们该如何用归并排序去思考问题？

我们可以这样想，首先将 int[ ] arr = {2, 7, 8, 1, 4, 9} 这个数组根据索引分隔成每一份，arr[0]它是一个有序的"数组",arr[1]它也是一个有序的"数组"，接着利用指针(L,M,R)又可以像操作两个数组一样进行排序。最终合成{2,7}…….再不断拆分合并，因此最后又回到了我们的arr = {1,2,4,7,8,9}。所以，归并排序可以排序杂乱无章的数组。

将一个大问题分成很多个小问题进行解决，最后重新组合起来，这种思想一般称为：分治法，很明显，归并排序也可以借鉴使用这种思想去操作。

    * 合并数组

    * @param arrays

    * @param L      指向数组第一个元素

    * @param M      指向数组分隔的元素

    * @param R      指向数组最后的元素

    public static void merge(int[] arrays, int L, int M, int R) {

        //左边的数组的大小 == 也就是中间的索引减去最小索引

        int [ ] leftArray = new int[M - L];

        //右边的数组大小 == 数组最大索引减去中间的索引 还要+1

        int [ ] rightArray = new int[R - M + 1];

        //往这两个数组填充数据

        for (int i = L; i < M; i++) {

            leftArray[i - L] = arrays[i];

        }

        for (int i = M; i <= R; i++) {

            rightArray[i - M] = arrays[i];

        }

        int i = 0, j = 0;

        // arrays数组的第一个元素

        int  k = L;

        //比较这两个数组的值，哪个小，就往数组上放

        while (i < leftArray.length && j < rightArray.length) {

            //谁比较小，谁将元素放入大数组中,移动指针，继续比较下一个

            if (leftArray[i] < rightArray[j]) {

                arrays[k] = leftArray[i];

                i++;

                k++;

            } else {

                arrays[k] = rightArray[j];

                j++;

                k++;

            }

}

        //如果左边的数组还没比较完，右边的数都已经完了，那么将左边的数抄到大数组中(剩下的都是大数字)

        while (i < leftArray.length) {

            arrays[k] = leftArray[i];

            i++;

            k++;

        }

        //如果右边的数组还没比较完，左边的数都已经完了，那么将右边的数抄到大数组中(剩下的都是大数字)

        while ( j < rightArray.length ) {

            arrays[k] = rightArray[j]；

            k++;

            j++;

        }

    }

以上代码是合并的代码，下面是归并排序的参考代码：

归并排序

最后是测试代码：

测试代码

另外：归并排序是一种稳定的算法。

如果这篇文章对您有开发or学习上的些许帮助，希望各位看官留下宝贵的star，谢谢。

Ps:著作权归作者所有,转载请注明作者, 商业转载请联系作者获得授权，非商业转载请注明出处(开头或结尾请添加转载出处，添加原文url地址),文章请勿滥用,也希望大家尊重笔者的劳动成果。