【C++】几个常见的简单排序算法

先给结论，随机出10000个0-100000的数字后，各算法的消耗如下(swap_counts表示交换或拷贝次数, compare_counts表示比较次数)

sort_helper.h

#pragma once
#include <iostream>
#include <vector>


enum INIT_MODE
{
    INIT_MODE_RAND = 1,//随机
    INIT_MODE_SORT = 2,//已排序
    INIT_MODE_REVERSE = 3,//逆排序
};
class SortHelper {
public:
    void InitData();
    SortHelper(int iInitMode, int iInitNum = 50, int iNumMin = 0, int iNumMax = 100, uint32_t iRandSeed = 0):
        m_initmode(iInitMode), m_initnum(iInitNum), m_inummin(iNumMin), m_inummax(iNumMax), m_randseed(iRandSeed)
    {
        InitData();
    };
    void print(std::string name);
public:
    void bubbleSort();
    void insertSort();
    void heapSort();
    void quickSort();
    void mergeSort();
    void bucketSort();
private:
    void swap(int& a, int& b);
    void copy(int& a, const int& val);
    void push(std::vector<int> &a, const int& val);
    void adjust(int loc, int n);
    void QuickSortFunc(std::vector<int> &arr, int low, int high);
    int Partition(std::vector<int> &arr, int low, int high);
    void MergeSortFunc(std::vector<int> &arr, int low, int high);
    void MergeSortArr(std::vector<int> &arr, int low, int mid, int high);
private:
    int m_swapcounts;//交换次数
    int m_compcounts;//比较次数
    std::vector<int> m_arr;//待排序数组
    int m_initmode;
    int m_initnum;
    int m_inummin;
    int m_inummax;
    uint32_t m_randseed;
};

sort_helper.cpp

#include "sort_helper.h"
#include <algorithm>
#include <string>

void SortHelper::InitData()
{
    m_swapcounts = 0;
    m_compcounts = 0;
    m_arr.clear();
    srand(m_randseed);
    for (int i = 0; i < m_initnum; ++i)
    {
        int val = rand() % (m_inummax - m_inummin) + m_inummin;
        m_arr.push_back(val);
    }
    switch (m_initmode)
    {
        case INIT_MODE_SORT: sort(m_arr.begin(), m_arr.end()); break;
        case INIT_MODE_REVERSE: sort(m_arr.begin(), m_arr.end()); reverse(m_arr.begin(), m_arr.end()); break;
        default:break;
    }
}
void SortHelper::print(std::string name)
{
    int N = m_arr.size();

    for (int i = 0; i < N; ++i)
    {
        if (N < 20 || i % (N / 20) == 0)
        std::cout << m_arr [i]<< " ";
    }
    std::cout << std::endl;
    std::cout << name << ": swap_counts = " << m_swapcounts << ", compare_counts = " << 
    m_compcounts << std::endl;
}

void SortHelper::swap(int& a, int& b)
{
    int tmp = a;
    a = b;
    b = tmp;
    m_swapcounts++;
}
void SortHelper::copy(int& a, const int& val)
{
    a = val;
    m_swapcounts++;
}
void SortHelper::push(std::vector<int> &a, const int& val)
{
    a.push_back(val);
    m_swapcounts++;
}
void SortHelper::adjust(int loc, int n)
{
    int left = loc * 2 + 1;
    int right = (loc + 1) * 2;
    m_compcounts += (left < n) ? 1 : 0;
    if (left < n && m_arr[loc] < m_arr[left])
    {
        swap(m_arr[left], m_arr[loc]);
        adjust(left, n);
    }
    m_compcounts += (right < n) ? 1 : 0;
    if (right < n && m_arr[loc] < m_arr[right])
    {
        swap(m_arr[right], m_arr[loc]);
        adjust(right, n);
    }
}
int SortHelper::Partition(std::vector<int> &arr, int low, int high)
{
    int val = arr[low];
    while (low < high)
    {
        while (low < high && arr[high] >= val)
        {
            --high; m_compcounts++;
        }
        copy(arr[low], arr[high]);
        while (low < high && arr[low] <= val)
        {
            ++low; m_compcounts++;
        }
        copy(arr[high], arr[low]);
    }
    copy(arr[low], val);
    return low;
}
void SortHelper::QuickSortFunc(std::vector<int> &arr, int low, int high)
{
    if (low < high && high < m_arr.size())
    {
        int pivot = Partition(arr, low, high);
        QuickSortFunc(arr, pivot + 1, high);
        QuickSortFunc(arr, low, pivot - 1);
    }
}
void SortHelper::MergeSortArr(std::vector<int> &arr, int low, int mid, int high)
{
    std::vector<int> tmp;
    int idx1 = low;
    int idx2 = mid + 1;
    while (idx1 <= mid && idx2 <= high)
    {
        int val = arr[idx1] < arr[idx2] ? arr[idx1++] : arr[idx2++];
        push(tmp, val);
        m_compcounts++;
    }
    while (idx1 <= mid)
    {
        push(tmp, arr[idx1++]);
    }
    while (idx2 <= high)
    {
        push(tmp, arr[idx2++]);
    }
    for (int i = 0; i < tmp.size(); ++i, low++)
    {
        copy(arr[low], tmp[i]);
    }
}
void SortHelper::MergeSortFunc(std::vector<int> &arr, int low, int high)
{
    if (low < high && high < m_arr.size())
    {
        int mid = (low + high) / 2;
        MergeSortFunc(arr, low, mid);
        MergeSortFunc(arr, mid + 1, high);
        MergeSortArr(arr, low, mid, high);
    }
}

