快排
原理
快排利用分治思想。快排的思想是这样的：如果要排序数组中下标从 p 到 r 之间的一组数据，我们选择 p 到 r 之间的任意一个数据作为 pivot（分区点）。我们遍历 p 到 r 之间的数据，将小于 pivot 的放到左边，将大于 pivot 的放到右边，将 pivot 放到中间。经过这一步骤之后，数组 p 到 r 之间的数据就被分成了三个部分，前面 p 到 q-1 之间都是小于 pivot 的，中间是 pivot，后面的 q+1 到 r 之间是大于 pivot 的。
归并排序
原理
归并排序也是用到了分治思想，将要排序的数组取中间点为节点其值为 k，然后将其拆分成两个数组，比选定节点值小的放到左边数组left，大于k 的放在右边数组，然后再对这两个数组进行排序，最后合并两个数组为一个数组
快排源码：
算法导论中的
def quick_sort(array, l, r):
if l < r:
q = partition(array, l, r)
quick_sort(array, l, q - 1)
quick_sort(array, q + 1, r)
def partition(array, l, r):
x = array[r]
i = l - 1
for j in range(l, r):
if array[j] <= x:
i += 1
array[i], array[j] = array[j], array[i]
array[i + 1], array[r] = array[r], array[i+1]
归并排序
def merge(L,R):
n = len(L) + len(R)
L.append(float("inf"))
R.append(float("inf"))
i = 0
j = 0
A = []
for k in range(0,n):
if L[i]<=R[j]:
A.append(L[i])
i = i+1
else:
A.append(R[j])
j = j+1
return A
merge([1,5,6],[2,3])
#自定义merge_sort函数
def merge_sort(A):
l = len(A)
if l<=1:
return A
else:
mid = l//2
print(mid)
left = merge_sort(A[0:mid])
right = merge_sort(A[mid:])
return merge(left,right)
总结
两个排序平均时间复杂度都是O(nlogn)，快排最坏时间复杂度为 O(n^2)，归并则是O(nlogn)，空间复杂度方面，快排是原地排序的数组 O(1)，归并则是 O(n)，所以这就是为什么实际上，快排的使用远远高于归并排序。
