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后面
// 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堆排序。

# 参考资料

(adsbygoogle = window.adsbygoogle || []).push({});