快速排序

快速排序(英语:Quicksort),又称划分交换排序(partition-exchange sort),通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。步骤为:从数列中挑出一个元素,称为"基准"(pivot),重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会结束,因为在6. 每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。快速排序的分析

image.pngdef quick_sort(alist, start, end): """快速排序""" # 递归的退出条件 if start >= end: return # 设定起始元素为要寻找位置的基准元素 mid = alist[start] # low为序列左边的由左向右移动的游标 low = start # high为序列右边的由右向左移动的游标 high = end while low < high: # 如果low与high未重合,high指向的元素不比基准元素小,则high向左移动 while low < high and alist[high] >= mid: high -= 1 # 将high指向的元素放到low的位置上 alist[low] = alist[high] # 如果low与high未重合,low指向的元素比基准元素小,则low向右移动 while low < high and alist[low] < mid: low += 1 # 将low指向的元素放到high的位置上 alist[high] = alist[low] # 退出循环后,low与high重合,此时所指位置为基准元素的正确位置 # 将基准元素放到该位置 alist[low] = mid # 对基准元素左边的子序列进行快速排序 quick_sort(alist, start, low-1) # 对基准元素右边的子序列进行快速排序 quick_sort(alist, low+1, end)alist = [54,26,93,17,77,31,44,55,20]quick_sort(alist,0,len(alist)-1)print(alist)时间复杂度最优时间复杂度:O(nlogn)最坏时间复杂度:O(n2)稳定性:不稳定从一开始快速排序平均需要花费O(n log n)时间的描述并不明显。但是不难观察到的是分区运算,数组的元素都会在每次循环中走访过一次,使用O(n)的时间。在使用结合(concatenation)的版本中,这项运算也是O(n)。在最好的情况,每次我们运行一次分区,我们会把一个数列分为两个几近相等的片段。这个意思就是每次递归调用处理一半大小的数列。因此,在到达大小为一的数列前,我们只要作log n次嵌套的调用。这个意思就是调用树的深度是O(log n)。但是在同一层次结构的两个程序调用中,不会处理到原来数列的相同部分;因此,程序调用的每一层次结构总共全部仅需要O(n)的时间(每个调用有某些共同的额外耗费,但是因为在每一层次结构仅仅只有O(n)个调用,这些被归纳在O(n)系数中)。结果是这个算法仅需使用O(n log n)时间。快速排序演示image.png

(0)

相关推荐

  • 递归时间复杂度分析——master公式

    [牛客左神的算法课笔记] 若递归可以写成如下形式: T ( n ) = a T ( n b ) O ( n d ) T(n) = aT(\frac{n}{b}) O(n^d) T(n)=aT(bn​) ...

  • VBA常用小代码:对工作表按名称快速排序

    比如说,有一个工作薄,有十几张工作表,现在要重新设置工作表排放顺序,能不能快速处理哩? 当然是可以的. 为了方便大家理解和灵活使用VBA小代码,我们同03期一样,依然采用多步走的方式. 第1步,将工作 ...

  • Go 数据结构和算法篇(八):快速排序

    今天 以下文章来源于xueyuanjun ,作者xueyuanjun xueyuanjun学院君的订阅号,我会在这里持续更新优质全栈编程技术教程,包括但不限于 Golang.PHP.JavaScrip ...

  • 图解快速排序

    快速排序是冒泡排序的改进版,也是最好的一种内排序,在很多面试题中都会出现,也是作为程序员必须掌握的一种排序方法. 思想:1.在待排序的元素任取一个元素作为基准(通常选第一个元素,但最的选择方法是从待排 ...

  • Excel 快速排序

    表白:黑白圣堂血天使,天剑鬼刀阿修罗. 讲解对象:/Excel 快速排序 作者:融水公子 rsgz Excel教程 Excel教程 http://www.rsgz.top/post/121.html ...

  • excel快速排序技巧,如何使用SORTBY函数对数据进行排序

    SORTBY 函数基于相应范围或数组中的值对范围或数组的内容进行排序. 在此示例中,我们按照人员年龄对人员姓名列表进行升序排列.  ---------------------------------- ...

  • python sortedcontainers-Python实现的快速排序算法集合

    介绍 Sorted Containers是Apache2许可的Sorted Collections库,用纯Python编写,并且可以像C扩展一样快速. Python的标准库已经非常实用了,实践已经证明 ...

  • Office 365函数新世界:快速排序

    打个响指,提一个问题. 以下图所示的数据为例,A:D是数据源,是一份成绩表,现在需要按语文成绩降序排列,结果如F:G列所示. 你会怎么写函数公式呢? 常规的解法套路是这样的▼ F2单元格输入数组公式▼ ...

  • 前端笔试题——手撕快速排序(保姆级手撕)

    引言: 许多互联网公司在招聘前端开发人才时,不仅考察面试者对于前端知识的掌握程度,数据结构与算法也渐渐成为了默许的要求. 除了考察链表.二叉树.图等数据结构以外,在算法中最具有代表性的就是" ...

  • C语言数据结构和算法快速排序法

    https://m.toutiao.com/is/JHSWhce/ 一.设计思想 对一组无序的数组进行排序的时候,选其中一个数组元素(一般为中间元素)作为参照,把比它小的元素放到它的左边,比它大的元素 ...