这个算法系列主要是自己学习算法过程中动手实践一下，写这个文章作为笔记和分享个人心得，如有错误请各位提出。
注：转载请说明出处
问题提出：
将以下数据升序排列：5, 2, 8, 6, 4, 9, 7, 3, 1
快速排序的原理：
快速排序的核心思想是(如下图)
1.先确定一个基准数，让后按照比较规则，如本例是升序排列，则将比基数大的放到右边，比基数小的放到左边。
2.接下来各边重复步骤1，直到全部排序完毕。
程序设计的思路就是(以上面的问题为例)
左右分别遍历比较
#非程序代码，只用来讲解 a = [5,2,8,6,4,9,7,3,1] #数据
temp #用于保存基数
left #左起点
right #右起点
i #左游标
j #右游标
1.将第一个数作为基数，temp=a[left], 初始化两个游标 i=left;j=right,（当left大于right时，分类结束）。
2.先由右边 j 开始遍历(必须要先从右边开始遍历，想想为什么，后面会解答)，当遇到比基数小的停下；
然后左边 i 开始遍历，当遇到比基数大的数停下，当i<j时，交换i和j所在的数a[i], a[j] = a[j],a[i],
交换完成后，继续遍历直到 i 和 j 相遇。
3.当i 和 j 相遇，说明一次分类完成，注意此时要将基数和 i，j 相遇时所在的数交换。a[left], a[i]=a[i], a[left]
4.先处理基数左边的数字，设置左起点为left=left,右起点为right=i-1， 重复1到5步。
5.当左边的数字处理完成，再处理右边数字，设置左起点为了left=i+1, 右起点为right=right，重复1到5步。
接下来为python程序源码:（可以到github上下载https://github.com/DIGCreat/pythonAndAlgorithms.git）
#!/usr/bin/env python
# -*- coding:utf8 -*-
'''
简介:本程序主要是用python实现快速排序，程序的功能是实现
升序排列。
本程序在数据量大的情况下，需要注意递归深度的问题。 作者:King 日期:2016/08/01 版本1
''' class QuickSort(object):
'''
self.datas: 要排序的数据列表
_sort(): 排序函数
show(): 输出结果函数 用法：
QuickSort(datas) 实例化一个排序对象 QuickSort(datas)._sort(left, right)
开始排序，由于排序直接操作
self.datas, 所以排序结果也
保存在self.datas中, left为
排序的开始位置，right为排
序的结束位置。因此可以实现
局部排序 QuickSort(datas).show() 输出结果
'''
def __init__(self, datas):
self.datas = datas def _sort(self, left, right):
# 排序函数，由两个游标分别从两端开始遍历
# 左端数据要比基数小，所以判断条件是遇到
# 比基数大的就要停下。
# 右端的情况与左端相反。
#
# 注意：程序一定要先从右端开始遍历，因为
# 两端遍历最终停下的条件肯定是相遇
# 的时候，如果左端先移动，则最后停
# 下时的数值肯定比基数大，若将这个
# 数字与基数交换，则基数左边的数字
# 就不是全部比基数小了，程序运行就
# 不正确了。
if(left > right):
return
temp = self.datas[left]
i = left
j = right
while i != j:
while(self.datas[j] >= temp and i < j):
j -= 1 while(self.datas[i] <= temp and i < j):
i += 1 if i < j:
self.datas[i], self.datas[j] = \
self.datas[j], self.datas[i] self.datas[left], self.datas[i] = self.datas[i], temp self._sort(left, i-1)
self._sort(i+1, right) def show(self):
print 'Result is:',
for i in self.datas:
print i, print '' if __name__ == '__main__':
try:
datas = raw_input('Please input some number:')
datas = datas.split()
datas = [int(datas[i]) for i in range(len(datas))]
except Exception:
pass qs = QuickSort(datas)
qs._sort(0, len(datas)-1)
qs.show()
最后有兴趣的同学可以关注我的微信公众号，可以随时及时方便看我的文章。*^_^*
扫码关注或者搜索微信号：King_diary