你以为只是简单的排序？（二）

上一篇文章中分享了冒泡排序、插入排序、选择排序这三种排序算法，它们的时间复杂度都是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 quickSort
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)
}
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)的排序算法，但是它是非原地排序算法。归并之所以是非原地排序算法，主要原因是合并函数无法在原地执行。快速排序通过设计巧妙的原地分区函数，可以实现原地排序，解决了归并排序占用太多内存的问题