快速排序和归并排序的比较

1. 基本原理比较
   • 快速排序：
     • 基于分治策略。它选择一个基准元素（pivot），通过一趟排序将待排序序列分割成两部分，其中左边部分的元素都小于等于基准元素，右边部分的元素都大于等于基准元素。然后对这两部分分别进行快速排序，递归地重复这个过程，直到整个序列有序。例如，对于序列[4, 7, 2, 9, 1]，如果选择4作为基准元素，经过一趟排序后可能得到[1, 2, 4, 9, 7]，然后再对[1, 2]和[9, 7]分别进行排序。
   • 归并排序：
     • 同样是分治思想。它将数组不断地二等分，直到子数组只有一个元素（认为单个元素是有序的）。然后将这些子数组两两合并，在合并过程中，将两个有序子数组的元素按顺序比较并放入新的数组，使得合并后的数组也是有序的。例如，对于序列[4, 7, 2, 9, 1]，先分为[4, 7]和[2, 9, 1]，再细分，最后合并时会按照顺序合并这些子数组，最终得到有序序列。
2. 时间复杂度比较
   • 快速排序：
     • 平均时间复杂度是。在每次划分比较均匀的理想情况下，每次划分可以将序列分成两个大小相近的子序列，这样递归树的高度为，每层的比较次数总和为，所以时间复杂度为。
     • 最坏情况时间复杂度是。当序列已经有序或者逆序，并且每次选择的基准元素是序列的最大值或者最小值时，每次划分只能得到一个比原序列少一个元素的子序列和一个空序列，这样就会导致比较次数达到，时间复杂度为。
   • 归并排序：
     • 时间复杂度稳定为。因为它总是将序列均匀地划分，递归树的高度始终为，每次合并操作的时间复杂度为（需要遍历合并所有元素），所以总的时间复杂度为。
3. 空间复杂度比较
   • 快速排序：
     • 空间复杂度为（平均情况）。这是因为在递归调用过程中，栈需要存储每层递归的信息，在平均情况下，递归深度为，所以空间复杂度为。
     • 最坏情况空间复杂度为。当递归深度达到时（例如刚才提到的最坏时间复杂度的情况），需要的空间来存储栈信息。
   • 归并排序：
     • 空间复杂度为。因为在合并过程中，需要使用额外的临时数组来存储合并后的元素，临时数组的大小与原数组大小相同，所以空间复杂度为。
4. 稳定性比较
   • 快速排序：
     • 是不稳定的排序算法。例如序列[4, 4, 2]，如果选择第一个4作为基准元素，经过排序后可能得到[2, 4, 4]，相同元素的相对位置发生了改变。
   • 归并排序：
     • 是稳定的排序算法。在合并两个子数组时，如果两个子数组中有相同的元素，先放入合并数组的是前面子数组中的元素，这样就保证了相同元素的相对位置不变。
5. 适用场景比较
   • 快速排序：
     • 适用于数据量较大且对空间要求比较严格，并且不要求排序稳定性的情况。因为它的平均性能很好，而且空间复杂度在平均情况下相对较低。另外，在内存层次结构中，快速排序的顺序访问模式在某些硬件上可能更高效。
   • 归并排序：
     • 适用于需要稳定排序的情况，比如对一些数据结构（如链表）排序或者对外部文件排序（可以将文件分成多个小部分排序后再合并）。不过由于它的空间复杂度较高，在空间有限的情况下可能不太合适。

c++实现快速排序代码如下： 

#include <iostream>
#include <vector>

// 交换两个元素的函数
template<typename T>
void swap(T& a, T& b) {
    T temp = a;
    a = b;
    b = temp;
}

// 划分函数，选择一个基准元素，将数组划分为两部分
template<typename T>
int partition(std::vector<T>& arr, int low, int high) {
    T pivot = arr[high];  // 通常选择最后一个元素作为基准元素
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }

    swap(arr[i + 1], arr[high]);
    return i + 1;
}

// 快速排序主函数，采用递归方式进行排序
template<typename T>
void quickSort(std::vector<T>& arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);

        // 对基准元素左边的子数组进行快速排序
        quickSort(arr, low, pivotIndex - 1);

        // 对基准元素右边的子数组进行快速排序
        quickSort(arr, pivotIndex + 1, high);
    }
}

int main() {
    std::vector<int> arr = { 5, 4, 3, 2, 1 };
    int n = arr.size();

    quickSort(arr, 0, n - 1);

    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

c++实现归并排序代码如下： 

#include <iostream>
#include <vector>

// 合并两个已排序的子数组
template<typename T>
void merge(std::vector<T>& arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    // 创建临时数组来存储两个子数组
    std::vector<T> leftArr(n1);
    std::vector<T> rightArr(n2);

    // 将数据复制到临时数组
    for (int i = 0; i < n1; ++i) {
        leftArr[i] = arr[left + i];
    }
    for (int j = 0; j < n2; ++j) {
        rightArr[j] = arr[mid + 1 + j];
    }

    // 合并临时数组回原数组的索引
    int i = 0, j = 0, k = left;

    // 比较并合并两个临时数组中的元素到原数组
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        }
        else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    // 将左临时数组剩余元素复制回原数组
    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    // 将右临时数组剩余元素复制回原数组
    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

// 归并排序主函数，采用递归方式
template<typename T>
void mergeSort(std::vector<T>& arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        // 对左半部分进行归并排序
        mergeSort(arr, left, mid);

        // 对右半部分进行归并排序
        mergeSort(arr, mid + 1, right);

        // 合并两个已排序的子数组
        merge(arr, left, mid, right);
    }
}

int main() {
    std::vector<int> arr = { 5, 4, 3, 2, 1 };
    int n = arr.size();

    mergeSort(arr, 0, n - 1);

    for (int num : arr) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}