概要
-IDE：Pycharm
-Python版本：python3.x
-算法分类：内部排序->交换类排序->快速排序
算法思想
待排序记录序列中选取一个记录为枢轴，其关键字为$k_1$，然后将其余关键字小于$k_1$的移到前面，大于$k_1$的移到后面，结果是待排序记录分为两个子表，最后将关键字$k_1$插到中间处。这个过程称为一趟快速排序。对分割后的序列，按上述规则继续划分直到所有子表长度不大于$1$，此时待排序记录成为一个有序表。
算法分析
分析快速排序的时间耗费，共需要进行多少趟排序，取决于递归深度。
1.快速排序的最好情况是每一趟排序都将序列一分为二，正好在表中间，将表分为大小相等的子表，类似于折半查找，其时间复杂度约为$O(nlog_{2^n})$
2.快速排序的最坏情况是已经排好序，第一趟经过$n-1$次比较，第一个记录停在原地，产生的左边的列表长度为$0$，右边的列表长度为$n-1$,这样下来比较的次数为$sum_{i=1}^{n-1}(n-i)=(n-1)+(n-2)+...+1=frac{n(n-1)}{2}approx frac{n^2}{2}$
快速排序所需的时间平均值为$T_{avg}(n)=Knlog_{2^n}$，其中K为某个常数。
3.快速排序递归算法的执行过程对应一颗而叉树，理想状态下是一颗完全二叉树，递归工作站的大小，与此二叉树的深度对应，平均情况下空间复杂度为$O(log_{2^n})$。
稳定性与时间复杂度
| 排序算法 | 稳定性 | 时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 |
|---|---|---|---|---|---|
| 快速排序 | 不稳定 | $O(nlog_{2^n})$ | $O(nlog_{2^n})$ | $O(n^2)$ | $O(log_{2^n})$ |
Python代码清单
# !/usr/bin/python3
# _*_ coding:utf-8 _*_
# 快速排序
import sys, random, time # 导入包
def make_numbers(number, maxNumber): # 用于生成列表的算法。
listA = []
for i in range(number):
listA.append(random.randint(0, maxNumber))
print(listA)
return listA # 返回列表
def quick_sort(listA, low, high): # 进行快速排序的算法。
global pos # 设置全局变量，因为我这里是把一次排序的算法写到另一个方法里的。
if low < high: # 判断是否相交。
pos = quick_pass(listA, low, high) # 一次排序。
quick_sort(listA, low, pos-1) # 左子树。递归调用。
quick_sort(listA, pos+1, high) # 右子数。
return listA # 返回排好的list
def quick_pass(listA, low, high): # 一次快速排序算法。
pivot = listA[low] # 记录低点的值
while low < high: # 判断是否相交
while low < high and listA[high] >= pivot: # 在没有相交的情况下，从右向左寻找大于低点的值的数。
high = high-1 # 高位减一。向前走一位。
if low < high: # 如果高低位没有相交，
listA[low] = listA[high] # 没啥意思。就是给个值。
low = low + 1 # 低位向前1位。
while low < high and listA[low] < pivot: # 同理，寻找小于低点的值。
low = low + 1
if low < high:
listA[high] = listA[low]
high = high - 1
listA[low] = pivot # 最后，将低点的值放到low点，或者high点。（此地low = high）
return low
if __name__ == '__main__':
helpInfo = '''
This program is for Quick Sort.
How to use it! Follow the example!
python Quick_Sort.py 10 100
The 10 representative will generate ten numbers.
100 representative the max-number you make.
'''
command = sys.argv[0:] # 从键盘获取输入。
if len(command) != 3 or 'help' in command: # 对输入的参数进行检查。
print(helpInfo) # 打印帮助文本
else:
try: # 尝试将输入测参数转化为int型。
number = int(command[1])
maxNumber = int(command[2])
except ValueError: # 转化失败，出现ValueError
print(helpInfo) # 打印帮助文本。
sys.exit(1) # 异常退出
listA = make_numbers(number, maxNumber) # 一切正常， 生成列表listA。
timeStart = time.time() # 记录开始时间
list = quick_sort(listA, 0, number-1) # 接收返回的排序好的list
timeEnd = time.time() # 记录结束时间。
timeIs = timeEnd - timeStart # 记录消耗时间。
print('排序%d个数花费的时间是%f' % (number, timeIs)) # 输出消息信息。
print(list)
有什么问题请联系我
QQ：3116316431 (请附上信息）
E-mail：wongyinlong@yeah.net