关于快速排序的函数式实现

函数式编程就像是数学中的函数调用，可以将函数反复嵌套调用，一般的调用思路是将问题转化为复杂函数，将复杂函数一步步简单化，从顶向下细化函数，最终解决问题。

在函数式编程中，使用map、reduce、fliter、递归等方法，避免使用for、while，这样会避免很多诸如i，j，k等复杂的循环控制变量，而且也更加利于理解，因为传统的过程、面向对象的编程方式是计算机解释性的，是符合计算机理解的表达形式，所以有许多的循环控制变量、状态控制变量等，对于编程人员来讲无疑是最为晦涩难懂的地方，人类相对较容易理解，数学上的函数嵌套调用的方式。

下文介绍一种函数式编程实现的快速排序。

函数式

def qSort(arr: list):
    if len(arr) > 0:
        # 获得以首元素为基准的左边较小的序列
        l = list(filter(lambda x: x <= arr[0], arr[1:]))
        # 获取以首元素为基准的右边较大的序列
        r = list(filter(lambda x: x > arr[0], arr[1:]))
        # 递归排序左边序列
        ll = qSort(l)
        # 递归排序右边序列
        rr = qSort(r)
        # 结果合并
        t = []
        # 按照 左边序列（较小） 首元素 右边序列（较大）合并
        t.extend(ll)
        t.append(arr[0])
        t.extend(rr)
        return t
    else:
        # 如果分解到空序列
        return []

过程式

过程式编程需要定义两个独立的函数，对每一次的快排的方式进行定义（partion），对待排数组的分解模式进行定义（qSort）。

def partion(arr,l,r):
    key = arr[l]
    low = l
    high = r
    while low < high:
        while low < high and arr[high] >= key:
            high = high - 1
        arr[low] = arr[high]
        while low < high and arr[low] <= key:
            low = low + 1
        arr[high] = arr[low]
     arr[low] = key
    return low


def qSort(arr, l ,r):
    if l < r:
        low = partion(arr, l, r)
        qSort(arr, l, low - 1)
        qSort(arr, low + 1, r)

从上文可以看出过程式编程的qSort含有大量的循环控制变量，以及状态变量，其实这些变量都是为了实现过程式编程的中间变量，和快速排序的主体思想是无关的不易理解，反观函数式编程的代码十分简洁，表达巨清楚，无无关循环控制变量以及状态变量。且函数式编程易于转化为多线程程序。