[数据结构与算法] 几大排序算法的c++实现

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 几大排序算法的c++实现 -> 正文阅读

[数据结构与算法]几大排序算法的c++实现

归并排序

void mergeSort(vector<int>& data) {
    int len = data.size();
    vector<int> dataTemp(len, 0);
    mergeSortCore(data, dataTemp, 0, len - 1);
}

void mergeSortCore(vector<int>& data, vector<int>& dataTemp, int low, int high) {
    if (low >= high)
        return;
    int len = high - low, mid = low + len / 2;
    int start1 = low, end1 = mid, start2 = mid + 1, end2 = high;
    mergeSortCore(data, dataTemp, start1, end1);
    mergeSortCore(data, dataTemp, start2, end2);
    int index = low;
    while (start1 <= end1 && start2 <= end2) {
        dataTemp[index++] =
            data[start1] < data[start2] ? data[start1++] : data[start2++];
    }
    while (start1 <= end1) {
        dataTemp[index++] = data[start1++];
    }
    while (start2 <= end2) {
        dataTemp[index++] = data[start2++];
    }
    for (index = low; index <= high; ++index) {
        data[index] = dataTemp[index];
    }
}

快速排序

    void quickSort(vector<int>& arr, int l, int r) {
        // 子数组长度为 1 时终止递归
        if (l >= r) return;
        // 哨兵划分操作（以 arr[l] 作为基准数）
        int i = l, j = r;  //arr[l]是哨兵值
        while (i < j) {
            while (i < j && arr[j] >= arr[l]) j--;
            while (i < j && arr[i] <= arr[l]) i++;
            swap(arr[i], arr[j]);
        }//循环结束时i=j
        swap(arr[i], arr[l]);
        // 递归左（右）子数组执行哨兵划分
        quickSort(arr, l, i - 1);
        quickSort(arr, i + 1, r);
    }