doc/算法/排序算法/基本排序算法.md

归并排序

#include <bits/stdc++.h>
using namespace std;

void merge(vector<int>& nums, int left, int right, int mid) {
    vector<int> temp(right - left + 1);
    int i = left;
    int j = mid + 1;
    int k = 0;
    while (i <= mid && j <= right) {
        if (nums[i] > nums[j]) {
            temp[k++] = nums[j++];
        } else {
            temp[k++] = nums[i++];
        }
    }
    while (i <= mid) {
        temp[k++] = nums[i++];
    }
    while (j <= right) {
        temp[k++] = nums[j++];
    }
    for (i = left, k = 0; k < temp.size(); k++) {
        nums[i++] = temp[k];
    }
}

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

int main() {
    vector<int> nums = {50, 10, 20, 30, 70, 40, 80, 60};
    mergeSort(nums, 0, nums.size() - 1);
    for (auto num : nums) {
        cout << num << " ";
    }
    return 0;
}

快速排序

#include <bits/stdc++.h>
using namespace std;

void quickSort(vector<int>& nums, int left, int right) {
    if (left >= right) return;
    int temp = nums[left];
    int i = left;
    int j = right;
    while (i != j) {
        while (j > i && nums[j] >= temp) {
            j--;
        }
        while (j > i && nums[i] <= temp) {
            i++;
        }
        if (i < j) {
            swap(nums[i], nums[j]);
        }
    }
    swap(nums[left], nums[j]);
    quickSort(nums, left, i - 1);
    quickSort(nums, i + 1, right);
}

int main() {
    vector<int> nums = {50, 10, 20, 30, 70, 40, 80, 60};
    quickSort(nums, 0, nums.size() - 1);
    for (auto num : nums) {
        cout << num << " ";
    }
    return 0;
}