快速排序

思想

1）快排是冒泡的升级，都是交换排序类，它增大了元素比较和交换的距离，将值较大的元素直接从前面换到后面，值比较小的元素直接从后面换到前面，而不是相邻相邻地换，从而减少了比较和交换的次数

2）每一轮排序，先选出一个枢轴，让比枢轴小的元素放在枢轴的左边，比枢轴大的元素放在枢轴的右边，再把序列分成按枢轴前后分成两个子序列，对子序列分别进行下一轮排序；不断重复上述操作，直到再也分不出子序列，排序完成

3）枢轴选取的一般规则：选序列的第一个或最后一个元素当枢轴，将选取的枢轴不断交换，将比它小的换到它的左边，比它大的换到它的右边，它自己也在交换中不断更换自己的位置，直到比枢轴小的元素全部都在枢轴的左边，比枢轴大的元素全部都在枢轴的右边

代码实现

 1 int partiton(vector<int>& nums, int left, int right)
 2 {
 3     int pivotKey = nums[left];//这里选序列的第一个元素当枢轴
 4     while (left < right)//left == right，一个点了就不用选了，枢轴就是它自己
 5     {
 6         while (left < right && nums[right] >= pivotKey)
 7             --right;
 8         swap(nums[left], nums[right]);
 9         while (left < right && nums[left] <= pivotKey)
10             ++left;
11         swap(nums[left], nums[right]);
12     }
13     return left;
14 }
15 
16 void sortQuick(vector<int>& nums, int begin, int last)
17 {
18     if (begin < last)//begin==last，一个点了就不用排序了
19     {
20         int pivot = partiton(nums, begin, last);
21         sortQuick(nums, begin, pivot - 1);
22         sortQuick(nums, pivot + 1, last);
23     }
24 }

举例：

　　第一轮：

时间复杂度

　　最好情况：每次的枢轴划分都很均匀，仅需递归logn次，再考虑比较操作为O(n)，最后能得出复杂度为O(nlogn)

　　最坏情况：待排序序列为正序或者逆序，每次枢轴划分会分出一个空的子序列，用递归树画出来就是一棵斜树，此时需要递归n-1次，此时退化成冒泡排序，再考虑比较操作为O(n)，最后能得出复杂度为O(n²)

　　平均情况：O(nlogn)

空间复杂度

　　因为递归深度的缘故，最好情况O(logn)，最坏情况O(n)，平均情况O(logn)

稳定性

　　快速排序的交换有两个方向，分别从两边向中间靠拢，这样的过程无法保证相同元素排序前后的相对顺序不变，所以是不稳定的。如：序列为5 3 4 3 8 9 10 11，中枢元素5，序列中有相同元素3，5最开始会和第二个3交换，这样第二个3就跑到第一个3地前面去了，稳定性破坏

优化

1.优化枢轴选择规则

　　选取序列的第一个或最后一个元素当枢轴时，如果这个元素恰好是极端元素（最大值或者最小值），会导致做枢轴划分时，分出一个空的子序列，用递归树画出来就是一棵斜树，大大增加了递归次数，所以我们最好选择一个序列中间数作为枢轴

1.1三数取中法

　　取序列左端、中间、右端三个数，将它们进行比较的出中间值，放在左端，再把这个左端数作为枢轴

 1 int partitonThree(vector<int>& nums, int left, int right)
 2 {
 3     int mid = left + (right - left) / 2;
 4     if (nums[left] < nums[mid])//left放left和mid之中更大的那个
 5         swap(nums[left], nums[mid]);
 6     if (nums[left] > nums[right])//left放left和right之中更小的那个
 7     {
 8         swap(nums[left], nums[right]);
 9         if (nums[left] < nums[mid])//left放left和right之中更大的那个
10             swap(nums[left], nums[mid]);
11     }
12 
13     int pivotKey = nums[left];//最后nums[left]为三数取中的中间值
14     while (left < right)
15     {
16         while (left < right && nums[right] >= pivotKey)
17             --right;
18         swap(nums[left], nums[right]);
19         while (left < right && nums[left] <= pivotKey)
20             ++left;
21         swap(nums[left], nums[right]);
22     }
23     return left;
24 }
25 
26 void sortQuick(vector<int>& nums, int begin, int last)
27 {
28     if (begin < last)
29     {
30         int pivot = partitonThree(nums, begin, last);
31         sortQuick(nums, begin, pivot - 1);
32         sortQuick(nums, pivot + 1, last);
33     }
34 }

