用 C++ 正确地手写经典排序算法（上）

不同的人写同一个算法，可能会有不同的实现细节。为了能在做题或面试过程中快速、准确地写出经典排序算法，我总结了自己的写法以及在实现中需要注意的一些细节。本系列分为上下两篇文章。

上篇（本文）：冒泡排序、选择排序、插入排序、快速排序、归并排序

下篇：堆排序、希尔排序、计数排序、桶排序、基数排序

冒泡排序

• 外层循环 pass 表示趟数，共循环 len - 1 趟，因为只剩下一个元素时默认是有序的。
• 外层每一趟都会把未排序部分中最大的元素依次交换到未排序部分的末尾，交换后这一元素成为已排序部分的第一个元素。
• 内层循环从 0 遍历到 len - pass - 1，因为在第 pass 趟时，数组末尾的 pass 个元素已经排好序了。减 1 是因为两两交换使用了下标 i+1。

void bubbleSort(vector<int>& nums) {
    int len = nums.size();
    for (int pass = 0; pass < len - 1; pass++) {
        for (int i = 0; i < len - pass - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                swap(nums[i], nums[i + 1]);
            }
        }
    }
}

选择排序

• 外层循环 i 表示趟数，共循环 len - 1 趟，因为只剩下一个元素时默认是有序的。
• 外层每一趟都会把未排序部分中最小的元素（下标为 min_pos）交换到下标为 i 的位置，交换后下标为 i 的元素成为已排序部分的最后一个元素。
• 内层循环在下标区间 $[i+1, \textit{len}-1]$ 中找到最小的元素，并记录该最小元素的下标 min_pos。

void selectionSort(vector<int> &nums) {
    int len = nums.size();
    for (int i = 0; i < len - 1; i++) {
        int min_pos = i;
        for (int j = i + 1; j < len; j++) {
            if (nums[j] < nums[min_pos]) {
                min_pos = j;
            }
        }
        swap(nums[i], nums[min_pos]);
    }
}

本文地址：https://www.jeddd.com/article/sorting-algorithm-in-cpp-1.html

插入排序

• 外层 for 循环从 1 开始，因为算法开始时，有序部分只包含 nums[0] 这一个元素。
• 内层 while 循环从下标 i - 1 开始内自右向左寻找首个不大于 nums[i] 的元素，然后把 nums[i] 插入到该元素后面（下标 j + 1）；如果没找到，那么把 nums[i] 插入到最前面（下标 0）。
• 由于在数组中插入元素需要将它后面的元素逐个右移，所以要提前保存 nums[i] 的值到 temp 中以防覆盖。

void insertionSort(vector<int>& nums) {
    int len = nums.size();
    for (int i = 1; i < len; i++) {
        int temp = nums[i];
        int j = i - 1;
        while (j >= 0 && nums[j] > temp) {
            nums[j + 1] = nums[j];
            j--;
        }
        nums[j + 1] = temp;
    }
}

快速排序

• 当 low == high 时，区间内只包含一个元素，则默认是有序的，递归停止。
• pivot_pos 记录的是最后一个小于 pivot 的元素的下标。
• 从 low + 1 开始自左向右遍历每个元素，将所有小于 pivot 的元素交换到 pivot_pos 下一个元素的位置，同时更新 pivot_pos。也就是 pivot_pos 先递增，后交换。

• 交换过程：

int partition(vector<int>& nums, int low, int high) {
    int pivot = nums[low];
    int pivot_pos = low;
    for (int i = low + 1; i <= high; i++) {
        if (nums[i] < pivot) {
            swap(nums[++pivot_pos], nums[i]);
        }
    }
    swap(nums[low], nums[pivot_pos]);
    return pivot_pos;
}

void quickSort(vector<int>& nums, int low, int high) {
    if (low < high) {
        int pivot_pos = partition(nums, low, high);
        quickSort(nums, low, pivot_pos - 1);
        quickSort(nums, pivot_pos + 1, high);
    }
}

归并排序

• 当 low == high 时，区间内只包含一个元素，则默认是有序的，递归停止。
• 用 low + (high - low) / 2 代替 (low + high) / 2 是为了防止溢出。
• 归并排序不是原址的，在 merge 中先将左右两部分分别复制了一份，然后再归并回原先的数组中。
• 归并时，k 是原数组的下标，从 low 开始而不是从 0 开始。i 和 j 是复制出来的新数组的下标，都从 0 开始。

void merge(vector<int>& nums, int low, int mid, int high) {
    // Copy data into two temp vectors
    vector<int> left(nums.begin() + low, nums.begin() + mid + 1);
    vector<int> right(nums.begin() + mid + 1, nums.begin() + high + 1);

    // Merge them back into the original vector
    int i = 0, j = 0, k = low;
    while (i < left.size() && j < right.size()) {
        if (left[i] <= right[j])
            nums[k++] = left[i++];
        else
            nums[k++] = right[j++];
    }
    while (i < left.size()) nums[k++] = left[i++];
    while (j < right.size()) nums[k++] = right[j++];
}

void mergeSort(vector<int>& nums, int low, int high) {
    if (low < high) {
        int mid = low + (high - low) / 2;
        mergeSort(nums, low, mid);
        mergeSort(nums, mid + 1, high);
        merge(nums, low, mid, high);
    }
}

本文地址：https://www.jeddd.com/article/sorting-algorithm-in-cpp-1.html