小小千想和您聊一聊

当前位置: 首页> 技术分享> Python实现快速排序算法

Python实现快速排序算法


Python实现快速排序算法

快速排序算法是一种基于交换的高效的排序算法,由C.R.A.Hoare于1962年提出,是一种划分交换排序。它采用了一种分治的策略,通常称其为分治法(Divide and conquer algorithm)。

分治法的基本思想

将原问题分解为若干个规模更小但结构与原问题相似的子问题。递归地解这些子问题,然后将这些子问题的解组合为原问题的解。

快速排序的基本思想

  • 先找到一个基准点(一般指数组的中部),然后数组被该基准点分为两部分,依次与该基准点数据比较,如果比它小,放左边;反之,放右边。
  • 左右分别用一个空数组去存储比较后的数据。
  • 最后递归执行上述操作,直到数组长度 <= 1;

动画

(请在发表文章时插入 qs.webp 这张图片)

代码实现

```python def quick_sort(lists, left, right): '''快速排序''' # 跳出递归判断 if left >= right: return lists

# 选择参考点,该调整范围的第1个值
key = lists[left]
low = left  
high = right

# 循环判断直到遍历全部
while left < right:
    # 从右边开始查找大于参考点的值
    while left < right and lists[right] >= key:
        right -= 1
    lists[left] = lists[right]  # 这个位置的值先挪到左边

    # 从左边开始查找小于参考点的值
    while left < right and lists[left] <= key:
        left += 1
    lists[right] = lists[left]  # 这个位置的值挪到右边

# 写回改成的值
lists[left] = key

# 递归,并返回结果
quick_sort(lists, low, left - 1)    # 递归左边部分
quick_sort(lists, left + 1, high)   # 递归右边部分
return lists

numbers = [4, 0, 7, 9, 2, 8, 1, 3, 6, 5] quick_sort(numbers,0,len(numbers)-1) assert numbers == [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] ```



上一篇:HTML5工具初识之网页编辑器

下一篇:Python实现归并排序算法

QQ技术交流群

千锋Python官方①群
790693323

加入群聊