入秋的第一篇数据结构算法：看看归并与快排的风采
=============================
===============================================
既然都说了算法是一个程序猿的灵魂，那么我们当然是要冲击一下灵魂了，没错，这篇文章我们将算法：归并排序和快速排序。
=====================================================================
归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
根据概念和动图，你是否能看明白呢？也许还有点懵吧，其实归并就是借助了分治的思想，把一个大问题拆分成许多个小问题，然后解决小问题，小问题解决了，大问题自然就解决了，这个时候你可能有点疑惑了,刚刚说的这个不就是递归吗？为什么又成分治了呢？这里大家要搞明白一点：分治是一种思想，递归是一种实现技巧。
也许上面的动图不太好理解，那么请看下图
先将需要排序的数组进行拆解，拆解到只有两个元素二点之后进行排序，然后在合并，如此反复，即可得到一个完全有序的数组。
下面我们就一起来使用分治思想、递归方案来实现归并排序。
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
我们假设对 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*(2T(n/4) + n/2) + n = 4T(n/4) + 2*n
= 4*(2T(n/8) + n/4) + 2n = 8T(n/8) + 3n
= 8*(2T(n/16) + n/8) + 3n= 16T(n/16) + 4n
......
= 2^k * T(n/2^k) + k * n
......
通过这样一步一步分解推导，我们可以得到 T(n) = 2 k 2^k 2k T(n/ 2 k 2^k 2k)+kn。当 T( n / 2 k n/2^k n/2k)=T(1) 时，也就是 2 k 2^k 2k=1，我们得到 k= l o g 2 n log_2n log2?n 。我们将 k 值代入上面的公式，得到 T(n)=Cn+ l o g 2 n log_2n log2?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
*/
评论