C++中的SORT算法比较

C++中可用的排序算法有两个，一个是cstdlib中的qsort函数，另外一个是STL中的sort函数。

# 1.`qsort`函数

需包含头文件#include<cstdlib>

void qsort (void* base, size_t num, size_t size,
            int (*compar)(const 
            void*,const void*));

base:排序数组的头元素指针，被转成了void *类型
num:数组元素个数
size:数组中每个元素占用字节数
compar:函数指针
int compar (const void* p1, const void* p2);降序*p1-*p2，升序*p2-*p1。

*p1 -*p2返回值含义

<0 *p1移到*p2前面

0 *p1与*p2等价

>0 *p1移到*p2后面

`p1 -p2`返回值	含义
<0	`p1`移到`p2`前面
0	`p1`与`p2`等价
>0	`p1`移到`p2`后面

// test_sort.h
// #ifndef __TEST_SORT__H__
// #define __TEST_SORT__H__

// #include <cstdlib>
// #include <algorithm>
// #include <vector>
// #include <iostream>

// using namespace std;

// #endif // __TEST_SORT__H__
#include <test_sort.h>

int compareAB(const void *a, const void *b)
{
    return (*(int *)a - *(int *)b);
}
// 升序
int compareBA(const void *a, const void *b)
{
    return (*(int *)b - *(int *)a);
}
// 降序
void printArray(int*p, size_t n) {
    for (size_t n = 0; n < 6; n++)
        cout << p[n] << " ";
    cout << endl;
}

int main()
{   size_t num = 6;
    int values[num] = {40, 10, 100, 90, 20, 25};
    qsort(values, num, sizeof(int), compareAB);
    printArray(values, num);

    qsort(values, num, sizeof(int), compareBA);
    printArray(values, num);

    return 0;
}
// 10 20 25 40 90 100 
// 100 90 40 25 20 10

# 2.`sort`函数

需包含头文件#include<algorithm>


default (1)	`template <class RandomAccessIterator>` `
void sort (RandomAccessIterator first, RandomAccessIterator last);`
custom (2)	`template <class RandomAccessIterator, class Compare>` `void sort (RandomAccessIterator first, RandomAccessIterator last, Compare comp);`

first/last：迭代器的开始和结束位置
comp返回布尔类型的函数，接受两个入参

#include <iostream>
#include <algorithm>
using namespace std;

void printArray(int*p, size_t n) {
    for (size_t n = 0; n < 6; n++)
        cout << p[n] << " ";
    cout << endl;
}

int main()
{
    size_t num = 6;
    int values[num] = {40, 10, 100, 90, 20, 25};
    // 升序
    sort(values, values + num);
    printArray(values, num);
    // 升序
    sort(values, values + num, [](int x, int y) { return x < y; });
    printArray(values, num);
    // 降序
    sort(values, values + num, [](int x, int y) { return x > y; });
    printArray(values, num);

    return 0;
}

# 3.qsort与sort性能测试

// main.h
// #ifndef __MAIN_H_
// #define __MAIN_H_

// #include <iostream>
// #include <cstdlib>
// #include <ctime>
// #include <chrono>
// #include <algorithm>
// #include <vector>

// int compare(const void *a, const void *b);
// int compare(int a, int b);

// double qsortCompare(int *p, size_t n);
// double sortCompare(int *p, size_t n);
// double sortCompare(std::vector<int> &p);

// size_t partition(int *p, size_t begin, size_t end);
// double quickSort(int *p, int begin, int end);
// double myQuickSort(int *p, int n);
// #endif // __MAIN__
#include <main.h>

int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

// c qsort
double qsortCompare(int *p, size_t n) {
    std::chrono::steady_clock::time_point t1 = std::chrono::steady_clock::now();
    qsort(p, n, sizeof(int), compare);
    std::chrono::steady_clock::time_point t2 = std::chrono::steady_clock::now();
    std::chrono::duration<double> dt = std::chrono::duration_cast<std::chrono::duration<double>>(t2 -t1);
    return dt.count() * 1000;
}

// stl sort
double sortCompare(int *p, size_t n) {
    std::chrono::steady_clock::time_point t1 = std::chrono::steady_clock::now();
    std::sort(p, p+n, [](int x, int y) { return x < y; });
    std::chrono::steady_clock::time_point t2 = std::chrono::steady_clock::now();
    std::chrono::duration<double> dt = std::chrono::duration_cast<std::chrono::duration<double>>(t2 -t1);
    return dt.count() * 1000;
}

double sortCompare(std::vector<int> &p) {
    std::chrono::steady_clock::time_point t1 = std::chrono::steady_clock::now();
    std::sort(p.begin(), p.end(), [](int x, int y) { return x < y; });
    std::chrono::steady_clock::time_point t2 = std::chrono::steady_clock::now();
    std::chrono::duration<double> dt = std::chrono::duration_cast<std::chrono::duration<double>>(t2 -t1);
    return dt.count() * 1000;
}