1.2九数取中法

　　三数取中对小序列来说可以有很大概率选到中间数，但是对于非常大的序列来说，这个概率又变得很小，所以可以采取九数取中法。先从序列中分三次取样，每次取样取三个数，三个样品都得出中间数，再从三个中间数中再得出中数，作为枢轴

2.优化不必要的交换

　　在枢轴划分时，某个元素可能会经过若干次的交换到达目的地，这些交换其实可以不需要，可以用“赋值替换”的操作来替代“交换”，使算法性能提升

 1 int partitonThree(vector<int>& nums, int left, int right)
 2 {
 3     int mid = left + (right - left) / 2;
 4     if (nums[left] < nums[mid])//left放left和mid之中更大的那个
 5         swap(nums[left], nums[mid]);
 6     if (nums[left] > nums[right])//left放left和right之中更小的那个
 7     {
 8         swap(nums[left], nums[right]);
 9         if (nums[left] < nums[mid])//left放left和right之中更大的那个
10             swap(nums[left], nums[mid]);
11     }
12 
13     int pivotKey = nums[left];//最后nums[left]为三数取中的中间那个数
14     while (left < right)//采用赋值替换而不是交换
15     {
16         while (left < right && nums[right] >= pivotKey)
17             --right;
18         nums[left] = nums[right];
19         while (left < right && nums[left] <= pivotKey)
20             ++left;
21         nums[right] = nums[left];
22     }
23     nums[left] = pivotKey;//把覆盖值换回枢轴值
24     return left;
25 }

3.对短序列排序优化

　　如果序列很小，快速排序反而不如简单排序中的直接插入排序性能好，因为快排用到了递归，因此改进快排。加入一个检测，检测序列的长度，如果长度大于这个值则采用快排，否则采用直接插入排序。有资料认为这个MAX_LENGTH值为7比较合适，也有认为50比较合适，可自行调整。

#define MAX_LENGTH 7

void sortInsert(vector<int>& nums)
{
    int length = nums.size();
    for (int i = 1; i <= length-1; ++i)
    {
        int j = i;
        while (j > 0 && nums[j] < nums[j - 1])//已排序序列的最后一个元素是最大的，从已排序序列的最后一个开始往前进行两两比较，最后形成的效果就好像找到了一个合适的位置插入一样
        {
            swap(nums[j], nums[j - 1]);
            --j;
        }
    }
}

void sortQuick(vector<int>& nums, int begin, int last)
{
    if ((last - begin + 1) > MAX_LENGTH)
    {
        if (begin < last)
        {
            int pivot = partitonThree(nums, begin, last);
            sortQuick(nums, begin, pivot - 1);
            sortQuick(nums, pivot + 1, last);
        }
    }
    else
        sortInsert(nums, last - begin + 1);
}

4.优化递归

4.1尾递归优化

　　快排在尾部有两次递归，可保留一次递归，对尾递归优化

 1 void sortQuick(vector<int>& nums, int begin, int last)
 2 {
 3     if ((last - begin + 1) > MAX_LENGTH)
 4     {
 5         while (begin < last)//if改成while
 6         {
 7             int pivot = partitonThree(nums, begin, last);
 8             sortQuick(nums, begin, pivot - 1);
 9             begin = pivot + 1;//最后一次递归取消
10         }
11     }
12     else
13         sortInsert(nums, last - begin + 1);
14 }

这样部分递归变成了迭代，可以减少栈的深度

4.2非递归版

　　使用栈stack

 1 void sortQuick_nonrecursive(vector<int>& nums, int begin, int last)
 2 {
 3     stack<int> sta;
 4     sta.push(begin);
 5     sta.push(last);
 6     while (!sta.empty())
 7     {
 8         int right = sta.top();
 9         sta.pop();
10         int left = sta.top();
11         sta.pop();
12 
13         int pivot = partitonThree(nums, left, right);
14         if (left < (pivot - 1))//左子序列
15         {
16             sta.push(left);
17             sta.push(pivot - 1);
18         }
19         if ((pivot + 1) < right)//右子序列
20         {
21             sta.push(pivot + 1);
22             sta.push(right);
23         }
24     }
25 }