Given an array of integers nums, sort the array in ascending order.
Example 1:
Input: [5,2,3,1]
Output: [1,2,3,5]
Example 2:
Input: [5,1,1,2,0,0]
Output: [0,0,1,1,2,5]
Note:
1<=A.length<=10000
-50000<=A[i]<=50000
這道題讓我們給數組排序，在平時刷其他題的時候，遇到要排序的時候，一般都會調用系統自帶的排序函數，像 C++ 中直接就調用 sort 函數即可，但是這道題考察的就是排序，再調用系統的排序函數就有些說不過去了。這裡需要自己實現排序功能，常見排序方法有很多，插入排序，選擇排序，堆排序，快速排序，冒泡排序，歸併排序，桶排序等等。它們的時間複雜度不盡相同，這道題貌似對於平方級複雜度的排序方法會超時，所以只能使用那些速度比較快的排序方法啦。題目給定了每個數字的範圍是 [-50000, 50000]，並不是特別大，這裡可以使用記數排序 Count Sort，在 LeetCode 中也有直接利用這個解法的題Sort Colors，建立一個大小為 100001 的數組 count，然後統計 nums 中每個數字出現的個數，然後再從0遍歷到 100000，對於每個遍歷到的數字i，若個數不為0，則加入 count 數組中對應個數的 i-50000 到結果數組中，這裡的 50000 是 offset，因為數組下標不能為負數，在開始統計個數的時候，每個數字都加上了 50000，那麼最後組成有序數組的時候就要減去，參見代碼如下：
解法一：
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int n = nums.size(), j = 0;
vector<int> res(n), count(100001);
for (int num : nums) ++count[num + 50000];
for (int i = 0; i < count.size(); ++i) {
while (count[i]-- > 0) {
res[j++] = i - 50000;
}
}
return res;
}
};
下面就是大名鼎鼎的快速排序了 Quick Sort，貌似 STL 中的內置 sort 函數就是基於快速排序的，只不過這裡要自己寫而已。在 LeetCode 中也有一道使用這個算法思想的題 Kth Largest Element in an Array。快排的精髓在於選一個 pivot，然後將所有小於 pivot 的數字都放在左邊，大於 pivot 的數字都放在右邊，等於的話放哪邊都行。但是此時左右兩邊的數組各自都不一定是有序的，需要再各自調用相同的遞歸，直到細分到只有1個數字的時候，再返回的時候就都是有序的了，參見代碼如下：
解法二：
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
quickSort(nums, 0, (int)nums.size() - 1);
return nums;
}
void quickSort(vector<int>& nums, int start, int end) {
if (start >= end) return;
int pivot = nums[start], i = start + 1, j = end;
while (i <= j) {
if (nums[i] > pivot && nums[j] < pivot) {
swap(nums[i++], nums[j--]);
}
if (nums[i] <= pivot) ++i;
if (nums[j] >= pivot) --j;
}
swap(nums[start], nums[j]);
quickSort(nums, start, j - 1);
quickSort(nums, j + 1, end);
}
};
我們也可以使用混合排序 Merge Sort，在 LeetCode 中也有一道使用這個思想的題 Count of Range Sum。混合排序的思想跟快速排序比較類似，但也不完全一樣，這裡其實是一種先對半分，一直不停的對半分，直到分到只有一個數字的時候返回，然後在返回的途中進行合併，合併的時候用到了一個臨時數組 tmp，先將區間 [start, end] 中的數字按順序存入這個臨時數組 tmp 中，然後再覆蓋原數組中的對應位置即可，參見代碼如下：
解法三：
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
mergeSort(nums, 0, (int)nums.size() - 1);
return nums;
}
void mergeSort(vector<int>& nums, int start, int end) {
if (start >= end) return;
int mid = (start + end) / 2;
mergeSort(nums, start, mid);
mergeSort(nums, mid + 1, end);
merge(nums, start, mid, end);
}
void merge(vector<int>& nums, int start, int mid, int end) {
vector<int> tmp(end - start + 1);
int i = start, j = mid + 1, k = 0;
while (i <= mid && j <= end) {
if (nums[i] < nums[j]) tmp[k++] = nums[i++];
else tmp[k++] = nums[j++];
}
while (i <= mid) tmp[k++] = nums[i++];
while (j <= end) tmp[k++] = nums[j++];
for (int idx = 0; idx < tmp.size(); ++idx) {
nums[idx + start] = tmp[idx];
}
}
};
Github 同步地址:
https://github.com/grandyang/leetcode/issues/912
類似題目：
Kth Largest Element in an Array
Sort Colors
Count of Range Sum
參考資料：
https://leetcode.com/problems/sort-an-array/
https://leetcode.com/problems/sort-an-array/discuss/319326/Java-merge-sort-implementation
https://leetcode.com/problems/sort-an-array/discuss/293820/Easiest-and-fastest-solution.-O(10n)
https://leetcode.com/problems/sort-an-array/discuss/280903/C%2B%2B-QuickSort-and-CountingSort-solutions
LeetCode All in One 題目講解匯總(持續更新中...)