Python实现快速排序的方法详解

向北走

发布时间：2026-10-14 | 3人浏览过

原创

本文详细介绍Python中快速排序算法的实现原理与代码编写。通过设定参考值K，利用双指针left和right从两端向中间扫描并交换元素，完成单次分区。随后对左右子序列递归执行相同操作，直至排序完成。文章包含完整代码示例及运行结果，并推荐了在线算法演示工具供学习参考。

快速排序原理概述

本文通过具体实例，详细解析了如何使用Python语言实现快速排序算法。内容旨在帮助读者理解其核心逻辑并提供可参考的代码实现。

在探讨快速排序的Python实现之前，首先需要明确其基本思路。

1、选取一个基准值（参考值）置于列表中间位置。经过初次排序处理后，确保该基准值左侧的所有元素均小于它，而右侧的所有元素均大于它。

2、分别对基准值左侧和右侧的子序列，递归地执行上述第1步的操作，直至整个列表有序。

算法实现思路

具体实现逻辑如下：

设置两个指针left和right，分别指向列表的起始元素（索引0）和末尾元素。选取参考值K，默认取列表的第一个元素list[0]。
首先比较left指向的值与参考值K。若list[left]小于或等于K，则left指针向右移动（left+1），直到找到大于K值的元素位置并停止。
接着比较right指向的值与参考值K。若list[right]大于K，则right指针向左移动（right-1），直到找到小于K值的元素位置并停止。
当left和right指针尚未相遇（即left仍小于right）时，交换这两个指针所指向的值。
若指针已经相遇，则表明第一次分区排序已完成。此时将list[right]的值与初始参考值list[0]进行互换，随后对分割后的左右两部分分别进行递归排序。

Python代码实现

以下是具体的编程实现代码。


#快排的主函数，传入参数为一个列表，左右两端的下标
def QuickSort(list,low,high):
  if high > low:
    #传入参数，通过Partitions函数，获取k下标值
    k = Partitions(list,low,high)
    #递归排序列表k下标左侧的列表
    QuickSort(list,low,k-1)
    # 递归排序列表k下标右侧的列表
    QuickSort(list,k+1,high)
def Partitions(list,low,high):
  left = low
  right = high
  #将最左侧的值赋值给参考值k
  k = list[low]
  #当left下标，小于right下标的情况下，此时判断二者移动是否相交，若未相交，则一直循环
  while left < right :
    #当left对应的值小于k参考值，就一直向右移动
    while list[left] <= k:
      left += 1
    # 当right对应的值大于k参考值，就一直向左移动
    while list[right] > k:
      right = right - 1
    #若移动完，二者仍未相遇则交换下标对应的值
    if left < right:
      list[left],list[right] = list[right],list[left]
  #若移动完，已经相遇，则交换right对应的值和参考值
  list[low] = list[right]
  list[right] = k
  #返回k值
  return right
list_demo = [6,1,2,7,9,3,4,5,10,8]
print(list_demo)
QuickSort(list_demo,0,9)
print(list_demo)