排序专题

本专题我们将回顾经典的排序算法，这节先看

冒泡排序

每一次遍历会将一个元素“浮”到数列的末尾
快速排序
排序的基本思想是：

1．先从数列中取出一个数作为基准数。

2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

3．再对左右区间重复第二步，直到各区间只有一个数。

代码模板

c++

void quick_sort(int q[], int l, int r){
	if (l >= r) return
	int i = l - 1;
	int r = r + 1;
	int x = q[l + r >>1];
	while (i < j){
		do i++; while(q[i] < x);
		do j--; while(q[j] > x);
		if(i < j)
			swap(q[i], q[j]);
	}
	quick_sort(q, l, j);
	quick_sort(q, j + 1, r);
}

while循环结束后，q[l…j] <= x,q[j+1…r] >= x
注:q[l…j] <= x意为q[l],q[l+1]…q[j-1],q[j]的所有元素都<= x
最小k个数

注意x不一定在位置j上
比如q=[4,7,2]，第一轮x为7，第一轮完事是[4,2,7]，j是1，x在位置2上

还有一个点，一定要多多留意两个指针l，r重合的情况，在有些题会对这个做文章，比如返回最小的k个数

leetcode面试题 17.14. 最小K个数

c++

class Solution {
public:
    vector<int> res;
    void quick_sort(vector<int>& arr, int l, int r, int k) {
        if (l >= r) return;
        int i = l - 1, j = r + 1;
        int x = arr[l + r >> 1];
        while (i < j) {
            do i++; while (arr[i] < x);
            do j--; while (arr[j] > x);
            if (i < j) swap(arr[i], arr[j]);
        }
        int n = j - l + 1;
        if (n > k)
            quick_sort(arr, l, j, k);
        else if (n == k) {
            for (int m = 0; m < k; m++) {
                res.push_back(arr[l + m]);
            }
        }
        else {
            for (int m = 0; m < n; m++) {
                res.push_back(arr[l + m]);
            }
            if (j + 1 == r)     //注意这个情况
                res.push_back(arr[r]);
            else
                quick_sort(arr, j + 1, r, k - n);
        }
    }
    vector<int> smallestK(vector<int>& arr, int k) {
        quick_sort(arr, 0, arr.size() - 1, k);
        return res;
    }
};

最开始我的写法发现有些情况最终的结果数组res元素小于k，也就是有些情况没有考虑到，其实就是当n < k的时候，也就是后半段还要进行递归去找剩下n-k个，当就剩下一个的时候，也就是j + 1 == r，进入下层递归在开头(l >= r)就退出了，所以这种情况要单独考虑的。

这道题还有很多解法，下面给出冒泡和堆得写法，冒泡会在最后一个用例超时

冒泡：

c++

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        for(int i = 0; i < k; i++){
            for(int i = arr.size() - 1; i > 0; i--){
                if(arr[i] < arr[i - 1])
                    swap(arr[i], arr[i - 1]);
            }
        }
        vector<int> res;
        for(int i = 0; i < k; i++){
            res.push_back(arr[i]);
        }
        return res;
    }
};

堆：

不正经版本：

c++

class Solution {
public:
    vector<int> smallestK(vector<int>& arr, int k) {
        sort(arr.begin(),arr.end());
        arr.resize(k);
        return arr;
    }
};

归并排序

对[l, r]这个区间的数，我们递归的先去排序[l, mid],[mid + 1, r]两个区间，然后对这两个排序好的区间进行合并：

c++

void merge_sort(vector<int> &vec, int l, int r) {
    if (l >= r) return;
    int mid = l + r >> 1;
    merge_sort(vec, l, mid - 1);
    merge_sort(vec, mid + 1, r);
    int i = l, j = mid + 1;
    vector<int> temp(r - l + 1);
    int k = 0;
    while(i <= mid && j <= r) {
        if (vec[i] < vec[j]) {
            temp[k++] = vec[i++];
        } else {
            temp[k++] = vec[j++];
        }
    }
    while (i <= mid) temp[k++] = vec[i++];
    while (j <= r) temp[k++] = vec[j++];
    for (int i = l, j = 0; i <= r; i++, j++) {
        vec[i] = temp[j];
    }
}