排序的问题基本都是让我们利用各种排序的思想去解决其他问题的

快排

思想

快速排序所采用的思想是分治的思想。所谓分治，就是指以一个数为基准，将序列中的其他数往它两边“扔”。以从小到大排序为例，比它小的都“扔”到它的左边，比它大的都“扔”到它的右边，然后左右两边再分别重复这个操作，不停地分，直至分到每一个分区的基准数的左边或者右边都只剩一个数为止。这时排序也就完成了。

快排模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, 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);
}

32、调整数组顺序使奇数位于偶数前面

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution {
public:
    void reOrderArray(vector<int> &array) {
        int l = 0, r = array.size() - 1;
         while (l < r) {
             while (l < r && array[l] % 2 == 1) l ++ ;
             while (l < r && array[r] % 2 == 0) r -- ;
             if (l < r) swap(array[l], array[r]);
         }
    }
};

普通归并

思想

分治思想：分：划分成很多个小的问题，然后递归处理，治：将分阶段得到的答案整合起来，即为分治思想。

20210706201255615.png

归并模板

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

void merge_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int mid = l + r >> 1;
    merge_sort(q, l, mid);
    merge_sort(q, mid + 1, r);

    int k = 0, i = l, j = mid + 1;
    while (i <= mid && j <= r)
        if (q[i] <= q[j]) tmp[k ++ ] = q[i ++ ];
        else tmp[k ++ ] = q[j ++ ];

    while (i <= mid) tmp[k ++ ] = q[i ++ ];
    while (j <= r) tmp[k ++ ] = q[j ++ ];

    for (i = l, j = 0; i <= r; i ++, j ++ ) q[i] = tmp[j];
}

65、数组中的逆序对

 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

class Solution {
public:
    int res = 0;
    int b[100];
    void merge_sort(vector<int>& a,int l,int r){
        if(l>=r) return;
        int mid = l+r>>1;
        merge_sort(a,l,mid);
        merge_sort(a,mid+1,r);
        int k = l,i=l,j=mid+1;
        while(i<=mid&&j<=r){
            if(a[i]<=a[j]) b[k++]=a[i++];
            else{
                b[k++]=a[j++];
                res+=mid-i+1;
            }
        }
        while(i<=mid) b[k++]=a[i++];
        while(j<=r) b[k++]=a[j++];
        for(i=l;i<=r;i++) a[i]=b[i];
    }
    int inversePairs(vector<int>& nums) {
        merge_sort(nums,0,nums.size()-1);
        return res;
    }
};

三路归并

62、丑数

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    int getUglyNumber(int n) {
        if(n <= 1) return n;
        vector<int> f(1,1);
        int i = 0, j = 0, k = 0;
        long long t = 0;
        while(--n)
        {
            t = min({f[i] * 2,f[j] * 3, f[k] * 5});
            if(t == f[i] * 2) i++;
            if(t == f[j] * 3) j++;
            if(t == f[k] * 5) k++;
            f.push_back(t);
        }
        return f.back();

    }
};