题解 | #排序# C++ 解法，快排，归并，堆排

题解 | #排序#
C++ 解法，快排，归并，堆排

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    // 快排
    void quick_sort(vector<int> &arr, int l, int r) {
        if (l >= r) return ;
        int x = l, y = r, z = arr[(l + r) >> 1];
        do {
            while (arr[x] < z) ++x;
            while (arr[y] > z) --y;
            if (x <= y) {
                swap(arr[x], arr[y]);
                ++x, --y;
            }
        } while (x <= y);
        quick_sort(arr, l, y);
        quick_sort(arr, x, r);
        return ;
    }
    // 归并
    void merge_sort(vector<int> &arr, int l, int r, vector<int> &tmp) {
        if (l >= r) return ;
        int mid = ((long long)l + r) >> 1;
        merge_sort(arr, l, mid, tmp);
        merge_sort(arr, mid + 1, r, tmp);
        int i = l, j = mid + 1;
        for (int k = l; k <= r; ++k) {
            tmp[k] = arr[k];
        }
        for (int k = l; k <= r; ++k) {
            if (i == mid + 1) {
                arr[k] = tmp[j++];
            } else if (j == r + 1 || tmp[i] <= tmp[j]) {
                arr[k] = tmp[i++];
            } else {
                arr[k] = tmp[j++];
            }
        }
        return ;
    }
    // 堆排
    void heapify(vector<int> &arr, int n, int i) {
        int l = 2 * i + 1;
        int r = 2 * i + 2;
        int max = i;
        if (l < n && arr[l] > arr[max]) {
            max = l;
        }
        if (r < n && arr[r] > arr[max]) {
            max = r;
        }
        if (max != i) {
            swap(arr[max], arr[i]);
            heapify(arr, n, max);
        }
        return ;
    }
    void build_heap(vector<int> &arr, int n) {
        int last_node_ind = n - 1;
        int parent = (last_node_ind - 1) >> 1;
        for (int i = parent; i >= 0; --i) {
            heapify(arr, n, i);
        }
        return ;
    }
    void heap_sort(vector<int> &arr, int n) {
        build_heap(arr, n);
        for (int i = n - 1; i >= 0; --i) {
            swap(arr[i], arr[0]);
            heapify(arr, i, 0);
        }
        return ;
    }
    vector<int> MySort(vector<int>& arr) {
        // quick_sort(arr, 0, arr.size() - 1);
        /* vector<int> tmp(arr.size());
        merge_sort(arr, 0, arr.size() - 1, tmp); */
        heap_sort(arr, arr.size());
        return arr;
    }
};