博客

快速排序的四种python实现（推荐）

  • Post category:Python

下面是详细讲解“快速排序的四种Python实现（推荐）”的完整攻略，包括快速排序的定义、快速排序的基本思想、四种Python实现和两个示例说明。

快速排序定义

快速排序是一种常用的排序算法，它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均另一部分记录的关键字小，然后再分别对这两分记录继续进行排序，以达到整个序列有序的目的。

快速排序基本思想

快速排序的基本思想是分治法，具体过程如下：

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

四种Python实现

下面是四种Python实现快速排序的方法：

方法一：使用列表推导式

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

方法二：使用filter函数

def quick_sort(lst):
    if not lst:
        return []
    else:
        pivot = lst[0]
        less = list(filter(lambda x: x < pivot, lst[1:]))
        greater = list(filter(lambda x: x >= pivot, lst[1:]))
        return quick_sort(less) + [pivot] + quick_sort(greater)

方法三：使用递归

def quick_sort(lst):
    if len(lst) <= 1:
        return lst
    else:
        pivot = lst[0]
        left = [x for x in lst[1:] if x < pivot]
        right = [x for x in lst[1:] if x >= pivot]
        return quick_sort(left) + [pivot] + quick_sort(right)

方法四：使用双向扫描

def quick_sort(lst):
    if len(lst) <= 1:
        return lst
    else:
        pivot = lst[0]
        i = 0
        j = len(lst) - 1
        while i < j:
            while i < j and lst[j] >= pivot:
                j -= 1
            if i < j:
                lst[i] = lst[j]
                i += 1
            while i < j and lst[i] < pivot:
                i += 1
            if i < j:
                lst[j] = lst[i]
                j -= 1
        lst[i] = pivot
        left = quick_sort(lst[:i])
        right = quick_sort(lst[i+1:])
        return left + [pivot] + right

示例说明

以下两个示例，说明如何使用快速排序进行排序。

示例1

使用快速排序对一个列表进行排序。

lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
sorted_lst = quick_sort(lst)
print(sorted_lst)

上述代码中，定义了一个列表lst，并使用quick_sort函数对其进行排序。

示例2

使用快速排序对一个文件中的数字进行排序。

with open("example.txt", "r") as f:
    lst = [int(x) for x in f.readlines()]
sorted_lst = quick_sort(lst)
with open("sorted_example.txt", "w") as f:
    for num in sorted_lst:
        f.write(str(num) + "\n")

上述代码中，读取了一个名为example.txt的文件，其中包含一些数字，将这些数字读入一个列表lst中，并使用quick_sort函数对其进行排序。最后，将排序后的结果写入一个名为sorted_example.txt的文件中。

Tags: ,