利用分治思想的两大排序算法笔记

近日流行的有个以教育为目的帮助学习主要算法的python模块：pygorithm

使用pip3 install pygorithm安装后

from pygorithm.sorting import bubble_sort
code = bubble_sort.get_code()
print(code)

就可以看到相应算法的实现代码了，还是挺方便的。主要运用了inspect标准库中的getsource函数：

def get_code():
    import inspect
    return inspect.getsource(some_algorithm)

顺便复习下利用分治思想的两大排序算法：归并排序和快速排序。

归并排序简述

• 归并排序(merge_sort)是分治思想的一个典型应用。
  分治的简单理解就是将大问题分解为两个或多个更简单的小问题，组合小问题的解得到原问题的答案。
• 在归并排序中，对原数组排序等同于将原数组分为具有相近大小的两份，对这两个数组分别排序，然后合并它们。

图解与实现

• 下图来自 《Algorithms - Robert Sedgewick and Kevin Wayne》：对一乱序的英文字母列表排序，将其分为两半，分别对左右两部分排序，然后合并排序结果。

  
  

• 下图来自维基百科：将一个无序的数组自顶向下递归分解，每次二分，直到每份只有一个数，然后将它们逐层合并为有序数组，生成最终的排序结果。（分解与合并是对称的，即分解的过程限定了合并的路径）。
  

  

• 用代码表示上述过程（代码出自rosettacode.org）

from heapq import merge
 
def merge_sort(m):
    if len(m) <= 1:  # 直到每份只有一个数，停止分解
        return m     # 一个数本身就是有序，直接返回
 
    middle = len(m) // 2  # 二分法选取分界点，二分位置与上图略有不同，与上图一致应为 middle = (len(m)+1) // 2
    left = m[:middle]  # 由分界点得到左侧 与 右侧子数组
    right = m[middle:]
 
    left = merge_sort(left)   # 递归分解(与排序) 左侧 和 右侧子数组
    right = merge_sort(right)  
    # print(left, '+', right)      # 取消注释，查看合并过程
    return list(merge(left, right))   # 沿递归调用的逆序合并有序数组

# merge_sort([38, 27, 43, 3, 9, 82, 10, 19])

• 其中merge()为合并多个有序数组的函数：
  

• 输出，与图示相符：

  
  
• merge()的简单实现，如何合并两个有序数组：对两个数组的队首元素进行比较，取出其中小的放入新数组，对取出该数后的两个数组的队首元素再进行比较，如此循环直到某一数组为空，将另一非空数组中的所有数按原序添加至新数组即可。如对(b)中两个数组S1和S2，比较队首24和31的大小，选择较小的24放入新数组S的17的后面。
  
  
• 用代码表示上述过程（代码出自pygorithm）

def merge(S1, S2):
    """ Function to merge two arrays """
    S = []  # 新数组S
    while len(S1) != 0 and len(S2) != 0: # S1、S2数组中有一个被取空了则跳出循环
        if S1[0] < S2[0]:  # 比较队首元素，选择小的元素取出
            S.append(S1[0])  # 添加该元素到新数组
            S1.remove(S1[0])  # 在原数组中去除该元素
        else:
            S.append(S2[0])
            S2.remove(S2[0])
    if len(S1) == 0:  # 将非空的数组中的元素按原序添加到新数组尾部
        S += S2
    else:
        S += S1
    return S

另一版本（代码出自rosettacode.org）：

def merge(left, right):
    result = []                 # 新数组S
    left_idx, right_idx = 0, 0  # 数组S1和S2的队首元素索引
    while left_idx < len(left) and right_idx < len(right):  # 当其中一个索引越界即其中一个数组已经取空时跳出循环
        # 改变比较的方向改变排序的方向，这里是小的数在前
        if left[left_idx] <= right[right_idx]:  # 比较队首元素的大小
            result.append(left[left_idx])       # 将小的元素放入新数组
            left_idx += 1                       # 队首索引后移一位
        else:
            result.append(right[right_idx])
            right_idx += 1

    if left_idx < len(left):  # 如果S1为非空，将S1中剩余数按原有顺序直接添加在新数组尾部
        result.extend(left[left_idx:])
    if right_idx < len(right):  # 如果S2为非空，将S2中剩余数按原有顺序直接添加在新数组尾部
        result.extend(right[right_idx:])
    return result

