用Python排序,用python实现快速排序算法

　　作为我们在数据结构面试中经常看到的算法，快速排序对于我们理解和掌握它非常重要。在这里，我将使用一个简单的步骤描述图和代码描述来带您快速浏览。

　　快速排序（英语：Quicksort），又称划分交换排序（partition-exchange sort）。

　　要排序的数据通过一次排序分成两个独立的部分，一部分的所有数据小于另一部分的所有数据。然后用这种方法对两部分数据进行快速排序，整个排序过程可以递归进行，使整个数据成为有序序列。

　　步骤为：

　　1，从序列中挑选出一个元素，叫做‘pivot’，

　　2.对序列重新排序，所有小于基准值的元素放在基准前面，所有大于基准值的元素放在基准后面(同一个数可以在两边)。在这个分区结束后，基准位于系列的中间。这称为分区操作。

　　3.递归排序小于参考值的元素子系列和大于参考值的元素子系列。

　　随机输入

　　defquick_sort(列表，开始，结束):

　　ifstartend:

　　#如果前一个值大于后一个值，排序停止，低位指针和高位指针重合。

　　低=开始

　　高=结束

　　middle=list[start]

　　#中间是我们一开始设定的基准值，低和高表示指针的位置。

　　whilelowhigh:

　　while whighandalist[high]=middle :

　　高=1

　　列表[低]

　　while whighandalist[low]=middle :

　　低=1

　　列表[高]

　　#退出循环时，证明低位指针指向的数据大于基准中位，所以将大于中位的数与高位交换。

　　列表[低]=中间

　　#推出循环后，低和高的位置重合，这个重合的位置就是中间元素应该在的位置。这时中间放在这里，一个大循环结束。

　　quick_sort(列表，开始，低位-1)

　　quick_sort(列表，低位1，结束)

　　list1=[]

　　#通过生成随机数来验证我们的排序算法。

　　(30):

　　list1.append(random.randint(1，300))

　　quick_sort(list1，0，len(list1)-1)

　　打印(列表1)时间复杂度

　　最优时间复杂度：O(nlogn)

　　最坏时间复杂度：O(n2)

　　稳定性：不稳定

　　从一开始就快速排序平均需要O(n log n)时间并不明显。但是观察分区操作并不难。数组的元素将在每个循环中遍历一次，使用的时间为O(n)。在使用组合的版本中，这个操作也是O(n)。

　　在最好的情况下，每次运行分区时，我们都会将一个系列分成两个几乎相等的部分。

　　这意味着每个递归调用处理一半大小的序列。

　　因此，在到达大小为1的序列之前，我们只需要进行log n个嵌套调用。

　　这意味着调用树的深度是O(log n)。

　　但是，在两个相同层次结构的程序调用中，原始序列的相同部分不会被处理；所以每个层次的程序调用总共只需要O(n)次(每个调用都有一些共同的开销，但是因为每个层次只有O(n)次调用，所以这些都汇总在O(n)系数中)。

　　结果是该算法只需要O(n log n)时间。

　　更多Python知识，请关注Python视频教程！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。