https://www.acwing.com/solution/content/24716/

https://www.acwing.com/blog/content/3585/

快速排序 (Quick Sort)

在待排序序列 nums 中选取一个元素 pivot 作为枢轴，通过一趟排序将 nums 0 ~ n-1分为两部分 0 ~ k-1 k+1 ~ n-1 (使得左侧的元素 ≤ 枢轴，右侧的元素 ≥ 枢轴)。递归地对两个子部分进行上述过程，直到每部分只有一个元素或为空。

void quick_sort(int q[], int l, int r)
{
    if (l >= r) return;

    int i = l - 1, j = r + 1, x = q[l + r >> 1];
    while (i < j)
    {
        do i ++ ; while (q[i] < x);
        do j -- ; while (q[j] > x);
        if (i < j) swap(q[i], q[j]);
    }
    quick_sort(q, l, j), quick_sort(q, j + 1, r);
}

• [ ] 将快排的递归写法改为非递归写法

归并排序 (Merge Sort)

void merge_sort(vector<int>& nums, int l, int r) {
    if (l >= r) return;

    vector<int> temp(r - l + 1);
    int mid = (l + r) / 2;
    merge_sort(nums, l, mid);
    merge_sort(nums, mid + 1, r);

    int i = l, j = mid + 1, k = 0;
    while (i <= mid && j <= r) {
        if (nums[i] < nums[j]) {
            temp[k++] = nums[i++];
        } else {
            temp[k++] = nums[j++];
        }
    }
    while (i <= mid) temp[k++] = nums[i++];
    while (j <= r) temp[k++] = nums[j++];
    for (i = l, j = 0; i <= r; i++, j++) nums[i] = temp[j];
}

堆排序 (Heap Sort)

把无序数组构建成二叉堆 循环删除堆顶元素，移到集合尾部，调节堆产生新的堆顶

完全二叉树的顺序存储

// nums[0 ... n - 1]
auto left = 2 * i + 1;
auto right = 2 * i - 1;
auto parent = (i + 1) / 2;

void head_adjust(vector<int>& nums, int k, int n) {
    for (int i = 2 * k + 1; i < n; i = 2 * i + 1) {
        if (i + 1 < n && nums[i] < nums[i + 1]) {
            i++;
        }
        if (nums[k] > nums[i]) break;
        else {
            swap(nums[k], nums[i]);
            k = i;
        }
    }
}

void build_max_heap(vector<int>& nums, int n) {
    for (int i = (n - 1) / 2; i >= 0; i--) {
        head_adjust(nums, i, n);
    }
}

void head_sort(vector<int>& nums) {
    int n = nums.size();
    if (n <= 1) return;
    build_max_heap(nums, n);

    for (int i = n - 1; i > 0; i--) {
        swap(nums[0], nums[i]);
        head_adjust(nums, 0, i);
    }
}

冒泡排序（Bubble Sort）

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n =nums.size();
        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j + 1 < n - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums[j], nums[j + 1]);
                }
            }
        }
        return nums;
    }
};

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n =nums.size();
        for (int i = 0; i < n - 1; i++) {
            bool ischanged = false;
            for (int j = 0; j + 1 < n - i; j++) {
                if (nums[j] > nums[j + 1]) {
                    swap(nums[j], nums[j + 1]);
                    ischanged = true;
                }
            }
            if (!ischanged) {
                cout << "break" << endl;
                break;
            }
        }
        return nums;
    }
};

最好情况是原数组有序，最快情况是逆序

选择排序（Select Sort）