排序算法：快速排序、归并排序

← 返回课程C++ 数据结构与算法 › 第 7 关

进度 0%

第 7 关：排序算法：快速排序、归并排序

C++进阶

📖 本课目标

本关属于《C++ 数据结构与算法》第 7 课。阅读右侧代码模板，理解每一行的作用，然后动手修改并完成练习。

🎯 本课要点

include <iostream>
include <vector>

🛠 学习方式

阅读右侧代码模板中的注释与实现
修改代码，尝试达成新的效果
点击「运行」查看实际输出
确认理解后点击「提交」标记本关完成

💡 说明

本关为 C++，浏览器内无法真正执行该语言。当前「运行」输出为演示结果，请在本地环境中编译运行以验证代码。

main.pytest.py

#include <iostream>
#include <vector>
using namespace std;

// 快速排序 O(n log n)
int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

// 归并排序 O(n log n)
void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp;
    int i = left, j = mid + 1;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) temp.push_back(arr[i++]);
        else temp.push_back(arr[j++]);
    }
    while (i <= mid) temp.push_back(arr[i++]);
    while (j <= right) temp.push_back(arr[j++]);
    for (int k = 0; k < temp.size(); k++) {
        arr[left + k] = temp[k];
    }
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void print(vector<int>& arr) {
    for (int x : arr) cout << x << " ";
    cout << endl;
}

int main() {
    vector<int> a = {38, 27, 43, 3, 9, 82, 10};
    vector<int> b = a;
    
    cout << "原始: "; print(a);
    quickSort(a, 0, a.size() - 1);
    cout << "快速排序: "; print(a);
    
    mergeSort(b, 0, b.size() - 1);
    cout << "归并排序: "; print(b);
    
    return 0;
}

点击「运行」或「提交代码」查看结果

📖 查看本课说明

第 7 关：排序算法：快速排序、归并排序

C++ · 进阶 · 《C++ 数据结构与算法》

include <iostream>
include <vector>

本关为 C++，浏览器无法真正编译运行，请在本地环境验证代码。