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;
}

堆排序

#include <bits/stdc++.h>

using namespace std;

void adjust(vector<int>& nums, int start, int end) {
    int tmp = nums[start];
    for (int i = 2 * start + 1; i <= end; i = i * 2 + 1) {
        // 有右孩子并且左孩子小于右孩子
        if (i < end && nums[i] < nums[i + 1]) {
            i++;
        }
        // i一定是左右孩子的最大值
        if (nums[i] > tmp) {
            nums[start] = nums[i];
            start = i;
        } else {
            // 比左右孩子都大
            break;
        }
    }
    nums[start] = tmp;
}

void heapSort(vector<int>& nums) {
    int len = (int) nums.size();
    // 第一次建立大根堆，从后往前依次调整
    for (int i = (len - 1 - 1) / 2; i >= 0; i--) {
        adjust(nums, i, len - 1);
    }
    // 每次将根和待排序的最后一次交换，然后在调整
    int tmp;
    for (int i = 0; i < len - 1; i++) {
        swap(nums[0], nums[len - i - 1]);
        adjust(nums, 0, len - 1 - i - 1);
    }
}

int main() {
    vector<int> nums = {9, 5, 6, 3, 5, 3, 1, 0, 96, 66};
    heapSort(nums);
    for (auto num: nums) cout << num << " ";
    return 0;
}