• 3

  • 443

入秋的第一篇数据结构算法:看看归并与快排的风采

云哥

关注云计算

3星期前

程序猿正能量

靠代码行数来衡量开发进度,就像是凭重量来衡量飞机制造的进度。—比尔·盖茨

前言

作为开发人员,尤其是三年以上工作经验的 ,如果整天都是在CRUD,这个时候,你是不是需要憧憬一下35岁之后的生活呢?退休送外卖还是回老家种田呢?因为你除了CRUD,其他你一概不会,所以这个时候,你需要改变一下自己,比如:学习数据结构与算法俗话说的好,算法是程序员的灵魂,只有触及到灵魂深处,你才能看见诗和远方,加油吧,骚年!

@TOC

一、我们这篇文章讲什么呢?

既然都说了算法是一个程序猿的灵魂,那么我们当然是要冲击一下灵魂了,没错,这篇文章我们将算法:归并排序和快速排序。

二、归并排序

1.什么是归并排序

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

在这里插入图片描述
根据概念和动图,你是否能看明白呢?也许还有点懵吧,其实归并就是借助了分治的思想,把一个大问题拆分成许多个小问题,然后解决小问题,小问题解决了,大问题自然就解决了,这个时候你可能有点疑惑了,刚刚说的这个不就是递归吗?为什么又成分治了呢?这里大家要搞明白一点: 分治是一种思想,递归是一种实现技巧。 也许上面的动图不太好理解,那么请看下图
在这里插入图片描述
先将需要排序的数组进行拆解,拆解到只有两个元素二点之后进行排序,然后在合并,如此反复,即可得到一个完全有序的数组。

下面我们就一起来使用分治思想、递归方案来实现归并排序。

2.利用递归实现归并排序

package com.liuxing.sort;

import com.liuxing.util.Print;

/**
 * @author liuxing007
 * @ClassName MergeSort
 * @Description 归并排序(Merge Sort)
 * 归并排序的核心思想还是蛮简单的。如果要排序一个数组,
 * 我们先把数组从中间分成前后两部分,然后对前后两部分分别排序,
 * 再将排好序的两部分合并在一起,这样整个数组就都有序了。
 *
 * 时间复杂度:O(nlogn)
 * 空间复杂度:O(n)
 * 不是原地排序算法
 * @date 2020/9/17 15:04
 */

public class MergeSort {

    public static void main(String[] args) {
        int[] arr = new int[]{6,4,1,7,2,5,8,3};
        int length = arr.length;
        System.out.println("排序前数组===========");
        Print.print(arr, length);
        sort(arr, length);
        System.out.println("排序后数组===========");
        Print.print(arr, length);
    }

    /**
     * 排序算法
     * @param arr 数组
     * @param l 数组长度
     */
    private static void sort(int[] arr,int l){
        sortMerge(arr,0,l-1);
    }


    /**
     * 递归
     * @param arr 数组
     * @param p 开始位置下表
     * @param r 结束位置下表
     */
    private static void sortMerge(int[] arr,int p,int r){
        if(p >= r){
            return ;
        }
        //分治的下标,这里我采用p到r的中间位置index。
        int index = p + (r-p)/2;
        //左侧递归
        sortMerge(arr,p,index);
        //右侧递归
        sortMerge(arr, index + 1, r);
         merge(arr, p, index,r);
         System.out.println("排序后数组===========");
         Print.print(arr, length);
    }

