快速排序算法举例说明_常⽤排序算法之快速排序
前天给⼤家分享了归并排序，但是它不是原地排序算法，需要消耗额外的内存空间，今天给⼤家分享的是江湖⽆⼈不知⽆⼈不晓的"快排"--快速排序。
快排是⼩⽣接触开发学会的第⼀个排序算法
快速排序原理
快排也⽤到了分治思想。快排的核⼼思想是：如果要排序的数组中下标从 p 到 r 之间的⼀组数据，我们选择 p 到 r 之间的任意⼀个数据作为分区点 pivot。
我们遍历p 到 r 之间的数据，将⼩于 pivot 的放到左边，将⼤于 pivot 的放到右边，将 pivot 放到中间。经过这⼀步之后，数组 p 到 r 之间的数据就被分成了三个部分，前⾯ p 到 q-1 之间都是⼩于 pivot 的，中间是 pivot ，后⾯的 q+1 到 r 之间都是⼤于 pivot 的。
如下图：js合并两个数组
根据分治、递归的处理思想，我们可以⽤递归排序从下标 p 到 q-1 之间的数据和下标从 q+1 到 r 之间的数据，直到区间缩⼩为1，就说明所有的数据都有序了。快排不需要归并那样做合并，也不需要额外的存储空间，在时间复杂度⼀样的情况下有着⽐归并更好的空间复杂度表现。
快排⾸先到分区点，⼀般我们会将数组第⼀个或最后⼀个元素作为 pivot，我们以最后⼀个作为分区点 pivot，然后通过两个变量 i 和 j 作为下标来循环数组，当下标 j 对应数据⼩于 pivot 时，交换 i 和 j 对应数据，并且将 i往前移动⼀位，否则 i 不动，下标 j 始终是往前移动的， j 到达终点后，将 pivot 如
下标 i 对应数据交换，这样最终将 pivot 置于数组中间，[0...i-1]区间的数据都⽐ pivot ⼩，[j] 之间的数据都⽐ pivot ⼤，我们以递归的⽅式循环处理，最终整个数组都会变成有序的，如下图：
因为分区的过程涉及交换操作，如果数组中有两个相同的元素，⽐如序列 7， 9，5，7，3，6 经过第⼀次分区操作之后，两个 7的相对先
后顺序会改变。所以，快速排序并不是⼀个稳定的排序算法。
代码⽰例
Go语⾔：
package mainimport "fmt"func main() {  arr := []int{8, 3, 4, 5, 9, 2, 1}  QuickSort(arr)  fmt.Println(arr)}func QuickSort(arr []int) {  separateSort(arr, 0, len(arr)
PHP⽰例：
function quick_sort($nums){    if (count($nums) <= 1) {        return $nums;    }    quick_sort_c($nums, 0, count($nums) - 1);    return $nums;}function quick_
JS⽰例：
const swap = (arr, i, j) => {    const temp = arr[i]    arr[i] = arr[j]    arr[j] = temp}// 获取 pivot 交换完后的indexconst partition = (arr, pivot, left, right) => {    const pivotV 性能分析
最后我们看下快速排序的性能和稳定性：
1. 时间复杂度：是O(nlogn)，同样要优于冒泡和插⼊排序
2. 空间复杂度：不需要额外的空间存放排序的数据，是原地排序
3. 算法稳定性：涉及数据交换，可能破坏原来相等元素的位置排序，所以是不稳定的排序算法

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。