(五)C++中的排序函数性能比较

---

欢迎访问个人网络日志🌹🌹知行空间🌹🌹

---

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

1.qsort函数

需包含头文件#include

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

• 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 
// #include 
// #include 
// #include 

// using namespace std;

// #endif // __TEST_SORT__H__
#include 

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 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

2.sort函数

需包含头文件#include

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

#include 
#include 
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;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

3.qsort与sort性能测试

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

// #include 
// #include 
// #include 
// #include 
// #include 
// #include 

// 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 &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 

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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158

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

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

---

欢迎访问个人网络日志🌹🌹知行空间🌹🌹

---

参考资料

• 1.https://cplusplus.com/reference/algorithm/sort/
• 2.https://cplusplus.com/reference/cstdlib/qsort/
• 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