排序算法（python）-归并排序和快速排序

排序算法（python）-归并排序和快速排序

文章目录

• 归并排序（分治策略）
• 快速排序

---

归并排序（分治策略）

归并排序是递归算法，思路是将数据表持续分裂为两半，对两半分别进行归并排序。

• 递归的基本结束条件：数据表仅有一项数据，自然是排好序的；
• 缩小规模：将数据表分裂为相等的两半，规模减小为原来的二分之一；
• 调用自身：将两半分别调用自身排序，然后将排好序的两半进行归并，得到排好序的数据表；
  

def mergeSort(alist):
    #基本结束条件
    if len(alist) > 1:
        mid = len(alist) // 2
        left = alist[:mid]
        right = alist[mid:]

        #递归调用
        mergeSort(left)
        mergeSort(right)

        #拉链式交错把左右半部分从小到大归并到结果列表中
        i = j = k = 0
        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                alist[k] = left[i]
                i += 1
            else:
                alist[k] = right[j]
                j += 1
            k += 1
        #归并左半部分剩余项
        while i < len(left):
            alist[k] = left[i]
            i += 1
            k += 1
        #归并右半部剩余项
        while j < len(right):
            alist[k] = right[j]
            j += 1
            k += 1

    return alist

test_list = [54,2,1,77,100,15,12,18]
print(mergeSort(test_list))

另一种归并排序代码；（更符合python风格）

def merge_Sort(alist):
    #递归结束条件
    if len(alist) <= 1:
        return alist
    #递归调用
    mid = len(alist) // 2
    left = merge_Sort(alist[:mid])
    right = merge_Sort(alist[mid:])

    merged = []
    while left and right:
        if left[0] <= right[0]:
            merged.append(left.pop(0))
        else:
            merged.append(right.pop(0))

    merged.extend(right if right else left)
    return merged

test_list = [54, 2, 1, 77, 100, 15, 12, 18]
print(merge_Sort(test_list))

归并算法的两个过程：分裂和归并。
分裂的过程时间复杂度：O(logn)；
归并的过程时间复杂度：O(n)；
总的时间复杂度：O(nlogn)。

另外归并排序算法使用了额外的一倍的存储空间，当数据集较大时进行排序，需要考虑进去。

快速排序

快速排序的思路是：依据一个“中值”数据项把数据表分为两半：小于中值的一半和大于中值的一半，然后每部分分别进行快速排序（递归）。

避免中位数的计算开销，所以随意找一个熟充当“中值”。

快速排序的递归三要素；

• 基本结束条件：数据表仅有1个数据项，自然是排好序的；
• 缩小规模：根据‘中值’，将数据表分为两半，最好情况是相等规模的两半；
• 调用自身：将两半分别调用自身进行排序（排序基本 *** 作在分裂过程中）。

算法步骤：

• 找到分裂数据表的目标（中值）：数据表的第一项；
• 分裂数据表
  设置左右标，左标向右移动，右标向左移动；
  1、左标一直向右移动，碰到比中值大的就停止；
  2、右标一直向左移动，碰到比中值小的就停止；
  3、然后把左右标所指的数据项交换。
• 继续移动，直到左标移到右标的右侧，停止移动；这时右标所指的位置就是中值应处的位置；
• 将中值和这个位置交换，这样做半部分比中值小，右半部分比中值大。

def quick_Sort(alist):
    quick_Sort_Helper(alist, 0, len(alist)-1)
    return alist

def quick_Sort_Helper(alist, left, right):
    #基本结束条件
    if left < right:
        #分裂
        split_point = partition(alist, left, right)
        #递归调用
        quick_Sort_Helper(alist, left, split_point-1)
        quick_Sort_Helper(alist, split_point+1, right)

def partition(alist, left, right):
    p = alist[left]
    left_mark = left + 1
    right_mark = right
    done = False
    while not done:
        #向右移动左标
        while left_mark <= right_mark and alist[left_mark] <= p:
            left_mark = left_mark + 1
        #向左移动右标
        while alist[right_mark] >= p and right_mark >= left_mark:
            right_mark = right_mark - 1
        #两标相错就结束移动
        if right_mark < left_mark:
            done = True
        else:
            #左右标的值交换
            alist[left_mark], alist[right_mark] = alist[right_mark], alist[left_mark]

    #中值就位
    alist[left], alist[right_mark] = alist[right_mark], alist[left]
    return right_mark

test_list = [54, 2, 1, 77, 100, 15, 12, 18]
print(quick_Sort(test_list))

快速排序过程分为两部分：分裂和移动。
算法复杂度：O(nlogn)。
不稳定点：中值取值问题。