侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

快速排序

kaixindeken
2021-04-19 / 0 评论 / 0 点赞 / 88 阅读 / 1,422 字

实现原理

归并排序算法虽好,但是不是原地排序算法,需要消耗额外的内存空间,今天我们要介绍的是常规排序里综合排名最高的排序算法:快速排序,江湖人称「快排」。

快排的核心思想是这样的:

如果要排序数组中下标从 p 到 r 之间的一组数据,我们选择 p 到 r 之间的任意一个数据作为 pivot(分区点)。

我们遍历 p 到 r 之间的数据,将小于 pivot 的放到左边,将大于 pivot 的放到右边,将 pivot 放到中间。经过这一步骤之后,数组 p 到 r 之间的数据就被分成了三个部分,前面 p 到 q-1 之间都是小于 pivot 的,中间是 pivot,后面的 q+1 到 r 之间是大于 pivot 的。

图示如下:

1.png

根据分治、递归的处理思想,我们可以用递归排序下标从 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 小,[i+1...j] 之间的数据都比 pivot 大,我们以递归的方式处理该流程,最终整个数组都会变成有序的,对应的算法操作流程如下:

1.png

示例代码

void quickSort(int a[], int low, int high) {
  if (low < high) {
    int m = partition(a, low, high); // O(N)
    // a[low..high] ~> a[low..m–1], pivot, a[m+1..high]
    quickSort(a, low, m-1); // recursively sort left subarray
    // a[m] = pivot is already sorted after partition
    quickSort(a, m+1, high); // then sort right subarray
  }
}

性能分析

快速排序是原地排序算法,时间复杂度和归并排序一样,也是 O(nlogn),这个时间复杂度数据量越大,越优于 O(n2),但是快速排序也有其缺点,因为涉及到数据的交换,有可能破坏原来相等元素的位置排序,所以是不稳定的排序算法,尽管如此,凭借其良好的时间复杂度表现和空间复杂度的优势,快速排序在工程实践中应用较多。

0

评论区