快速排序使用分治法 (Divide and conquer)策略来把一个串行 (list)分为两个子串行(sub-lists)。
步骤为:
- 从数列中挑出一个元素,称为 "基准"(pivot),
- 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition) 操作。
- 递归 地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。
递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。
(以上摘自 wiki)
python 实现为:
def sub_sort(array,low,high) : 3 key = array[low] 4 while low < high : 5 while low < high and key <= array[high] : 6 high -= 1 7 while low < high and key > array[high] : 8 array[low] = array[high] 9 low += 1 10 array[high] = array[low] 11 array[low] = key 12 return low 13 14 15 16 def quick_sort(array,low,high) : 17 if low < high : 18 key_index = sub_sort(array,low,high) 19 quick_sort(array,low,key_index) 20 quick_sort(array,key_index+1,high) 21 22 23 if __name__ == '__main__': 24 array = [8,10,6,4,5,13,26,18] 25 print array 26 quick_sort(array,0,len(array)-1) 27 print array
相关推荐
python实现快速排序源码python实现快速排序源码python实现快速排序源码python实现快速排序源码python实现快速排序源码python实现快速排序源码python实现快速排序源码python实现快速排序源码python实现快速排序源码
基于python实现的快速排序程序源码基于python实现的快速排序程序源码基于python实现的快速排序程序源码基于python实现的快速排序程序源码基于python实现的快速排序程序源码基于python实现的快速排序程序源码基于...
Python 算法 快速排序.py
快速排序.py python代码实现快速排序.py python代码实现快速排序.py python代码实现快速排序.py python代码实现快速排序.py python代码实现快速排序.py python代码实现快速排序.py python代码实现快速排序.py python...
利用python代码实现数据结构的经典算法——快速排序算法。
一个Python实现的快速排序算法的程序
利用python进行快速排序,代码可以直接用
Python实现快速排序.rar
python编写 快速排序 Quick Sort
python写的快速排序算法,以及与冒泡排序的时间比较.
快速排序等经典排序算法C++、Java、python等版本 快速排序等经典排序算法C++、Java、python等版本 快速排序等经典排序算法C++、Java、python等版本 快速排序等经典排序算法C++、Java、python等版本 快速排序等经典...
基于python的快速排序算法设计与实现
插入排序.py python实现的排序插入排序.py python实现的排序插入排序.py python实现的排序插入排序.py python实现的排序插入排序.py python实现的排序插入排序.py python实现的排序插入排序.py python实现的排序插入...
本文实例讲述了Python实现快速排序的方法。分享给大家供大家参考,具体如下: 说起快排的Python实现,首先谈一下,快速排序的思路: 1、取一个参考值放到列表中间,初次排序后,让左侧的值都比他小,右侧的值,都比...
python常用的几种排序方法,这几个方法涉及到冒泡,快速排序,等等.............
python实现快速排序的几种方法.docx
该程序包含7大排序算法: # sort.bubbleSort() #冒泡排序 ...# sort.quickSort() #快速排序 该排序算法把每次的排序结果都列出来,可供初学者学习。 self.arr存放的是待排序列表,可改成自己的数据
快速排序算法来源于分治法的思想策略,这里我们将来为大家简单解析一下快速排序的算法思想及Python版快速排序的实现示例:
快速排序 非递归实现方式的完整源代码和测试结果。