• 输出，与图示相符：

  
  

快速排序简述

• 快速排序同样应用了分治的思想。

回顾：分治是将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题，然后将这些子问题的解组合为原问题的解。

• 类似于归并排序，快排也是将要排序的原数组分成两份（这里不保证它们的大小相似），对这两个数组分别排序，然后合并它们。
• 不过，归并排序在分解时很轻松（直接二分），合并时比较费力（对两个有序子数组中的元素做了大量比较）；而快速排序在分割为两份时比较费力，要先从数组中任意选择一个基准数，使得分割得到的两份子数组中，一份中的所有数都小于该基准数，而另一份中所有数都大于它，而合并的时候，由于一组中所有数都比另一组所有数小，可以直接合并（在基准数两侧），所以合并很轻松。

图解与实现

• 代码实现（代码出自pygorithm）:

def quick_sort(arr):
    if len(arr) <= 1:  # 直到每份只有一个数，停止分解
        return arr     # 一个数本身就是有序，直接返回

    pivot = arr[len(arr) // 2]  # pivot为选取的基准数
    left = [x for x in arr if x < pivot]     # 将所有小于基准数的放入左边数组
    middle = [x for x in arr if x == pivot]  # 所有值为基准数的放到中间
    right = [x for x in arr if x > pivot]    # 将所有大于基准数的放入右边数组
    return quick_sort(left) + middle + quick_sort(right)  # 递归排列左边和右边数组，合并时直接将左中右数组顺序相连即可

另一版本（代码出自rosettacode.org，该网站上还有多种实现）（思路基本一致）：

def quick_sort(list):
    if not list:
        return []
    else:
        pivot = list[0]
        less = [x for x in list[1:] if x <  pivot]
        more = [x for x in list[1:] if x >= pivot]
        return quick_sort(less) + [pivot] + quick_sort(more)

• 这样看来用python实现真是非常简单，但是运算量较大，我们从C语言的角度看看如何实现分割过程的。
• 假设要对如下数组进行排序，我们选择第一个值72作为基准数。
  
• 实现分割，最简单的思路便是单方向逼近，如从最右边开始（索引j=9），将小于或等于基准数的值移动到基准数左边。
  
• 进一步，从左右两边逼近，将小于或等于基准数的值移动到基准数左边，且将大于基准数的值移动到基准数右边
  
  

• 代码

  
  

// 出处不详
#include<iostream>
using namespace std;
void quickSort(int a[],int,int);

int main()
{
    int array[] = {72,6,57,6,88,60,42,72,85,83,72,73,48,85};
    int k;
    int len=sizeof(array)/sizeof(int);

    cout<<"原始数组为:"<<endl;
    for(k=0;k<len;k++)
    cout<<array[k]<<",";
    cout<<endl;

    quickSort(array,0,len-1);

    cout<<"排序后数组:"<<endl;
    for(k=0;k<len;k++)
    cout<<array[k]<<",";
    cout<<endl;

    return 0;
}


void quickSort(int s[], int l, int r)
{
    if (l< r)
    {
        int i = l, j = r, x = s[l]; // 保留l,r的值,x为此次比较的基准数
        while (i < j) // 循环终止条件
        {
            while(i < j && s[j]>= x) // 从右向左找第一个小于x的数
                j--;
            if(i < j)
                s[i++] = s[j];
            while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数
                i++;
            if(i < j)
                s[j--] = s[i];
        }
        s[i] = x; // 分割结束

        quickSort(s, l, i - 1); // 递归调用 , i现在指向基准数
        quickSort(s, i + 1, r);
    }
}