排序算法之快速排序

1、简单介绍

快速排序核心思想是给中间值元素找到一个正确位置，使得左边元素小于该值，右边元素均大于该元素。

具体实现如下：快速排序有两个指针，一个指向最大值，一个指向最小值，分别向左、向右移动。两个指针相遇的位置即为元素所在正确索引。移动过程中的一个原则是左边元素均小于该中间值，右边元素均大于该中间值。移动的时候要判断指向的元素与中间值的大小，若满足规则，则指针移动，否则停止移动，通过交换最大值和最小值指向元素的值继续移动。中间值元素为一个分界线，索引左边的元素小于该元素，索引右边的元素大于该元素。然后将待排序的序列从该元素分成两个子序列，按照上面的思想继续执行[递归]。

代码实现中需要解决的问题

移动原则：最小值指针指向元素小于中间值元素，最大值指向的元素大于中间值元素。

当两个指针都停止移动的时候交换

1、刚开始移动的是第一个元素：最小值指针指向的是中间值，我们将中间值抽出来，则现在最小值指向元素为空，所以不能移动最小值指针，所以先移动最大值指针

2、若最大值大于中间值那么指针一直移动

3、若最大值小于或者等于中间值，我们这里采取的策略是让所有的与中间值相等的元素都放到左边，所以这个时候是停止移动

4、交换最大值指针和最小值指针对应元素

5、由于最大值指针对应元素为空，此时可以移动最小值指针

6、若最小值小于或者等于中间值那么指针一直移动

7、当最小值大于中间值元素的时候停止移动交换

8、交换后最大值指针对应元素大于中间值元素，最小值指针指向是空

9、此时要跳到步骤2继续执行，我们使用循环

10、考虑一下最大值指针的最小值指针相遇的情况，也就是最大值指针和最小值指针差1

此时有3种情况

情况1：

最大值指针指向元素大于最小值指针指向元素，移动最大值指针：移动后max_value=min_value，此时应该直接退出循环；最大值指针指向元素大于最小值指针指向元素，移动最小值指针：移动后max_value=min_value，此时应该直接退出循环，所以移动过程中指针加减1的判断条件要加max_value > min_value。

情况2：

最大值指针指向元素小于最小值指针指向元素，此时交换元素，交换后移动调到情况1

情况3：

最大值指针指向元素等于最小值指针指向元素，此时若最大值指针移动，让移动停止。让最小值元素指针移动

快排图1 快排图2 测试

时间复杂度：

最优时间复杂度：中间值每次把序列拆分成两半

代码中是递归调用：每次调用函数的话执行的主要步骤是移动最大值、最小值指针，最大值和最小值指针相遇的时候停止。序列长度是N，即代码执行N次。

递归调用的深度是多少呢，即进行几次函数调用。每次执行将序列分成两部分，所以调用次数是N的对数。

最坏时间复杂度：中间值每次只能拆分出一个元素