{"id":804,"date":"2018-04-09T15:58:14","date_gmt":"2018-04-09T07:58:14","guid":{"rendered":"http:\/\/www.mrtblog.cn\/?p=804"},"modified":"2023-03-10T21:54:26","modified_gmt":"2023-03-10T13:54:26","slug":"%e3%80%90c%e3%80%91%e5%87%a0%e4%b8%aa%e5%b8%b8%e8%a7%81%e7%9a%84%e7%ae%80%e5%8d%95%e6%8e%92%e5%ba%8f%e7%ae%97%e6%b3%95","status":"publish","type":"post","link":"http:\/\/www.mrtblog.cn\/?p=804","title":{"rendered":"\u3010C++\u3011\u51e0\u4e2a\u5e38\u89c1\u7684\u7b80\u5355\u6392\u5e8f\u7b97\u6cd5"},"content":{"rendered":"
<\/span> 1,649<\/span> Views<\/span><\/div>

\u5148\u7ed9\u7ed3\u8bba\uff0c\u968f\u673a\u51fa10000\u4e2a0-100000\u7684\u6570\u5b57\u540e\uff0c\u5404\u7b97\u6cd5\u7684\u6d88\u8017\u5982\u4e0b(swap_counts\u8868\u793a\u4ea4\u6362\u6216\u62f7\u8d1d\u6b21\u6570, compare_counts\u8868\u793a\u6bd4\u8f83\u6b21\u6570)<\/p>\n\n\n\n\n\n\n\n\n\n
Function<\/td>\nswap_counts<\/td>\ncompare_counts<\/td>\n<\/tr>\n
bubbleSort(\u5192\u6ce1\u6392\u5e8f)<\/td>\n24952888<\/td>\n49993404<\/td>\n<\/tr>\n
insertSort(\u76f4\u63d2\u6392\u5e8f)<\/td>\n24962888<\/td>\n24962883<\/td>\n<\/tr>\n
heapSort(\u5806\u6392\u5e8f)<\/td>\n17886448<\/td>\n24100914<\/td>\n<\/tr>\n
quickSort(\u5feb\u901f\u6392\u5e8f)<\/td>\n69039<\/td>\n173996<\/td>\n<\/tr>\n
mergeSort(\u5f52\u5e76\u6392\u5e8f)<\/td>\n267232<\/td>\n120493<\/td>\n<\/tr>\n
bucketSort(\u6876\u6392\u5e8f)<\/td>\n80640<\/td>\n132267<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n

sort_helper.h<\/strong><\/p>\n

#pragma once\n#include <iostream>\n#include <vector>\n\n\nenum INIT_MODE\n{\n    INIT_MODE_RAND = 1,\/\/\u968f\u673a\n    INIT_MODE_SORT = 2,\/\/\u5df2\u6392\u5e8f\n    INIT_MODE_REVERSE = 3,\/\/\u9006\u6392\u5e8f\n};\nclass SortHelper {\npublic:\n    void InitData();\n    SortHelper(int iInitMode, int iInitNum = 50, int iNumMin = 0, int iNumMax = 100, uint32_t iRandSeed = 0):\n        m_initmode(iInitMode), m_initnum(iInitNum), m_inummin(iNumMin), m_inummax(iNumMax), m_randseed(iRandSeed)\n    {\n        InitData();\n    };\n    void print(std::string name);\npublic:\n    void bubbleSort();\n    void insertSort();\n    void heapSort();\n    void quickSort();\n    void mergeSort();\n    void bucketSort();\nprivate:\n    void swap(int& a, int& b);\n    void copy(int& a, const int& val);\n    void push(std::vector<int> &a, const int& val);\n    void adjust(int loc, int n);\n    void QuickSortFunc(std::vector<int> &arr, int low, int high);\n    int Partition(std::vector<int> &arr, int low, int high);\n    void MergeSortFunc(std::vector<int> &arr, int low, int high);\n    void MergeSortArr(std::vector<int> &arr, int low, int mid, int high);\nprivate:\n    int m_swapcounts;\/\/\u4ea4\u6362\u6b21\u6570\n    int m_compcounts;\/\/\u6bd4\u8f83\u6b21\u6570\n    std::vector<int> m_arr;\/\/\u5f85\u6392\u5e8f\u6570\u7ec4\n    int m_initmode;\n    int m_initnum;\n    int m_inummin;\n    int m_inummax;\n    uint32_t m_randseed;\n};<\/code><\/pre>\n
sort_helper.cpp<\/strong><\/p>\n
#include "sort_helper.h"\n#include <algorithm>\n#include <string>\n\nvoid SortHelper::InitData()\n{\n    m_swapcounts = 0;\n    m_compcounts = 0;\n    m_arr.clear();\n    srand(m_randseed);\n    for (int i = 0; i < m_initnum; ++i)\n    {\n        int val = rand() % (m_inummax - m_inummin) + m_inummin;\n        m_arr.push_back(val);\n    }\n    switch (m_initmode)\n    {\n        case INIT_MODE_SORT: sort(m_arr.begin(), m_arr.end()); break;\n        case INIT_MODE_REVERSE: sort(m_arr.begin(), m_arr.end()); reverse(m_arr.begin(), m_arr.end()); break;\n        default:break;\n    }\n}\nvoid SortHelper::print(std::string name)\n{\n    int N = m_arr.size();\n\n    for (int i = 0; i < N; ++i)\n    {\n        if (N < 20 || i % (N \/ 20) == 0)\n        std::cout << m_arr [i]<< " ";\n    }\n    std::cout << std::endl;\n    std::cout << name << ": swap_counts = " << m_swapcounts << ", compare_counts = " << \n    m_compcounts << std::endl;\n}\n\nvoid SortHelper::swap(int& a, int& b)\n{\n    int tmp = a;\n    a = b;\n    b = tmp;\n    m_swapcounts++;\n}\nvoid SortHelper::copy(int& a, const int& val)\n{\n    a = val;\n    m_swapcounts++;\n}\nvoid SortHelper::push(std::vector<int> &a, const int& val)\n{\n    a.push_back(val);\n    m_swapcounts++;\n}\nvoid SortHelper::adjust(int loc, int n)\n{\n    int left = loc * 2 + 1;\n    int right = (loc + 1) * 2;\n    m_compcounts += (left < n) ? 1 : 0;\n    if (left < n && m_arr[loc] < m_arr[left])\n    {\n        swap(m_arr[left], m_arr[loc]);\n        adjust(left, n);\n    }\n    m_compcounts += (right < n) ? 1 : 0;\n    if (right < n && m_arr[loc] < m_arr[right])\n    {\n        swap(m_arr[right], m_arr[loc]);\n        adjust(right, n);\n    }\n}\nint SortHelper::Partition(std::vector<int> &arr, int low, int high)\n{\n    int val = arr[low];\n    while (low < high)\n    {\n        while (low < high && arr[high] >= val)\n        {\n            --high; m_compcounts++;\n        }\n        copy(arr[low], arr[high]);\n        while (low < high && arr[low] <= val)\n        {\n            ++low; m_compcounts++;\n        }\n        copy(arr[high], arr[low]);\n    }\n    copy(arr[low], val);\n    return low;\n}\nvoid SortHelper::QuickSortFunc(std::vector<int> &arr, int low, int high)\n{\n    if (low < high && high < m_arr.size())\n    {\n        int pivot = Partition(arr, low, high);\n        QuickSortFunc(arr, pivot + 1, high);\n        QuickSortFunc(arr, low, pivot - 1);\n    }\n}\nvoid SortHelper::MergeSortArr(std::vector<int> &arr, int low, int mid, int high)\n{\n    std::vector<int> tmp;\n    int idx1 = low;\n    int idx2 = mid + 1;\n    while (idx1 <= mid && idx2 <= high)\n    {\n        int val = arr[idx1] < arr[idx2] ? arr[idx1++] : arr[idx2++];\n        push(tmp, val);\n        m_compcounts++;\n    }\n    while (idx1 <= mid)\n    {\n        push(tmp, arr[idx1++]);\n    }\n    while (idx2 <= high)\n    {\n        push(tmp, arr[idx2++]);\n    }\n    for (int i = 0; i < tmp.size(); ++i, low++)\n    {\n        copy(arr[low], tmp[i]);\n    }\n}\nvoid SortHelper::MergeSortFunc(std::vector<int> &arr, int low, int high)\n{\n    if (low < high && high < m_arr.size())\n    {\n        int mid = (low + high) \/ 2;\n        MergeSortFunc(arr, low, mid);\n        MergeSortFunc(arr, mid + 1, high);\n        MergeSortArr(arr, low, mid, high);\n    }\n}\n\nvoid SortHelper::bubbleSort()\n{\n    InitData();\n    int N = m_arr.size();\n    for (int i = 0; i < N; ++i)\n    {\n        int flag = 0;\n        int tmp = m_arr[i];\n        for (int j = N - 1; j > i; --j)\n        {\n            m_compcounts++;\n            if (m_arr[j] < m_arr[j - 1])\n            {\n                flag = 1;\n                swap(m_arr[j], m_arr[j - 1]);\n            }\n        }\n        if (flag == 0)\n            break;\n    }\n    print("bubbleSort");\n}\n\nvoid SortHelper::insertSort()\n{\n    InitData();\n    int N = m_arr.size();\n    for (int i = 0, j = 0; i < N; ++i)\n    {\n        int tmp = m_arr[i];\n        for (j = i - 1; j >= 0; --j)\n        {\n            m_compcounts++;\n            if (tmp < m_arr[j])\n                copy(m_arr[j + 1], m_arr[j]);\n            else\n                break;\n        }\n        copy(m_arr[j + 1], tmp);\n    }\n    print("insertSort");\n}\n\nvoid SortHelper::heapSort()\n{\n    InitData();\n    int N = m_arr.size();\n    for (int i = N \/ 2 - 1; i >= 0; --i)\n    {\n        adjust(i, N);\n    }\n    for (int i = N - 1; i >= 0; --i)\n    {\n        swap(m_arr[i], m_arr[0]);\n        adjust(0, i);\n    }\n    print("heapSort");\n}\n\nvoid SortHelper::quickSort()\n{\n    InitData();\n    int low = 0;\n    int high = m_arr.size();\n    QuickSortFunc(m_arr, low, high - 1);\n    print("quickSort");\n}\nvoid SortHelper::mergeSort()\n{\n    InitData();\n    int low = 0;\n    int high = m_arr.size();\n    MergeSortFunc(m_arr, low, high - 1);\n    print("mergeSort");\n}\nvoid SortHelper::bucketSort()\n{\n    InitData();\n\n    std::vector<std::vector<int> > bucket;\n    int bucket_num = 10;\/\/10\u4e2a\u6876\n    int bais = (m_inummax - m_inummin) \/ bucket_num;\/\/\u533a\u95f4\u6bb5\n    for (int i = 0; i < bucket_num; ++i)\n    {\n        bucket.push_back({});\n    }\n    for (int i = 0; i < m_arr.size(); ++i)\n    {\n        int val = m_arr[i];\n        int bucketID = (val - m_inummin) \/ bais;\/\/\u770b\u770b\u5728\u7b2c\u51e0\u4e2a\u533a\u95f4\u6bb5\n        push(bucket[bucketID], val);\n    }\n    for (int i = 0, k = 0; i < bucket_num; ++i)\n    {\n        QuickSortFunc(bucket[i], 0, bucket[i].size() - 1);\n        if (bucket[i].size() > 0)\n        {\n            for (int j = 0; j < bucket[i].size(); ++j)\n            {\n                copy(m_arr[k++], bucket[i][j]);\n            }\n        }\n    }\n    print("bucketSort");\n}\n<\/code><\/pre>\n
main.cpp<\/strong><\/p>\n
#include<iostream>\n#include<memory>\n#include <algorithm>\n#include<vector>\n#include "sort_helper.h"\n\nusing namespace std;\n\nint main(int argc, char **argv) {\n    int model = INIT_MODE_RAND;\n    SortHelper ss(model, 30, 0, 100, 1);\n    ss.print("Init");\n\n    ss.bubbleSort();\n    ss.insertSort();\n    ss.heapSort();\n    ss.quickSort();\n    ss.mergeSort();\n    ss.bucketSort();\n\n    return 0;\n}\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
1,649 Views\u5148\u7ed9\u7ed3\u8bba\uff0c\u968f\u673a\u51fa10000\u4e2a0-100000\u7684\u6570\u5b57\u540e\uff0c\u5404\u7b97\u6cd5\u7684\u6d88\u8017\u5982\u4e0b(swap_cou […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[109],"tags":[],"class_list":["post-804","post","type-post","status-publish","format-standard","hentry","category-109"],"_links":{"self":[{"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts\/804","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=804"}],"version-history":[{"count":4,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts\/804\/revisions"}],"predecessor-version":[{"id":1118,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=\/wp\/v2\/posts\/804\/revisions\/1118"}],"wp:attachment":[{"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=804"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=804"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.mrtblog.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=804"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}