【连载】快速排序算法的普通版和简化版实现

落日映苍穹つ 2022-06-05 09:50 216阅读 0赞

### 快速排序算法 ###

> 针对本算法仅提供核心部分代码。代码均是基于python。

#### 1. 算法核心： ####

*  分治思想
 *  步骤：
    
     *  找出一个元素（理论上可以随便找一个）作为基准(pivot),然后对数组进行分区操作, 使基准左边元素的值都不大于基准值, 基准右边的元素值 都不小于基准值，如此作为基准的元素调整到排序后的正确位置。
     *  递归快速排序，将其他n-1个元素也调整到排序后的正确位置。
     *  最后每个元素都是在排序后的正确位置，排序完成。

#### 2. 算法实现： ####

##### 2.1 普通版 #####

> 为方便使用，下面定义一个非递归的主函数，其中调用一个递归定义的函数（可以作为局部定义），给定划分范围初值：

def quick_sort(lst):
        qsort_rec(let, 0, len(lst) - 1)

*  递归过程的框架：

def qsort_rec(lst, l, r):
        if l >= r: return
        i = 1;
        j = r
        pivot = lst[i]
        while i < j:
            ... ...
            ... ...
        lst[i] = pivot
        qsort_rec(lst, l, i - 1)
        qsort_rec(lst, i + 1, r)

*  递归的快速排序函数:

def qsort_rec(lst, l, r):
        if l >= r: return
        i = 1;
        j = r
        pivot = lst[i]
        while i < j:
            while i < j and lst[j].key >= pivot.key
                j -= 1
            if i < j:
                lst[i] = lst[j]
                i += 1
            while i < j and lst[i].key <= pivot.key
                i += 1
            if i < j:
                lst[j] = lst[i]
                j -= 1
        lst[i] = pivot
        qsort_rec(lst, l, i - 1)
        qsort_rec(let, i + 1, r)

上述代码过程完全遵循上面的框架，只是填入了划分过程的细节，包括各种比较条件、变量 i 和 j 的修改操作、元素移动操作等。

##### 2.2 简化版 #####

> 思想：R作为划分标准的记录，以其关键码K作为分界线，将表中记录（一般而言，是表中一个分段中的记录）划分为两组。工作过程中本分段的记录（除R外）顺序分为三组：小记录，大记录，未检查记录。

这里用两个下表变量，i 的值总是最后一个小记录的下标，而 j 的值是第一个未处理记录的下标。每次迭代比较K与记录 j 的关键码，有两种情况:

*  记录 j 较大：这时简单地将 j 加一，又恢复到原图类似状态。
 *  记录 j 较小：这时需要把这个记录调到左边，做法是将 i 加一，而后交换 i 和 j 位置的记录，并将 j 值加一，又恢复到原图类似状态。
 *  代码实现：

def quick_sort(lst):
        def qsort(lst, begin, end):
            if begin >= end:
                return
            pivot = lst[begin].key
            i = begin
            for j in range(begin + 1, end + 1):
                if lst[i].key < pivot:
                    i += 1
                    lst[i], lst[j] = lst[j], lst[i]
            lst[begin], lst[i] = lst[i], lst[begin]
            qsort(lst, begin, i - 1)
            qsort(lst, i + 1, end)
        qsort(lst, 0, len(lst) - 1)

如果需要完整代码实现的话，可以到[我的Github仓库下载][Github]，不过，只提供Java版代码实现。

[Github]: https://github.com/Zychaowill/AlgorithmAndDataStructure/blob/master/src/main/java/zychaowill/algorithm/newsort/QuickSort.java