经典排序算法

• 菜鸟导航！
  

选择排序

• 基本思想：每次从待排序的数据中选择最小（或最大）的元素，放到已排序序列的末尾，直到全部数据排序完成。→ 适用于数据量小且对性能要求不高的场景。（无额外的存储需求）

// 由小到大的选择排序示例
template<typename T>
void selection_sort(T arr[], int len) {
    for (int i = 0; i < len - 1; ++i) {
        int min = i;
        // 从待排序的数据中选择最小的元素
        for (int j = i + 1; j < len; ++j)
            if (arr[j] < arr[min])
                min = j;
        // 放到序列头部/末尾
        std::swap(arr[i], arr[min]);
    }
}

归并排序

• 基本思想：分而治之，分解 → 排序 → 合并！

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

    int k = 0;
    int i = left, j = mid + 1;
    vector<int> vec;

    while (i <= mid && j <= right)
    {
        if (nums[i] <= nums[j])
            vec.emplace_back(nums[i++]);
        else
            vec.emplace_back(nums[j++]);
    }

    while (i <= mid)
        vec.emplace_back(nums[i++]);
    while (j <= right)
        vec.emplace_back(nums[j++]);

    for (i = left, k = 0; i <= right; ++i)
        nums[i] = vec[k++];
}

快速排序

• 基本思想：选择基准元素，将列表分为两部分，递归地对这两部分进行排序。

void quickSort(vector<int>& nums, int l, int r)
{
    // 终止条件
    if (l >= r)
        return;
    
    // 随机选择基准元素
    int pivot = l + rand() % (r - l + 1);

    // 将基准元素放到数组最左边
    swap(nums[l], nums[pivot]);

    int i = l, j = r;
    while (i < j)
    {
        while (i < j && nums[l] <= nums[j])
            j--;
        while (i < j && nums[l] >= nums[i])
            i++;
        swap(nums[i], nums[j]);
    }

    // 将基准元素放到正确位置
    swap(nums[l], nums[i]);

    // 递归调用
    quickSort(nums, l, i - 1);
    quickSort(nums, i + 1, r);
}