比较排序算法中的快速排序是一种高效的排序算法，在这种情况下具有O(n log n)的时间复杂度

文章目录

• • • • 快速排序
  • • • 实现方式
      • 性能分析

快速排序

改写说明

依次处理位于p至r范围内的数据元素。具体操作包括：将所有数值小于pivot的元素放置在左侧；将所有数值大于pivot的元素放置在右侧；并将pivot置于中间位置。经过这一操作后，在p至r区间内已经划分出三个子区域：左侧区域包含所有小于pivot的元素；中间位置存放的是pivot；右侧区域则包含所有大于pivot的元素。然后按照分治法与递归策略对左半部分（从p到q-1）和右半部分（从q+1到r）分别进行同样的排序操作。当区间缩减至仅一个数据时，则表示该过程完成并达到了完全有序的状态。

    用递推公式将上面的过程写出来：
    
    递推公式：
    quickSort(p…r) = quickSort(p…q-1) + quickSort(q+1, r)
    终止条件：
    p >= r

实现方式

方法1: horea 法：

p向右扫描寻找大于基准值的元素，并在发现第一