    /**
     * 合并计算
     * @param arr 原素组
     * @param l 左侧数组开始位置下标
     * @param index 左侧数组结束位置下标
     * @param r 右侧数组结束位置下标
     */
    private static void merge(int[] arr, int l,int index, int r) {
        //临时数组,这里可以优化,数组的频繁创建会降低程序运行的效率,
        // 所以这里可以将这个临时数组改成参数传递进来,在数量较大的时候执行效率变化变焦显著
        int[] temp = new int[r-l+1];
        //左侧开始下标
        int i= l;
        //右侧开始下标
        int j = index+1;
        //临时数组下标
        int k=0;
        // 左侧数组与右侧数组进行对比,将小的元素放入临时数组中
        while(i<=index && j<=r){
            if(arr[i]<arr[j]){
                temp[k++] = arr[i++];
            }else{
                temp[k++] = arr[j++];
            }
        }
        //对比完成之后,需要把两侧数组中还没有对比的数据加入到临时数组中
        //把左边剩余元素加入临时数组中
        while(i<=index){
            temp[k++] = arr[i++];
        }
        //把右边剩余元素加入临时数组中
        while(j<=r){
            temp[k++] = arr[j++];
        }
        //将临时数组的元素拷贝原数组中
        for(int x=0;x<temp.length;x++){
            arr[x+l] = temp[x];
        }
    }

}

复制代码
package com.liuxing.util;

/**
 * @author liuxing007
 * @ClassName Print
 * @Description 打印
 * @date 2020/9/17 11:13
 */
public class Print {

    /***
     * 打印数据
     * @param arr 数组
     * @param length 数组长度
     */
    public static void print(int[] arr, int length) {
        for (int i = 0; i < length; ++i) {
            System.out.print(arr[i] + "  ");
        }
        System.out.println("");
    }


}

复制代码
排序前数组===========
6  4  1  7  2  5  8  3  
合并后的数据
4  6  1  7  2  5  8  3  
合并后的数据
4  6  1  7  2  5  8  3  
合并后的数据
1  4  6  7  2  5  8  3  
合并后的数据
1  4  6  7  2  5  8  3  
合并后的数据
1  4  6  7  2  5  3  8  
合并后的数据
1  4  6  7  2  3  5  8  
合并后的数据
1  2  3  4  5  6  7  8  
排序后数组===========
1  2  3  4  5  6  7  8  

Process finished with exit code 0

复制代码

3.时间空间复杂度分析

我们假设对 n 个元素进行归并排序需要的时间是 T(n),那分解成两个子数组排序的时间都是 T(n/2)。我们知道,merge() 函数合并两个有序子数组的时间复杂度是 O(n)。所以,套用前面的公式,归并排序的时间复杂度的计算公式就是:

T(1) = C; n=1时,只需要常量级的执行时间,所以表示为C。
T(n) = 2*T(n/2) + n; n>1
复制代码

通过这个公式,如何来求解 T(n) 呢?还不够直观?那我们再进一步分解一下计算过程。

T(n) = 2*T(n/2) + n 
= 2*(2*T(n/4) + n/2) + n = 4*T(n/4) + 2*n 
= 4*(2*T(n/8) + n/4) + 2*n = 8*T(n/8) + 3*n 
= 8*(2*T(n/16) + n/8) + 3*n= 16*T(n/16) + 4*n
 ...... 
= 2^k * T(n/2^k) + k * n 
......
 
复制代码

通过这样一步一步分解推导,我们可以得到 T(n) = 2 k 2^k T(n/ 2 k 2^k )+kn。当 T( n / 2 k n/2^k )=T(1) 时,也就是 2 k 2^k =1,我们得到 k= l o g 2 n log_2n 。我们将 k 值代入上面的公式,得到 T(n)=Cn+ l o g 2 n log_2n 。如果我们用大 O 标记法来表示的话,T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。从我们的原理分析和伪代码可以看出,归并排序的执行效率与要排序的原始数组的有序程度无关,所以其时间复杂度是非常稳定的,不管是最好情况、最坏情况,还是平均情况,时间复杂度都是 O(nlogn)-----摘自-极客时间-数据结构与算法-王争

归并排序的时间复杂度已经很优秀了,但为什么我们在日常开发中却很少看到他的身影呢?我们先来分析一下归并排序的空间复杂度。

