AC Code (quick sort 60ms)

把 pivot 當作分水嶺，in-place 的把 $\leq$ pivot 的數字搬到左邊， $\gt$ 的搬到右邊。

 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
39
40
41
42
43
44
45


class Solution {
private:
    void qSort(int lb, int rb, vector<int> &nums) { // [lb, rb)
        int n = rb - lb;
        
        // terminating condition
        if(n <= 1) {
            return;
        }
        
        int pivot = lb + rand() % n;
        swap(nums[rb - 1], nums[pivot]); // pivot init at rb - 1
        pivot = rb - 1; // lol, don't forget
        
        int i = lb;
        while(i != pivot) { 
            if(i < pivot) {
                if(nums[i] <= nums[pivot]) {
                    i++;
                } else {
                    swap(nums[i], nums[pivot]);
                    swap(pivot, i);
                    i--;
                }
            } else {
                if(nums[pivot] > nums[i]) {
                    swap(nums[i], nums[pivot]);
                    swap(pivot, i);
                    i++;
                } else {
                    i--;
                }
            }
        }

        qSort(lb, i, nums);
        qSort(i + 1, rb, nums);
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        qSort(0, nums.size(), nums);
        
        return nums;
    }
};

AC code (quick sort 472ms)

直觀的實作，有很多 vector 的操作，所以比較慢。

 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


class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        // straight forward implementation of quick sort
        int n = nums.size();
        
        // terminating condition
        if(n <= 1) {
            return nums;
        }
        
        int pivot = rand() % n;
        vector<int> left, right;
        for(int i = 0; i < n; i++) {
            if(i != pivot) {
                if(nums[i] <= nums[pivot]) {
                    left.push_back(nums[i]);
                } else {
                    right.push_back(nums[i]);
                }
            }
        }
        
        left = sortArray(left);
        right = sortArray(right);
        
        vector<int> ret(left);
        ret.push_back(nums[pivot]);
        ret.insert(ret.end(), right.begin(), right.end());
        
        return ret;
    }
};