您现在的位置是:首页 > 文章详情

Java常见排序基础 - 中

日期:2018-06-12点击:223

在 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),于是,我们就有了以下代码:

img_ce40720cf77cd2e42a9724229d7958ad.png
快速排序 - 1


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

img_c4128d486cf4b6908f59cdfbc98080ff.png
快速排序

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


归并排序:

归并排序(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++;

        }

    }

以上代码是合并的代码,下面是归并排序的参考代码:

img_084c426f67d47e9fc37b84f9a64282a6.png
归并排序

最后是测试代码:

img_ab80c6760330e836b579b888678fea3e.png
测试代码

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

如果这篇文章对你有帮助,希望各位看官留下宝贵的star,谢谢。

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

原文链接:https://yq.aliyun.com/articles/657505
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章