我们需要注意的是合并方法,这个方法中我们使用了一个临时数组用来存储数据,但是合并之后这个临时数组就会释放,又因为临时数组的最大长度不会超过原始数组长度n,所以归并排序的空间复杂度为:O(n)

为什么开发中很少人使用到归并排序呢?原因很简单,因为它不是一个原地排序算法,这个时候你可能会有疑惑了,什么是原地排序算法?简单来说:不通过其他空间来完成的排序,我们称它为原地排序算法,但归并排序很明显借用了一个临时数组,所以它不是一个原地排序算法,即使它的时间复杂都很稳定,使用的人也比较少。

三、快速排序

1.什么是快速排序

如果要排序数组中下标从 p 到 r 之间的一组数据, 我们选择 p 到 r 之间的任意一个数据作为 pivot(分区点)。我们遍历 p 到 r 之间的数据,将小于 pivot 的放到左边, 将大于 pivot 的放到右边,将 pivot 放到中间。经过这一步骤之后, 数组 p 到 r 之间的数据就被分成了三个部分,前面 p 到 q-1 之间都是小于 pivot 的,中间是 pivot,后面的 q+1 到 r 之间是大于 pivot 的.根据分治、递归的处理思想,我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据,直到区间缩小为 1,就说明所有的数据都有序了。(摘自-极客时间-数据结构与算法-王争)

在这里插入图片描述
快速排序的思想和归并排序有点类似,都是通过分治的思想,利用递归实现排序,只不过实现的细节有所不同,快排(快速排序)需要一个分区点,可以在数组中随便去一个元素作为分区点即可,后面就是前面讲到的概念了,归并的核心在于合并,而快排的核心在于分区点,所以我们就一起来看看在获取分区点的时候快排都干了些啥?

