乐趣区

关于python:排序算法的巅峰之选学习Python快速排序

jiezi

疾速排序（Quick Sort）是一种高效的排序算法，它的根本思维是通过分治的策略将一个大问题分解成小问题并解决。疾速排序的外围操作是选取一个基准元素，将待排序序列划分成左右两局部，其中左局部的元素都小于基准元素，右局部的元素都大于基准元素。而后递归地对左右两局部进行排序，最终实现整个序列的排序。本文将具体介绍疾速排序算法的原理和实现，并提供相干的 Python 代码示例。

一、算法原理

疾速排序算法的步骤如下：

  1. 抉择一个基准元素（通常抉择第一个或最初一个元素）。
  2. 将序列划分成两局部，使得左局部的元素都小于基准元素，右局部的元素都大于基准元素。这个过程称为分区（Partition）。
  3. 对左右两局部递归地利用步骤 1 和步骤 2，直到每个局部只剩下一个元素或为空。

疾速排序的核心思想是通过一直地划分和排序子序列，最终实现整个序列的排序。

二、疾速排序的实现

上面是应用 Python 实现疾速排序算法的代码：


def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]  # 抉择第一个元素作为基准元素
        less = [x for x in arr[1:] if x <= pivot]  # 小于等于基准元素的子序列
        greater = [x for x in arr[1:] if x > pivot]  # 大于基准元素的子序列
        return quick_sort(less) + [pivot] + quick_sort(greater)

# 测试代码
numbers = [4, 2, 6, 1, 3]
sorted_numbers = quick_sort(numbers)
print(sorted_numbers)  # 输入：[1, 2, 3, 4, 6]

在上述代码中，quick_sort() 函数承受一个待排序的列表作为输出，并对列表进行疾速排序。算法应用递归形式实现。首先抉择列表的第一个元素作为基准元素（也能够抉择最初一个元素），而后通过列表解析的形式将列表划分成两局部：小于等于基准元素的子序列和大于基准元素的子序列。最初，将子序列和基准元素合并起来，失去最终的排序后果。

三、算法剖析

疾速排序是一种旧址排序算法，即在排序过程中间接批改原始列表，不须要额定的存储空间。疾速排序的均匀工夫复杂度为 O(nlogn)，其中 n 是待排序序列的长度。在大多数状况下，疾速排序是一种高效的排序算法。然而，在最坏状况下，即待排序序列曾经有序或根本有序时，疾速排序的工夫复杂度为 O(n^2)，性能降落。
为了防止最坏状况的产生，能够采纳一些优化办法，如随机抉择基准元素、三数取中法抉择基准元素、应用插入排序优化小规模数据等。

四、优化思路

优化 1：随机抉择基准元素

为了防止最坏状况的产生，能够随机抉择基准元素。在每次分区时，随机抉择一个元素作为基准元素，而不是固定抉择第一个或最初一个元素。这样能够升高最坏状况产生的概率，进步算法的性能。


import random

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot_index = random.randint(0, len(arr) - 1)  # 随机抉择一个索引作为基准元素的索引
        pivot = arr[pivot_index]
        arr[0], arr[pivot_index] = arr[pivot_index], arr[0]  # 将基准元素替换到第一个地位
        less = [x for x in arr[1:] if x <= pivot]
        greater = [x for x in arr[1:] if x > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

优化 2：三数取中法抉择基准元素

另一种优化办法是应用三数取中法抉择基准元素。这种办法通过从待排序序列的首、尾和两头抉择三个元素，并将它们排序后的两头元素作为基准元素，来升高最坏状况的概率。


def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        first = arr[0]
        last = arr[-1]
        mid = arr[len(arr) // 2]
        pivot = sorted([first, mid, last])[1]  # 抉择三个元素排序后的两头元素作为基准元素
        pivot_index = arr.index(pivot)
        arr[0], arr[pivot_index] = arr[pivot_index], arr[0]
        less = [x for x in arr[1:] if x <= pivot]
        greater = [x for x in arr[1:] if x > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

优化 3：应用插入排序优化小规模数据

对于小规模的数据，疾速排序的性能可能不如插入排序。因而，能够设置一个阈值，当待排序序列的长度小于等于阈值时，应用插入排序来进步算法的性能。


def quick_sort(arr, threshold=10):
    if len(arr) <= threshold:
        return insertion_sort(arr)  # 应用插入排序进行优化
    else:
        # 失常的疾速排序逻辑
        pivot_index = random.randint(0, len(arr) - 1)
        pivot = arr[pivot_index]
        arr[0], arr[pivot_index] = arr[pivot_index], arr[0]
        less = [x for x in arr[1:] if x <= pivot]
        greater = [x for x in arr[1:] if x > pivot]
        return quick_sort(less, threshold) + [pivot] + quick_sort(greater, threshold)

五、总结

本文介绍了疾速排序算法的原理和实现，并提供了相干的 Python 代码示例。疾速排序是一种高效的排序算法，在大多数状况下体现良好。然而，在最坏状况下，其性能可能降落。为了防止最坏状况的产生，能够采纳随机抉择基准元素和三数取中法抉择基准元素的优化办法。另外，对于小规模的数据，能够应用插入排序进行优化。通过把握疾速排序的原理和优化思路，咱们能够更好地了解和利用这一经典的排序算法。
关注我，更多精彩内容立刻出现！

退出移动版