一道排序題引發的思考
題目：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; } };
結果：
從結果中我們可以看出，改進後的快速排序可以通過所有的測試用例，並且比歸併排序所用的空間要少。
是否還可以對快速排序繼續進行優化？
