C++ 排序算法：快速排序和归并排序详解

C++ 中提供了很多排序算法，如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。其中，快速排序和归并排序是较为常用和高效的排序算法。

以下是 C++ 中快速排序和归并排序的实现代码。

快速排序：

void quickSort(int arr[], int left, int right) {
    if (left >= right) return;  // 递归边界
    int pivot = arr[left];      // 设置基准值
    int i = left, j = right;
    while (i < j) {
        while (i < j && arr[j] >= pivot) j--;  // 从右向左找第一个小于基准值的数
        if (i < j) arr[i++] = arr[j];          // 将该数移到左端
        while (i < j && arr[i] < pivot) i++;   // 从左向右找第一个大于等于基准值的数
        if (i < j) arr[j--] = arr[i];          // 将该数移到右端
    }
    arr[i] = pivot;  // 将基准值放到正确的位置
    quickSort(arr, left, i - 1);  // 递归处理左边子数组
    quickSort(arr, i + 1, right); // 递归处理右边子数组
}

归并排序：

void mergeSort(int arr[], int left, int right) {
    if (left >= right) return;  // 递归边界
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);   // 递归处理左边子数组
    mergeSort(arr, mid + 1, right);  // 递归处理右边子数组
    int i = left, j = mid + 1, k = 0;
    int* temp = new int[right - left + 1];
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else temp[k++] = arr[j++];
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];
    for (int p = 0; p < k; p++) arr[left + p] = temp[p];
    delete[] temp;
}

以上两种算法都是基于递归实现的，其中快速排序利用了分治思想，而归并排序则利用了合并思想。在使用时需要注意数组下标边界问题和空间复杂度问题。