数据结构和算法顺序表（数据结构预算法）

程序猿正能量

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

前言

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

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

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

二、归并排序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 T(n/2^k ) kn。当 T(n / 2^k )=T(1) 时，也就是 2^k=1，我们得到 k=log2n(以2为底n的对数) 。我们将 k 值代入上面的公式，得到 T(n)=Cn log2n (以2为底n的对数) 。如果我们用大 O 标记法来表示的话，T(n) 就等于 O(nlogn)。所以归并排序的时间复杂度是 O(nlogn)。从我们的原理分析和伪代码可以看出，归并排序的执行效率与要排序的原始数组的有序程度无关，所以其时间复杂度是非常稳定的，不管是最好情况、最坏情况，还是平均情况，时间复杂度都是 O(nlogn)-----摘自-极客时间-数据结构与算法-王争

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

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

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

三、快速排序

什么是快速排序

如果要排序数组中下标从 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)，优化过的快排除外。

虽然归并排序算法比快速排序算法稳定，但是日常开发中，使用较多还是快排，为什么呢？原因很简单，归并排序不是原地排序。

这两个排序算法我分别绘制了一个动图，但是由于微信限制，上传失败，如果需要查看动图的话，可以直接去看我csdn发布的文章：https://blog.csdn.net/qq_33220089/article/details/108679257

源码地址：https://github.com/361426201/java_TIPS/tree/master/data-structures-and-algorithms

好了骚年，看完了，不点赞收藏吗？

推荐文章：

「数据结构与算法」将5个文件中的一千万年龄合并到一个新文件中

分布式架构都讲不明白，还敢随便跳槽？

使用数组与双向链表实现一个简单的LRU算法

天真，居然还有人认为java的参数传递方式是引用传递

「并发编程」面试官：有没有比读写锁更快的锁？

,