如何高效实现快速排序算法？

本文共计486个文字，预计阅读时间需要2分钟。

快速排序是一种经典的排序算法，其排序速度非常快！平均时间复杂度可达到O(nlogn)。

排序过程：

1.首先选择数组中的一个数字A作为基准。

2.遍历数组，将比A小的数移到左侧，比A大的数移到右侧。

快速排序

快速排序是一种经典的排序算法，和它的名字一样，它的排序速度非常快！平均时间复杂度可以达到O(nlogn)。

排序过程

1. 首先选择数组中的一个数字A
2. 遍历数组，将比A小的数移动到A的左边，将比A大的数移动到A的右边，完成后数组被分成左右两个区域，左边全部比A小，右边全部比A大
3. 对元素数量大于1的区域，执行1、2、3三个操作

大致过程如下图：

快速排序的过程，虽然不难理解，但是这里也存在几个问题：

1. 数字A该如何选择？数字A的选择其实是一件非常重的事情，数字A选的好可以使算法的时间复杂度更接近平均时间复杂度O(nlogn)，其中缘由我就不赘述了，实际中我们只需要随机选择一个就可以了，随机选择效果已经足够好了，而且很简单。