上一篇文章中分享了冒泡排序、插入排序、抉择排序这三种排序算法，它们的工夫复杂度都是O(n^2)，比拟高，适宜小规模数据的排序。这篇文章，分享两种工夫复杂度为O(nlogn)的排序算法，归并排序和疾速排序。这两种排序算法适宜大规模的数据排序，更加的罕用一些

归并排序

归并排序思维

归并排序核心思想：将待排序的数据分成前后两个局部，而后对前后两个局部的数据别离进行排序，再将前后两局部合并，失去的后果就是排好序的数据了

语言很形象，看图

归并排序应用的就是分治思维。分治，顾名思义，就是分而治之，将一个大问题分解成小的子问题来解决。小的子问题解决了，大问题也就解决了

分治思维跟之前的一篇文章中的递归很像，然而，分治是一种解决问题的解决思维，递归是一种编程技巧。归并排序用的是分治思维，能够用递归来实现

归并排序实现

如果你看过上一篇递归的文章，上边有介绍到，解递归问题，要剖析出递归公式，而后找到递归终止条件，有了这两个，基本上递归代码就进去了。有了上边的那个图，基本上能够失去下边的递推公式

递归公式MergeSort(start, end) = merge(MergeSort(start,(start+end)/2), MergeSort((start+end)/2 + 1, end))递归终止条件start >= end

MergeSort(start, end)示意的是给下标start到end之间的数组中的数据进行排序，将这个这个排序分成了两个子问题，一个是MergeSort(start,(start+end)/2)，另一个是MergeSort((start+end)/2 + 1), end)，当把这两个子问题排好序之后，再将它们合并，就把下标start到end之间的数据排好序了

最外层的那个merge就是对两个曾经有序的数组进行合并，具体过程如下：
用两个游标i和j，别离指向两个待merge数组(arr)的第一个元素（这两个数组各自是有序的），比拟游标对应地位元素的大小。如果arr[i]<arr[j]，则将arr[i]放入到一个新的数组中tmp，而后i向后挪动一位，否则，将a[j]放入tmp中，j向后一位。反复以上过程，直到有一个子数组空了，而后把另一个子数组中的数据追加到tmp的尾部，以上过程，即可将两个别离有序的数组合并成一个有序数组。具体过程如图：

代码实现

func MergeSort(arr []int) []int {    if len(arr) <= 0 {        fmt.Println("参数不非法")        return nil    }    //递归终止条件，当拆分后的数组长度少于两个元素的时候    if len(arr) < 2 {        return arr    }    midIndex := len(arr) / 2    leftArr := MergeSort(arr[0:midIndex])    rightArr := MergeSort(arr[midIndex:])    result := merge(leftArr, rightArr)    return result}func merge(leftArr, rightArr []int) []int {    var mergeRes []int    leftIndex, rightIndex := 0, 0    leftLength, rightLength := len(leftArr), len(rightArr)    for leftIndex < leftLength && rightIndex < rightLength {        if leftArr[leftIndex] > rightArr[rightIndex] {            mergeRes = append(mergeRes, rightArr[rightIndex])            rightIndex++        } else {            mergeRes = append(mergeRes, leftArr[leftIndex])            leftIndex++        }    }    if leftIndex == leftLength{        for rightIndex < rightLength {            mergeRes = append(mergeRes, rightArr[rightIndex])            rightIndex++        }    }    if rightIndex == rightLength {        for leftIndex < leftLength {            mergeRes = append(mergeRes, leftArr[leftIndex])            leftIndex++        }    }    return mergeRes}

归并排序性能剖析

首先归并排序是稳固排序算法，这个次要取决于merge操作，也就是将两个有序数组合并成一个有序数组。在合并的过程中，当两个数组中有雷同的元素时，先把前边那局部数组中元素放入到tmp中，这样就能够保障雷同的元素，在合并前后程序不变

归并排序的工夫复杂度是O(nlogn)。假如对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)=Cn+nlog2n(log以2为底的n)。所以失去归并排序的工夫复杂度就是O(nlogn)

从归并排序的原理图中能够看进去，归并排序的执行效率与要排序的原始数组的有序水平无关，所以其工夫复杂度是十分稳固的，不论是最好状况、最坏状况，还是均匀状况，工夫复杂度都是O(nlogn)

归并排序和下边的疾速排序相比，尽管工夫复杂度都是O(nlogn)，归并排序利用却不是那么宽泛，因为它不是原地排序。归并排序中合并过程须要借助额定的存储空间

递归代码的空间复杂度并不能像工夫复杂度那样累加，只管每次合并操作都须要申请额定的内存空间，但在合并实现之后，长期开拓的内存空间就被开释掉了。在任意时刻，CPU 只会有一个函数在执行，也就只会有一个长期的内存空间在应用。长期内存空间最大也不会超过n个数据的大小，所以空间复杂度是 O(n)

疾速排序

疾速排序思维

疾速排序的实现也是分治的思维，有点像归并排序，然而他们的实现思路还是齐全不一样的

疾速排序核心思想：如果要排序数组中下标从start到end之间的一组数据，抉择start到end之间的任意一个数据作为分区点（pivot）

而后遍历start到end之间的数据，将小于分区点(pivot)的数据放右边，大于分区点的数据放左边，将分区点地位的数据放两头。通过上边的操作之后，分区点之前的数据都小于分区点这个地位的数据，分区点左边的数据都大于分区点这个地位的数据

能够先不必纠结为什么通过一次分区之后变成这个样子了。往下看

