冒泡排序

插入排序

选择排序

快速排序

最好情况O(nlogn),最坏情况 $O(n^2)$ ，平均情况O(nlogn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void quickSort(int l, int r, vector<int>& nums){
    if(l >= r) return ;
    int mid = partition(l, r, nums);
    //递归排序左边和右边
    quickSort(mid+1, r, nums);
    quickSort(l, mid-1, nums);
}
int partition(int l, int r, vector<int>& nums){
    int pivot = nums[l]; //以最左边元素为基准
    while(l < r){
        while(l < r && nums[r] >= pivot) r--;
        nums[l] = nums[r];
        while(l < r && nums[l] <= pivot) l++;
        nums[r] = nums[l];
    }
    nums[l] = pivot;
    return l;
}
vector<int> sortArray(vector<int>& nums) {
    int n = nums.size();
    quickSort(0, n-1, nums);
    return nums;
}
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
void quickSort(int l, int r, vector<int>& nums){
        if(l >= r) return ;
        int mid = partition(l, r, nums);
        quickSort(mid+1, r, nums);
        quickSort(l, mid-1, nums);
    }
    int partition(int l, int r, vector<int>& nums){
        int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums[r], nums[i]);
        int pivot = nums[r];
        i = l-1;
        for(int j = l;j < r;j++){
            if(nums[j] < pivot){
                i = i+1;
                swap(nums[i],nums[j]);
            }
        }
        i = i+1;
        swap(nums[i], nums[r]);
        return i;
    }
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        quickSort(0, n-1, nums);
        return nums;
    }

归并排序

最好情况下O(nlogn)，最坏情况下O(nlogn)，平均情况下O(nlogn)

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
vector<int> tmp;
    void mergeSort(int l, int r, vector<int>& nums){
        if(l >= r) return ;
        int mid = (l+r)>>1;
        mergeSort(l, mid, nums);
        mergeSort(mid+1, r, nums);
        int i = l, j = mid+1;
        int k = 0;
        while(i <= mid && j <= r){
            if(nums[i] <= nums[j]){
                tmp[k++] = nums[i++];
            }else {
                tmp[k++] = nums[j++];
            }
        }
        while(i <= mid){
            tmp[k++] = nums[i++];
        }
        while(j <= r){
            tmp[k++] = nums[j++];
        }
        for(int i = 0;i < r-l+1;i++){
            nums[i+l] = tmp[i];
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        tmp.resize(n);
        mergeSort(0, n-1, nums);
        return nums;
    }

堆排序

最好情况下O(nlogn)，最坏情况下O(nlogn)，平均情况下O(nlogn)

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
void heapSort(vector<int>& nums){
    int len = nums.size()-1;
    //先建一个大根堆
    buildMaxHeap(nums, len);
    for(int i = len;i >= 1; --i){
        //将堆顶和最后一个元素交换位置
        swap(nums[i], nums[0]);
        len -= 1;
        //最后i个已经排好序，将前len-i个继续建一个大根堆，重复以上过程
        maxHeapify(nums,0,len);
    }
}
void buildMaxHeap(vector<int>& nums, int len) {
    //从最后一个父节点开始判断，让每个父节点都大于自己的孩子节点
    for (int i = len / 2; i >= 0; --i) {
        maxHeapify(nums, i, len);
    }
}
void maxHeapify(vector<int>& nums, int i, int len) {
    // for循环递归调整受影响的子树
    for (; (i << 1) + 1 <= len;) {
        int lson = (i << 1) + 1;
        int rson = (i << 1) + 2;
        int large;
        if (lson <= len && nums[lson] > nums[i]) {
            large = lson;
        } else {
            large = i;
        }
        if (rson <= len && nums[rson] > nums[large]) {
            large = rson;
        }
        if (large != i) {
            swap(nums[i], nums[large]);
            i = large;
        } else {
            break;
        }
    }
}
vector<int> sortArray(vector<int>& nums) {
    heapSort(nums);
    return nums;
}