void quickSortFast(int *p, int begin, int end)
{
    if(begin >= end)return;
    int pivot = (p[end] + p[begin]) / 2, i = begin, j = end;
    while (i <= j) {
        for(;p[i] < pivot;) {
            ++i;
        }
        for(;p[j] > pivot;) {
            --j;
        }
        if(i <= j) {
            std::swap(p[i], p[j]);
            ++i;
            --j;
        }
    }
    quickSortFast(p, begin, j);
    quickSortFast(p, i, end);
}

size_t partition(int *p, size_t begin, size_t end)
{
    int pivot = p[end];
    while(begin < end) {
        while(begin < end && p[begin] <= pivot) {
            ++begin;
        }
        std::swap(p[end], p[begin]);
        while(begin < end && pivot <= p[begin]) {
            --end;
        }
        std::swap(p[end], p[begin]);
    }
    std::swap(p[end], pivot);
    return end;
}

void quickSortSlow(int *p, size_t begin, size_t end) {
    if(begin < end) {
        size_t pivot_index = partition(p, begin, end);
        quickSortSlow(p, begin, pivot_index - 1);
        quickSortSlow(p, pivot_index + 1, end);
    }
}

// quick sort
double myQuickSort(int *p, int n) {
    std::chrono::steady_clock::time_point t1 = std::chrono::steady_clock::now();
    quickSortFast(p, 0, n -1);
    std::chrono::steady_clock::time_point t2 = std::chrono::steady_clock::now();
    std::chrono::duration<double> dt = std::chrono::duration_cast<std::chrono::duration<double>>(t2 -t1);
    return dt.count() * 1000;
}

int main(int argc, char **argv)
{
    srand(time(NULL));
    size_t n = 100000;
    int *p = new int[n];
    double dtSum = 0.0;
    const int EXP_TIMES = 10000;
    for(auto i = 0; i < EXP_TIMES; i++) {
        for (int i = 0; i < n; i++) {
            p[i] = rand();
        }
        dtSum += qsortCompare(p, n);
    }
    std::cout << "C qsort take " << dtSum / EXP_TIMES << " ms for " << n << " sort." << std::endl;

    dtSum = 0;
    for(auto i = 0; i < EXP_TIMES; i++) {
        for (int i = 0; i < n; i++) {
            p[i] = rand();
        }
        dtSum += sortCompare(p, n);
    }
    std::cout << "STL array sort take " << dtSum / EXP_TIMES << " ms for " << n << " sort." << std::endl;

    dtSum = 0;
    for(auto i = 0; i < EXP_TIMES; i++) {
        for (int i = 0; i < n; i++) {
            p[i] = rand();
        }
        std::vector<int> arr(p, p+n);
        dtSum += sortCompare(arr);
    }
    std::cout << "STL vector sort take " << dtSum / EXP_TIMES << " ms for " << n << " sort." << std::endl;

    dtSum = 0;
    for(auto i = 0; i < EXP_TIMES; i++) {
        for (int i = 0; i < n; i++) {
            p[i] = rand() % 1000;
        }
        dtSum += myQuickSort(p, n);
    }
    std::cout << "Custom quick sort take " << dtSum / EXP_TIMES << " ms for " << n << " sort." << std::endl;
    delete[] p;
    return 0;
}
// C qsort take 21.4219 ms for 100000 sort.
// STL array sort take 32.684 ms for 100000 sort.
// STL vector sort take 57.5976 ms for 100000 sort.
// Custom quick sort take 20.2387 ms for 100000 sort.

上面的测试是随机生成含有10万个int元素的数组，每个方法测试1万次后的平均性能，可见qsort和自己实现的quickSort性能相当，stl sort性能比较差，且迭代数组时比迭代vector容器要快。

STL sort的源码实现中，数据量大时采用QuickSort快排算法，然后分治部分的数据量小于某个门槛（16），为避免QuickSort快排的递归调用带来过大的额外负荷，就改用Insertion Sort插入排序。如果递归层次过深，还会改用HeapSort堆排序。

# 参考资料

1.https://cplusplus.com/reference/algorithm/sort/ (opens new window)

2.https://cplusplus.com/reference/cstdlib/qsort/ (opens new window)

3.https://zhuanlan.zhihu.com/p/36274119#:~:text=STL%E7%9A%84sort%E7%AE%97%E6%B3%95%EF%BC%8C%E6%95%B0%E6%8D%AE,%E6%94%B9%E7%94%A8HeapSort%E5%A0%86%E6%8E%92%E5%BA%8F%E3%80%82 (opens new window)

← C++的常用容器简析 C++中的static及文件包含 →

# 1.qsort函数

# 2.sort函数

# 3.qsort与sort性能测试

# 参考资料

# 1.`qsort`函数

# 2.`sort`函数