之前说过,快排选择一个分区点(pivot)之后,将小于分区点(pivot)的元素放左边,分区点(pivot)放中间,大于分区点(pivot)的放右边,这个一看就很好解决嘛,和归并排序一样,我先申请两个临时数组,一个存放小于分区点元素的数组,一个存放大于分区点元素的数组,这样,就能完美的解决了,非常简单,但是这个就和归并排序面临这同一样的一个问题:==它不是一个原地排序算法==,那如果我希望快排是一个原地排序算法呢?我们应该如何实现呢?其实也不难,我们可以参考一下选择排序:【数据结构与算法】常见的三种排序(冒泡排序、插入排序、选择排序

在这里插入图片描述

我们定义一个游标 i (数组下标) 把数组a[p-(r-1)]分成两部分,A[p-(i-1)]都是小于分区点(pivot)的,我们叫他“==已排序区间==”。a[(i+1) - (r-1)]都是大于分区点(pivot)元素的,我们叫他“==未排序区间==”,只要从未排序区间去值与分区点(pivot)进行比较,如果小于分区点(pivot),那么将此元素追加到已排序区间中(a[i]),否者不需要变动。

我还是准备了一张图给大家参考,也许大家就能明白了。

在这里插入图片描述
这是一次分区交换的结果,当把所有分区都交换完成之后,整个数组也就有序了,既然快速排序的思想已经讲的差不多了,下面我们一起来看看代码怎么实现

快排代码实现

package com.liuxing.sort;

import com.liuxing.util.DataUtil;
import com.liuxing.util.Print;

/**
 * @author liuxing007
 * @ClassName Quicksort
 * @Description 快速排序
 *
 * 如果要排序数组中下标从 p 到 r 之间的一组数据,
 * 我们选择 p 到 r 之间的任意一个数据作为 pivot(分区点)。
 * 我们遍历 p 到 r 之间的数据,将小于 pivot 的放到左边,
 * 将大于 pivot 的放到右边,将 pivot 放到中间。经过这一步骤之后,
 * 数组 p 到 r 之间的数据就被分成了三个部分,
 * 前面 p 到 q-1 之间都是小于 pivot 的,中间是 pivot,
 * 后面的 q+1 到 r 之间是大于 pivot 的.
 * 根据分治、递归的处理思想,
 * 我们可以用递归排序下标从 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据,
 * 直到区间缩小为 1,就说明所有的数据都有序了(摘自-极客时间-数据结构与算法-王争)
 *
 * 时间复杂度:O(nlogn)
 * 空间复杂度:O(1)
 * 原地排序算法,但不是稳点排序算法
 * @date 2020/9/18 10:22
 */
public class Quicksort {

    public static void main(String[] args) {
        int[] arr = new int[]{6, 5, 4, 3, 2, 1};
//        int[] arr = DataUtil.createIntArrData();
        int length = arr.length;
        System.out.println("排序前数组===========");
        Print.print(arr, length);
        sort(arr, length);
        System.out.println("排序后数组===========");
        Print.print(arr, length);
    }

    /**
     * 排序算法
     * @param arr 数组
     * @param l 数组长度
     */
    private static void sort(int[] arr,int l){
        sortRec(arr,0,l-1);
    }

    /**
     * 递归
     * @param arr
     * @param p
     * @param r
     */
    private static void sortRec(int[] arr, int p, int r) {
        //递归终止条件
        if (p >= r){
            return;
        }
        //获取分区点
        int q = partition(arr, p, r);
        //左侧递归
        sortRec(arr, p, q-1);
        //右侧递归
        sortRec(arr, q+1, r);
    }

    /**
     * 分区
     * @param arr 原始数组
     * @param p 数组起始下标
     * @param r 数组结束下标
     * @return  分区下标
     */
    private static int partition(int[] arr, int p, int r) {
        //取最后一个元素作为分区的值
        int pivot = arr[r];
        int i = p;
        for(int j = p; j < r; ++j) {
            if (arr[j] < pivot) {
                if (i == j) {
                    ++i;
                } else {
                    //交换位置
                    int tmp = arr[i];
                    arr[i++] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
        //交换位置
        int tmp = arr[i];
        arr[i] = arr[r];
        arr[r] = tmp;
        return i;
    }


}

复制代码
排序前数组===========
6  5  4  10  2  1  
排序后数组===========
1  2  4  5  6  10  

Process finished with exit code 0
复制代码

2.时间空间复杂度分析

快排的实现方式与归并排序一样,都是通过递归实现,所以他们的时间复杂度是一样的:O(nlogn),但是它是一种不稳定的排序算法,当极端条件下,他的时间复杂度将会衰减到O(n^2),为什么这样说呢?如果我们的原始数组就是一个有序数组,分区点还是选择最后一个,那么就会出现一边有数据,一边没有数据,这样性能会急速下滑,所以在使用快排的时候分区点很重要。

然后我们再来看看快排的空间复杂度,快排在交换的的时候没有使用到其他数组或者空间,所以他是一个原地排序算法,交换的时候只涉及到两个元素,所以不难分析空间复杂度为:O(1)

所以快排时间复杂度:O(nlogn),龙剑复杂度:O(1),极端情况下时间复杂度会退化到O(n^2),优化过的快排除外。

总结

归并排序是一种稳定、非原地的排序算法,时间复杂度:O(nlogn),空间复杂度:O(n)。 快排时间是一种非稳定,原地排序算法,复杂度:O(nlogn),空间复杂度:O(1),极端情况下时间复杂度会退化到O(n^2),优化过的快排除外。

虽然归并排序算法比快速排序算法稳定,但是日常开发中,使用较多还是快排,为什么呢?原因很简单,归并排序不是原地排序。 源码地址:github.com/361426201/j…

好了骚年,看完了,不点赞收藏吗?

在这里插入图片描述

 

免责声明:文章版权归原作者所有,其内容与观点不代表Unitimes立场,亦不构成任何投资意见或建议。

云计算

443

相关文章推荐

未登录头像

暂无评论