依据递归的思维，如果咱们用递归排序下标从start到pivot-1之间的数据和下标从pivot+1到end之间的数据，直到区间放大为 1，就阐明所有的数据都有序了

所以，依照上边的思维，能够失去下边这个递归公式

公式：QuickSort(start...end) = QuickSort(start...pivot-1) + QuickSort(pivot+1...end)终止条件：start >= end

依据递归的公式，写进去的代码是这个样子

func QuickSort(arr []int, start int, end int) {    if start >= end {        return    }    pivot := partition(arr, start, end)    QuickSort(arr, start, pivot-1)    QuickSort(arr, pivot+1, end)}

还记得上边的归并排序不，在归并排序里边有一个merge()办法，是将两个有序的数组合并成一个有序的数组。而这里用到了一个partition()函数，就是上边说到的，随机抉择一个元素作为分区点（pivot）（个别状况下，能够抉择start到end区间的最初一个元素），而后对A[start…end]分区，函数返回分区点（pivot）的下标

晓得这个partition()函数是做什么的，下边就是各显神通的去实现它了。如果不思考空间复杂度的话，就有一个非常简单的办法。申请两个长期数组A和B，而后遍历待分区的数组arr，将小于pivot分区点对应下标值的放到A数组，大于的放到B数组，而后将A数组和B数组中的数据别离程序的放入到arr中即可。看图：

如果依照这种思路实现的话，partition()函数就须要很多额定的内存空间，所以快排就不是原地排序算法了。如果心愿快排是原地排序算法，那它的空间复杂度得是O(1)，那partition()分区函数就不能占用太多额定的内存空间，咱们就须要在arr的原地实现分区操作

下边的这个就十分奇妙的实现了空间复杂度为O(1)的状况下，实现了分区的操作（反正我是不晓得他人是怎么想进去的，没别的法子，了解它，文字描述可能比拟难了解，不慌，看图）

func partition(arr []int, start int, end int) int {    pivotValue := arr[end]    i := start    for j:=start;j < end;j++ {        if arr[j] < pivot {            arr[i], arr[j] = arr[j],arr[i]            i++        }    }    arr[i], arr[end] = arr[end], arr[i]    return i}

上边是通过游标i，将arr[start...end]分成两个局部，arr[start...i-1]的元素都是小于pivot的，能够叫它“已解决区间”，arr[i...end]是“未解决区间”。每次都从未解决的区间arr[i...end]中取一个元素arr[j]，与pivotValue比照，如果小于pivotValue，则将其退出到已解决区间的尾部，也就是arr[i]的地位。文字描述不好了解，看图

疾速排序实现

原理上边都介绍了，下边是残缺的代码实现

package quickSortfunc QuickSort(arr []int, start int, end int) {    if start >= end {        return    }    pivot := partition(arr, start, end)    QuickSort(arr, start, pivot-1)    QuickSort(arr, pivot+1, end)}func partition(arr []int, start int, end int) int {    pivotValue := arr[end]    i := start    for j:=start;j < end;j++ {        if arr[j] < pivotValue {            arr[i], arr[j] = arr[j],arr[i]            i++        }    }    arr[i], arr[end] = arr[end], arr[i]    return i}

疾速排序性能剖析

上边应用了一种奇妙的办法，在空间复杂度为O(1)的状况下，实现了疾速排序，所以快排是一个稳固的排序算法

因为分区的过程波及替换操作，如果数组中有两个雷同的元素，比方序列 6，8，7，6，3，5，9，4，在通过第一次分区操作之后，两个6的绝对先后顺序就会扭转（跟着上边的分区算法图，很容易能够推出来）。所以，疾速排序并不是一个稳固的排序算法

快排也是用递归来实现的。对于递归代码的工夫复杂度，归并排序中剖析进去的公式，这里也还是实用的。如果每次分区操作，都能正好把数组分成大小靠近相等的两个小区间，那快排的工夫复杂度递推求解公式跟归并是雷同的。所以，快排的工夫复杂度也是O(nlogn)

T(1) = C；   n=1 时，只须要常量级的执行工夫，所以示意为 C。T(n) = 2*T(n/2) + n； n>1

然而，公式成立的前提是每次分区操作，咱们抉择的pivot都很适合，正好能将大区间对等地一分为二。但实际上这种状况是很难实现的

如果数组中的数据原来曾经是有序的了，比方 1，3，5，6，8。如果每次抉择最初一个元素作为pivot，那每次分区失去的两个区间都是不均等的。咱们须要进行大概n次分区操作，能力实现快排的整个过程。每次分区咱们均匀要扫描大概n/2个元素，这种状况下，快排的工夫复杂度就从O(nlogn)进化成了O(n^2)

快排在大部分状况下的工夫复杂度都能够做到O(nlogn)，只有在极其状况下，才会进化到O(n^2)

归并排序和疾速排序比照

两种排序思维的区别

快排和归并用的都是分治思维，递推公式和递归代码也十分类似，那它们的区别在哪里呢？

能够发现，归并排序的处理过程是由下到上的，先解决子问题，而后再合并。而快排正好相同，它的处理过程是由上到下的，先分区，而后再解决子问题

性能上的差别

归并排序尽管是稳固的、工夫复杂度为O(nlogn)的排序算法，然而它是非原地排序算法。归并之所以是非原地排序算法，次要起因是合并函数无奈在原地执行。疾速排序通过设计奇妙的原地分区函数，能够实现原地排序，解决了归并排序占用太多内存的问题