归并排序与快速排序

归并排序

基本思路

归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。

操作步骤如下：

1. 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
3. 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
4. 重复步骤 3 直到某一指针达到序列尾；
5. 将另一序列剩下的所有元素直接复制到合并序列尾。

示例，动图演示：

Python 实现

def merge(left, right):
    print(left, right)
    res = []
    i, j = 0, 0
    while i < len(left) and j < len(right):
        if left[i] > right[j]:
            res.append(right[j])
            j += 1
        else:
            res.append(left[i])
            i += 1
    if i < len(left):
        res.extend(left[i:])
    if j < len(right):
        res.extend(right[j:])
    return res


def merge_sort(nums):
    if len(nums) <= 1:
        return nums
    mid = len(nums) // 2
    left = merge_sort(nums[:mid])
    right = merge_sort(nums[mid:])
    return merge(left, right)

时间复杂度

• 最优时间复杂度：O(nlogn)。
• 最坏时间复杂度：O(nlogn)。
• 平均时间复杂度：O(nlogn)。
• 空间复杂度：O(1)。
• 稳定性：稳定。

快速排序

基本思路

快速排序（Quick Sort）是对冒泡排序的一种改进，基本思想是选取一个记录作为基准，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。快速排序是一种分而治之思想在 排序算法 上的典型应用。

操作步骤如下：

1. 从数列中挑出一个元素，称为 “基准”（pivot）;
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

示例，动图演示：

Python 实现

递归实现：

def part_sort(nums, left, right):
    key = nums[right]
    while left < right:
        while left < right and nums[left] < key:
            left += 1
        while left < right and nums[right] > key:
            right -= 1
        nums[left], nums[right] = nums[right], nums[left]
    nums[left], key = key, nums[left]
    return left


def quick_sort(nums, left, right):
    if left >= right:
        return
    index = part_sort(nums, left, right)
    quick_sort(nums, left, index-1)
    quick_sort(nums, index+1, right)

非递归实现：

def quick_sort(nums, left, right):
    if left > right:
        return
    tmp = nums[left]
    i = left
    j = right
    while i != j:
        while nums[j] >= tmp and i < j:
            j -= 1
        while nums[i] <= tmp and i < j:
            i += 1
        if i < j:
            nums[i], nums[j] = nums[j], nums[i]
    nums[left] = nums[i]
    nums[i] = tmp
    quick_sort(left, i - 1)
    quick_sort(i + 1, right)

时间复杂度

• 最优时间复杂度：O(nlogn)。
• 最坏时间复杂度：O(n**2)。
• 平均时间复杂度：O(nlogn)。
• 空间复杂度：O(logn)。
• 稳定性：不稳定。