本文实例讲述了Python实现的数据结构与算法之快速排序。分享给大家供大家参考。具体分析如下：
一、概述
快速排序（quick sort）是一种分治排序算法。该算法首先 选取 一个划分元素（partition element，有时又称为pivot）；接着重排列表将其 划分 为三个部分：left（小于划分元素pivot的部分）、划分元素pivot、right（大于划分元素pivot的部分），此时，划分元素pivot已经在列表的最终位置上；然后分别对left和right两个部分进行 递归排序。
其中，划分元素的 选取 直接影响到快速排序算法的效率，通常选择列表的第一个元素或者中间元素或者最后一个元素作为划分元素，当然也有更复杂的选择方式；划分 过程根据划分元素重排列表，是快速排序算法的关键所在，该过程的原理示意图如下：
<-- 选取划分元素 -->
<-- 划分过程 -->
<-- 划分结果 -->
快速排序算法的优点是：原位排序（只使用很小的辅助栈），平均情况下的时间复杂度为 O(n log n)。快速排序算法的缺点是：它是不稳定的排序算法，最坏情况下的时间复杂度为 O(n2)。
二、Python实现
1、标准实现
#!/usr/bin/env python
# -*- coding: utf-8 -*-
def stdQuicksort(L):
qsort(L, 0, len(L) - 1)
def qsort(L, first, last):
if first < last:
split = partition(L, first, last)
qsort(L, first, split - 1)
qsort(L, split + 1, last)
def partition(L, first, last):
# 选取列表中的第一个元素作为划分元素
pivot = L[first]
leftmark = first + 1
rightmark = last
while True:
while L[leftmark] <= pivot:
# 如果列表中存在与划分元素pivot相等的元素，让它位于left部分
# 以下检测用于划分元素pivot是列表中的最大元素时，
#防止leftmark越界
if leftmark == rightmark:
break
leftmark += 1
while L[rightmark] > pivot:
# 这里不需要检测，划分元素pivot是列表中的最小元素时，
# rightmark会自动停在first处
rightmark -= 1
if leftmark < rightmark:
# 此时，leftmark处的元素大于pivot，
#而rightmark处的元素小于等于pivot，交换二者
L[leftmark], L[rightmark] = L[rightmark], L[leftmark]
else:
break
# 交换first处的划分元素与rightmark处的元素
L[first], L[rightmark] = L[rightmark], L[first]
# 返回划分元素pivot的最终位置
return rightmark
2、Pythonic实现
#!/usr/bin/env python # -*- coding: utf-8 -*- def pycQuicksort(L): if len(L) <= 1: return L return pycQuicksort([x for x in L if x < L[0]]) + [x for x in L if x == L[0]] + pycQuicksort([x for x in L if x > L[0]])
对比 标准实现 可以看出，Pythonic实现 更简洁、更直观、更酷。但需要指出的是，Pythonic实现 使用了Python中的 列表解析 （List Comprehension，也叫列表展开、列表推导），每一次 递归排序 都会产生新的列表，因此失去了快速排序算法本来的 原位排序 的优点。
三、算法测试
#!/usr/bin/env python
# -*- coding: utf-8 -*-
if __name__ == '__main__':
L = [54, 26, 93, 17, 77, 31, 44, 55, 20]
M = L[:]
print('before stdQuicksort: ' + str(L))
stdQuicksort(L)
print('after stdQuicksort: ' + str(L))
print('before pycQuicksort: ' + str(M))
print('after pycQuicksort: ' + str(pycQuicksort(M)))
运行结果：
$ python testquicksort.py before stdQuicksort: [54, 26, 93, 17, 77, 31, 44, 55, 20] after stdQuicksort: [17, 20, 26, 31, 44, 54, 55, 77, 93] before pycQuicksort: [54, 26, 93, 17, 77, 31, 44, 55, 20] after pycQuicksort: [17, 20, 26, 31, 44, 54, 55, 77, 93]
希望本文所述对大家的Python程序设计有所帮助。
3月27日消息，苹果宣布2024年全球开发者大会（WWDC）将于6月10日至6月14日举行，巧合的是，这次大会与端午假期重合。
苹果官方表示：
在线参加 Apple 每年规模最大的开发者盛会。亲眼见证 Apple 最新平台、技术和工具的发布。了解如何创建和改进你的 App 和游戏。与 Apple 设计师和工程师互动交流，与全球开发者社区建立联系。以上活动均免费在线举行。
探索各种新的工具、框架和功能，助力你打造出理想的 App 和游戏。通过视频讲座学习新技能，与 Apple 专家进行一对一会面，以推进你的项目，完善你的构思。
Swift Student Challenge 旨在支持和鼓舞下一代开发者、创作者和企业家。太平洋时间 3 月 28 日，我们将公布今年的获奖者名单。获奖者将有资格参加在 Apple Park 举办的特别活动。我们还会选出 50 名杰出获胜者，他们将受邀前往库比提诺，获得为期三天的非凡体验，包括参加 Apple Park 的特别活动。
RTX 5090要首发 性能要翻倍！三星展示GDDR7显存
三星在GTC上展示了专为下一代游戏GPU设计的GDDR7内存。
首次推出的GDDR7内存模块密度为16GB，每个模块容量为2GB。其速度预设为32 Gbps（PAM3），但也可以降至28 Gbps，以提高产量和初始阶段的整体性能和成本效益。
据三星表示，GDDR7内存的能效将提高20%，同时工作电压仅为1.1V，低于标准的1.2V。通过采用更新的封装材料和优化的电路设计，使得在高速运行时的发热量降低，GDDR7的热阻比GDDR6降低了70%。