有被恶心到，几年没有手写快排了，细节已经忘记了。
题意
输入一个数组进行排序
思路
快速排序（其他排序方法也可以）
但是呢，这题主要是对普通的快速排序进行了hack，增加了一组有序的大数据，使得没有随机选取基数的方法超时了。
快排的思想：
主要是在一组数组中选取一个数做完基数，让数组以基数为准，使得比基数大的都在基数右边，比基数小的都在基数左边，此被称为一轮快排排序。
之后，将数组从基数处分开使得基数左右两边个组成一个数组，再对这两个数组分别进行快速排序。
重复此过程就可以得到有序的数组。
本文使用了两个优化：
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
|
#include "vector"
#include "algorithm"
#include "ctime"
using namespace std;
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
srand((unsigned)time(NULL));
quickSort(nums, 0, nums.size()-1);
return nums;
}
void quickSort(vector<int>& nums, int l, int r){
if(l >= r) return;
int k = rand()%(r-l+1)+l;
swap(nums[k], nums[l]);
int i = l, j = r;
while(i < j){
while(i < j && nums[j] >= nums[l]) j--;
while(i < j && nums[i] <= nums[l]) i++;
if(i < j) swap(nums[i], nums[j]);
}
swap(nums[l], nums[i]);
quickSort(nums,l, i-1);
quickSort(nums,i+1, r);
}
};
|