void SortHelper::bubbleSort()
{
    InitData();
    int N = m_arr.size();
    for (int i = 0; i < N; ++i)
    {
        int flag = 0;
        int tmp = m_arr[i];
        for (int j = N - 1; j > i; --j)
        {
            m_compcounts++;
            if (m_arr[j] < m_arr[j - 1])
            {
                flag = 1;
                swap(m_arr[j], m_arr[j - 1]);
            }
        }
        if (flag == 0)
            break;
    }
    print("bubbleSort");
}

void SortHelper::insertSort()
{
    InitData();
    int N = m_arr.size();
    for (int i = 0, j = 0; i < N; ++i)
    {
        int tmp = m_arr[i];
        for (j = i - 1; j >= 0; --j)
        {
            m_compcounts++;
            if (tmp < m_arr[j])
                copy(m_arr[j + 1], m_arr[j]);
            else
                break;
        }
        copy(m_arr[j + 1], tmp);
    }
    print("insertSort");
}

void SortHelper::heapSort()
{
    InitData();
    int N = m_arr.size();
    for (int i = N / 2 - 1; i >= 0; --i)
    {
        adjust(i, N);
    }
    for (int i = N - 1; i >= 0; --i)
    {
        swap(m_arr[i], m_arr[0]);
        adjust(0, i);
    }
    print("heapSort");
}

void SortHelper::quickSort()
{
    InitData();
    int low = 0;
    int high = m_arr.size();
    QuickSortFunc(m_arr, low, high - 1);
    print("quickSort");
}
void SortHelper::mergeSort()
{
    InitData();
    int low = 0;
    int high = m_arr.size();
    MergeSortFunc(m_arr, low, high - 1);
    print("mergeSort");
}
void SortHelper::bucketSort()
{
    InitData();

    std::vector<std::vector<int> > bucket;
    int bucket_num = 10;//10个桶
    int bais = (m_inummax - m_inummin) / bucket_num;//区间段
    for (int i = 0; i < bucket_num; ++i)
    {
        bucket.push_back({});
    }
    for (int i = 0; i < m_arr.size(); ++i)
    {
        int val = m_arr[i];
        int bucketID = (val - m_inummin) / bais;//看看在第几个区间段
        push(bucket[bucketID], val);
    }
    for (int i = 0, k = 0; i < bucket_num; ++i)
    {
        QuickSortFunc(bucket[i], 0, bucket[i].size() - 1);
        if (bucket[i].size() > 0)
        {
            for (int j = 0; j < bucket[i].size(); ++j)
            {
                copy(m_arr[k++], bucket[i][j]);
            }
        }
    }
    print("bucketSort");
}

main.cpp

#include<iostream>
#include<memory>
#include <algorithm>
#include<vector>
#include "sort_helper.h"

using namespace std;

int main(int argc, char **argv) {
    int model = INIT_MODE_RAND;
    SortHelper ss(model, 30, 0, 100, 1);
    ss.print("Init");

    ss.bubbleSort();
    ss.insertSort();
    ss.heapSort();
    ss.quickSort();
    ss.mergeSort();
    ss.bucketSort();

    return 0;
}