一道排序题引发的思考
题目：912. 排序数组
给你一个整数数组 nums，请你将该数组升序排列。
示例 1：
输入：nums = [5,2,3,1]
输出：[1,2,3,5]
示例 2：
输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]
提示：
1 <= nums.length <= 50000
-50000 <= nums[i] <= 50000
思考一：朴素快速排序
之所以叫做朴素快速排序是因为在选取枢轴量的时候就是选取最左边的那个元素来当做枢轴量，但是这样有一个很大的问题就是如果所给的排序序列都已经有序的话，这种情况下快速排序的时间复杂度会退化到O(n^2)，最后提交的时候也会有一组数据显示超时。
Code：
class Solution { public: void quickSort(vector<int>& nums, int l, int r) { if (l >= r) return; int pivot = partion(nums, l, r); quickSort(nums, l, pivot - 1); quickSort(nums, pivot + 1, r); } int partion(vector<int>& nums, int l, int r) { int temp = nums[l]; while (l < r) { while (l < r && nums[r] >= temp) r--; nums[l] = nums[r]; while (l < r && nums[l] <= temp) l++; nums[r] = nums[l]; } nums[l] = temp; return l; } vector<int> sortArray(vector<int>& nums) { int len = nums.size(); quickSort(nums, 0, len - 1); return nums; } };
结果：
思路二：归并排序
既然朴素快速排序在特定的条件下会退化到O（n^2），如果选择归并排序的话就不会存在时间复杂度退化到O（n^2）的情况，平均时间复杂度为O（nlogn），而且归并排序也是一种稳定的排序算法。但是，归并排序存在的缺点是需要一个额外的存储空间因此空间复杂的变为O(n)。而且平均情况下归并排序的常量因子k（O（knlogn））要比快速排序的常量因子大。
Code：
class Solution { public: vector<int> dummy; void mergeSort(vector<int>& nums, int l, int r) { if (l >= r) return; int m = (l + r) / 2; mergeSort(nums, l, m); mergeSort(nums, m+1, r); merge(nums, l, m, m+1, r); } void merge(vector<int>& nums, int l1, int r1, int l2, int r2) { int start = l1; int end = r2; int index = l1; while(l1 <= r1 && l2 <= r2) { if (nums[l1] <= nums[l2]) { dummy[index++] = nums[l1++]; } else { dummy[index++] = nums[l2++]; } } while (l1 <= r1) { dummy[index++] = nums[l1++]; } while (l2 <= r2) { dummy[index++] = nums[l2++]; } for (int i = start; i <= end; ++i) { nums[i] = dummy[i]; } } vector<int> sortArray(vector<int>& nums) { int len = nums.size(); dummy.resize(len); mergeSort(nums, 0, len - 1); return nums; } };
结果：
思路三：三者取其中快速排序
在《数据结构》（严蔚敏、吴伟民）这本书中介绍了这种方法，具体的做法就是在选取枢轴量的时候不是选取第一个元素作为枢轴量，而是在nums[l], nums[r], nums[mid]中选取一个中间值作为枢轴量，这样的话，如果原来的序列已经有序的话可以减少交换的次数（快速排序是一种基于交换的排序算法，不稳定），从而减少在最坏情况下的时间复杂度，但是仍然不能够做到在对已经有序的序列进行排序时做到O（n）。
Code：
class Solution { public: int findMid(vector<int>& nums, int l, int r) { int m = (l + r) / 2; int x1 = nums[l]; int x2 = nums[m]; int x3 = nums[r]; int t; if (x1 > x2) { t = x1; x1 = x2; x2 = t; } if (x1 > x3) { t = x1; x1 = x3; x3 = t; } if (x2 > x3) { t = x2; x2 = x3; x3 = t; } if (nums[l] == x2) return l; else if (nums[m] == x2) return m; else return r; } void quickSort(vector<int>& nums, int l, int r) { if (l >= r) return; int pivot = partion(nums, l, r); quickSort(nums, l, pivot - 1); quickSort(nums, pivot + 1, r); } int partion(vector<int>& nums, int l, int r) { int index = findMid(nums, l, r); int temp = nums[index]; nums[index] = nums[l]; while (l < r) { while (l < r && nums[r] >= temp) r--; nums[l] = nums[r]; while (l < r && nums[l] <= temp) l++; nums[r] = nums[l]; } nums[l] = temp; return l; } vector<int> sortArray(vector<int>& nums) { int len = nums.size(); quickSort(nums, 0, len - 1); return nums; } };
结果：
从结果中我们可以看出，改进后的快速排序可以通过所有的测试用例，并且比归并排序所用的空间要少。
是否还可以对快速排序继续进行优化？
