type
status
date
slug
summary
tags
category
icon
password
整理定义
中文名称:快速排序
英文名称:quicksort
出处 | 定义 |
一种排序算法。任选一个元素作为主元(pivot),把其余元素与主元比较后分成大小两个部分,再对每个部分继续如法炮制,直到全部元素排好序为止。又称分区交换排序。 | |
快速排序是一种高效且通用的分治排序算法。
Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959[1] and published in 1961.[2] It is still a commonly used algorithm for sorting. Overall, it is slightly faster than merge sort and heapsort for randomized data, particularly on larger distributions.[3]
Quicksort is a divide-and-conquer algorithm. It works by selecting a 'pivot' element from the array and partitioning the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. For this reason, it is sometimes called partition-exchange sort.[4] The sub-arrays are then sorted recursively. This can be done in-place, requiring small additional amounts of memory to perform the sorting.
Quicksort is a comparison sort, meaning that it can sort items of any type for which a "less-than" relation (formally, a total order) is defined. Most implementations of quicksort are not stable, meaning that the relative order of equal sort items is not preserved.
【快速排序是一种高效的通用排序算法。 快速排序由英国计算机科学家 Tony Hoare 于 1959 年开发,并于 1961 年发表。它仍然是一种常用的排序算法。 总的来说,对于随机数据,它比合并排序和堆排序稍快,特别是在较大的分布上。
快速排序是一种分而治之的算法。 它的工作原理是从数组中选择一个“枢轴”元素,并根据其他元素是小于还是大于枢轴将其他元素划分为两个子数组。 因此,有时称为分区交换排序。然后对子数组进行递归排序。 这可以就地完成,需要少量的额外内存来执行排序。
快速排序是一种比较排序,这意味着它可以对定义了“小于”关系(正式称为全序)的任何类型的项目进行排序。 大多数快速排序的实现都不稳定,这意味着相同排序项的相对顺序不会保留。】 | |
快速排序(Quicksort),计算机科学词汇,适用领域Pascal,C++等语言,是对冒泡排序算法的一种改进。快速排序采用的是分治思想,即在一个无序的序列中选取一个任意的基准元素pivot,利用pivot将待排序的序列分成两部分,前面部分元素均小于或等于基准元素,后面部分均大于或等于基准元素,然后采用递归的方法分别对前后两部分重复上述操作,直到将无序序列排列成有序序列。 |
复述展开
快速排序 (Quick Sort)
快速排序用到了分治思想,同样的还有归并排序。乍看起来快速排序和归并排序非常相似,都是将问题变小,先排序子串,最后合并。
不同的是快速排序在划分子问题的时候经过多一步处理,将划分的两组数据划分为一大一小,这样在最后合并的时候就不必像归并排序那样再进行比较。但也正因为如此,划分的不定性使得快速排序的时间复杂度并不稳定。
快速排序的基本思想:
通过一趟排序将待排序列分隔成独立的两部分,其中一部分记录的元素均比另一部分的元素小,则可分别对这两部分子序列继续进行排序,以达到整个序列有序。
算法步骤
快速排序使用分治法(Divide and conquer)策略来把一个序列分为较小和较大的 2 个子序列,然后递回地排序两个子序列。具体算法描述如下:
- 从序列中随机挑出一个元素,做为 “基准”(pivot);
- 重新排列序列,将所有比基准值小的元素摆放在基准前面,所有比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个操作结束之后,该基准就处于数列的中间位置。这个称为分区(partition)操作;
- 递归地把小于基准值元素的子序列和大于基准值元素的子序列进行快速排序。
算法分析
- 稳定性 :不稳定
- 时间复杂度 :最佳:O(nlogn), 最差:O(nlogn),平均:O(nlogn)
- 空间复杂度 :O(nlogn)
代码
理解体会
1、快速排序的最差情况分析,时间复杂度应该是O(n^2)。【此时作为基准的选择基本上都是选择左侧或者右侧第一位】
![notion image](https://www.notion.so/image/https%3A%2F%2Fprod-files-secure.s3.us-west-2.amazonaws.com%2Fdea38628-64dc-40fd-8d17-2efa87e3d554%2Fb581d7ad-e4a0-4283-9910-78956e52f4dd%2F%25E5%25BF%25AB%25E9%2580%259F%25E6%258E%2592%25E5%25BA%258F_%25E5%258E%258B%25E7%25BC%25A9.gif?table=block&id=1e3ecf82-c345-4e21-87e9-470102425349&t=1e3ecf82-c345-4e21-87e9-470102425349&width=419&cache=v2)
最差情况下,逆序情况,每次选择基准都是将两部分分为0,N,导致最终的时间复杂度退化到O(n^2)
对于上述的情况,可以通过随机选择基准来避免上述的情况。
所以,在上面,使用策略之后,最坏的情况也能达到 O(nlogn)
快速跳转链接
【概念解析】启动
【概念解析】Day 1 - 10
【概念解析】Day 11 - 20
【概念解析】Day 21 - 30
【概念解析】Day 31 - 40
【概念解析】Day 41 - 50
【概念解析】Day 51 - 60
【概念解析】Day 61 - 70
【概念解析】Day 71 - 80
【概念解析】Day 81 - 90
- 作者:eachenkuang
- 链接:https://kuangyichen.com/article/industry-day17
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。