快排堆排

using namespace std;

class QuickSort {
  public:
    void Sort(vector<int> &nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int start = l;
        int end = r;
        int target = nums[l];
        while (l < r) {
            while (l < r && nums[r] <= target) {
                r--;
            }
            while (l < r && nums[l] >= target) {
                l++;
            }
            swap(nums[l], nums[r]);
        }
        swap(nums[start], nums[l]);
        Sort(nums, start, l - 1);
        Sort(nums, l + 1, end);
    }
};

class HeapSort {
  public:
    void Sort(vector<int> &nums) {
        HeapInit(nums);
        int n = nums.size();

        for (int i = 1; i <= n - 1; i++) {
            swap(nums[0], nums[n - i]);
            ChangeNode(nums, 0, n - i);
        }
    }

    void HeapInit(vector<int> &nums) {
        int n = nums.size();
        for (int i = n / 2 - 1; i >= 0; i--) {
            ChangeNode(nums, i, n);
        }
    }

    void ChangeNode(vector<int> &nums, int now, int length) {
        // from top to bottom
        while (now < length) {
            int left = now * 2 + 1;
            int right = now * 2 + 2;
            if (left >= length) {
                break;
            }
            int k = left;
            if (right < length && nums[right] > nums[left]) {
                k = right;
            }
            if (nums[k] > nums[now]) {
                swap(nums[k], nums[now]);
                now = k;
            } else {
                break;
            }
        }
    }
};