acwing算法基础课笔记-快速排序和归并排序

发表于 2021-08-16 更新于 2022-04-02 分类于 acwing算法基础课笔记 Artalk： loading...

快排归并

前言

快速排序和归并排序都是基于分治思想，平均时间复杂度都是 $\Omicron(n\log_2 n)$

快排是不稳定的，归并排序是稳定的

快排的性能受初始数列的分布影响较大，最坏情况下时间复杂度达到 $\Omicron(n^2)$ ，空间复杂度达到 $\Omicron(n)$

快速排序

思路

分治思想

确定分界点pivot

调整区间

暴力方法
一般方法—交换双指针

void quickSort(int q[], int l, int r){
    if (l >= r) return;
    int x = q[l], i = l - 1, j = 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]);
    }
    quickSort(q, l, j);//这里一定是j，呼应前面的x=q[l],否则有可能无限循环。例如 1，2
    quickSort(q, j + 1, r);
}

递归

代码1–yxc版本

#include <iostream>

using namespace std;

const int N = 1000010;

int q[N];
void quickSort(int q[], int l, int r){
    if (l >= r) return;
    int x = q[l + r >> 1], i = l - 1, j = 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]);
    }
    quickSort(q, l, j);
    quickSort(q, j + 1, r);
}
int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &q[i]);
    
    quickSort(q, 0, n - 1);
    
    for (int j = 0; j < n; ++j) printf("%d ", q[j]);
    
    return 0;
}

代码2–严老师版本

#include <iostream>

using namespace std;

const int N = 1000010;

int q[N];
int helper(int q[], int low, int high) {
    int pivot = q[low];
    while (low < high) {
        while (low < high && q[high] >= pivot)
            --high;
        q[low] = q[high];
        while (low < high && q[low] <= pivot)
            ++low;
        q[high] = q[low];
    }
    q[low] = pivot;
    return low;
}
void quickSort(int q[], int l, int r) {
    if (l < r) {
        int pivotPos = helper(q, l, r);
        quickSort(q, l, pivotPos - 1);
        quickSort(q, pivotPos + 1, r);
    }
}
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
        scanf("%d", &q[i]);

    quickSort(q, 0, n - 1);

    for (int j = 0; j < n; ++j)
        printf("%d ", q[j]);

    return 0;
}

快选——quickSelect

acwing 786. 第k个数

与快排不同，每次迭代，只需递归一边。

复杂度 $\Omicron(n)$

第一次迭代 $n$
第二次迭代 $\frac{n}{2}$
……
$n+\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+\cdots=n(1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots)$
而 $\lim_{n\to\infty}1+\frac{1}{2}+\frac{1}{4}+\frac{1}{8}+\cdots+\frac{1}{2^{n}}=2$
所以是 $\Omicron(n)$

//时间复杂度是O(n)
//
#include <iostream>
using namespace std;

const int N = 1000010;
int q[N];
int n, k;

int quickSelect(int l, int r, int k){
    if (l == r) return q[l];
    int x = q[l];
    int i = l - 1, j = r + 1;
    while (i < j){
        while(q[++i] < x);
        while(q[--j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    int sl = j - l + 1;
    if (k <= sl) return quickSelect(l, j, k);
    return quickSelect(j + 1, r, k - sl);  
}
    
int main(){
    cin >> n >> k;
    for (int i = 0; i < n; ++i){
        cin >> q[i];
    }
    cout << quickSelect(0, n - 1, k) << endl;
    return 0;

注意事项：背诵模板的目的之一在于边界情况的处理，避免重复思考。

归并排序

思路1-自顶向下

分治思想
归并排序是稳定的

采用递归实现，本质是先将数组二分切成一个个小数组，直到每个小数组长度为1（因为只有一个元素时，数组一定有序），再逐步合并新的有序序列，以此递推。

代码流程：

确定分界点 mid=(left+right)/2;
递归排序左右两部分
“归并”——合二为一
- 申请一个新数组储存结果
- 两个指针分别指向两个有序序列的开头（最小值）
- 依次进行比较，if(a[i] <= b[j]) res[k++] = a[i++];

代码

#include <iostream>
using namespace std;

const int N = 1000010;

int n;
int q[N], tmp[N];
void mergeSort(int q[], int l, int r){
    if (l >= r) return;
    int mid = l + r >> 1;
    mergeSort(q, l, mid);
    mergeSort(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];
}
int main(){
    scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d", &q[i]);
    
    mergeSort(q, 0, n - 1);
    
    for (int i = 0; i < n; ++i) printf("%d", q[i]);
    
}

算法时间复杂度: $\Omicron(n\log_2n)$

思路2-自底向上

@2022年 3月24日星期四 23时15分27秒 CST
更新自底向上的写法
参考自顶向下归并排序和自底向上的归并排序

自底向上可以采用循环实现。开始，直接将数组两两归并，此轮循环后，数组变成两两有序的；然后每四个归并，数组变成每四个是有序的 $\dots$ 以此递推，直到每 $\lfloor{2^{x}}\rfloor=n$ 个元素是有序的。循环轮次为 $x$

$Java$ 版代码如下

public int[] mergeSort(int[] nums) {
    // 自底向上
    int n = nums.length;
    int[] tmp = new int[n];
    int start, mid, end, i, j, k;
    for (int len = 1; len < n; len = 2 * len) {
        for (start = 0; start < n; start = start + 2 * len) {
            mid = start + len - 1;
            end = Math.min(start + 2 * len - 1, n - 1);
            if (mid > end) mid = start + end >> 1; // 长度不够len的区间，有可能mid会大于end，超出合法范围
            i = start; j = mid + 1; k = 0;
            // 正常合并
            while (i <= mid && j <= end) {
                if (nums[i] <= nums[j]) tmp[k++] = nums[i++];
                else tmp[k++] = nums[j++];
            }
            while (i <= mid) tmp[k++] = nums[i++];
            while (j <= end) tmp[k++] = nums[j++];

            for (i = start, j = 0; i <= end; ++i, ++j) nums[i] = tmp[j];
        }
    }
    return nums;
}

例题

用归并排序思想求逆序对

代码

#include <iostream>

using namespace std;

typedef long long LL;

const int N = 100010;
int q[N], tmp[N];

LL mergeSort(int l, int r){
    if (l >= r) return 0;
    int mid = l + r >> 1;
    
    LL res = mergeSort(l, mid) + mergeSort(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++];
            res += mid - i + 1;
        }
    }
    // 扫尾处理
    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];
    }
    return res;
}

int main(void){
    int n;
    cin >> n;
    for (int i = 0; i < n; ++i){
        cin >> q[i];
    }
    cout << mergeSort(0, n - 1) << endl;
    return 0;
}

leetcode 23. 合并K个升序链表

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        int len = lists.length;
        if (len == 0 || len == 1 && lists[0] == null) return null;
        return merge(lists, 0, len - 1);
    }
    ListNode merge(ListNode[] lists, int l, int r) {
        if (l > r) return null; // 
        if (l == r) return lists[l];
        int mid = l + r >> 1;
        ListNode left = merge(lists,  l, mid);
        ListNode right = merge(lists, mid + 1, r);
        return mergeListNode(left, right);
    }
    ListNode mergeListNode(ListNode x, ListNode y) {
        ListNode res = new ListNode(0);
        ListNode p = res;
        while (x != null && y != null) {
            if (x.val < y.val) {
                p.next = x;
                x = x.next;
            } else {
                p.next = y;
                y = y.next;
            }
            p = p.next;
        }
        if (x != null) p.next = x;
        if (y != null) p.next = y;
        return res.next;
    }
}

Tips

找链表的中点，可以用快慢指针的方法，快指针每次移动2步，慢指针每次移动1步，当快指针到达链表末尾时，慢指针指向的链表节点即为链表的中点。

剑指 Offer II 077. 链表排序

要求：在 $\Omicron(n\log{n})$ 时间复杂度和 $\Omicron(1)$ 空间复杂度下，对链表进行排序

链表排序–>不能随机访问–>快排和堆排不能用–>只能用归并排序

基于分治的思想

代码：

class Solution {
    public ListNode sortList(ListNode head) {
        return merge(head);
    }
    ListNode merge(ListNode list) {
        if (list == null) return null;
        if (list.next == null) return list;
        ListNode midNode = findMid(list);
        ListNode rightStart = midNode.next;
        midNode.next = null; // 不要忘记截断！！！！
        ListNode left = merge(list);
        ListNode right = merge(rightStart);
        return mergeListNode(left, right);
    }

    ListNode mergeListNode(ListNode x, ListNode y) {
        ListNode res =  new ListNode(0);
        ListNode p = res;
        while (x != null && y != null) {
            if (x.val < y.val) {
                p.next = x;
                x = x.next;
            } else {
                p.next = y;
                y = y.next;
            }
            p = p.next;
        }
        if (x != null) p.next = x;
        if (y != null) p.next = y;
        return res.next;
    }

    ListNode findMid(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode fast = dummy, slow = dummy;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}

注意细节：

1 2	ListNode rightStart = midNode.next; midNode.next = null;

不要忘记将链表截断，分成两个独立的链表，否则会产生死循环。

📔博文图谱

提及本博文的链接

「前k个高频元素」解法优化过程