一，单路快排
1.测试用例：
1 #ifndef INC_06_QUICK_SORT_DEAL_WITH_NEARLY_ORDERED_ARRAY_SORTTESTHELPER_H
2 #define INC_06_QUICK_SORT_DEAL_WITH_NEARLY_ORDERED_ARRAY_SORTTESTHELPER_H
3 #include <iostream>
4 #include <algorithm>
5 #include <string>
6 #include <ctime>
7 #include <cassert>
8 using namespace std;
9 namespace SortTestHelper {
10
// 生成有n个元素的随机数组,每个元素的随机范围为[rangeL, rangeR]
11
int *generateRandomArray(int n, int range_l, int range_r) {
12
int *arr = new int[n];
13
srand(time(NULL));
14
for (int i = 0; i < n; i++)
15
arr[i] = rand() % (range_r - range_l + 1) + range_l;
16
return arr;
17 }
18
// 生成一个近乎有序的数组
19
// 首先生成一个含有[0...n-1]的完全有序数组, 之后随机交换swapTimes对数据
20
// swapTimes定义了数组的无序程度
21
int *generateNearlyOrderedArray(int n, int swapTimes){
22
int *arr = new int[n];
23
for(int i = 0 ; i < n ; i ++ )
24
arr[i] = i;
25
srand(time(NULL));
26
for( int i = 0 ; i < swapTimes ; i ++ ){
27
int posx = rand()%n;
28
int posy = rand()%n;
29
swap( arr[posx] , arr[posy] );
30
}
31
return arr;
32 }
33
// 拷贝整型数组a中的所有元素到一个新的数组, 并返回新的数组
34
int *copyIntArray(int a[], int n){
35
int *arr = new int[n];
36
copy(a, a+n, arr);
37
return arr;
38 }
39
// 打印arr数组的所有内容
40
template<typename T>
41
void printArray(T arr[], int n) {
42
for (int i = 0; i < n; i++)
43
cout << arr[i] << " ";
44
cout << endl;
45
46
return;
47 }
48
// 判断arr数组是否有序
49
template<typename T>
50
bool isSorted(T arr[], int n) {
51
for (int i = 0; i < n - 1; i++)
52
if (arr[i] > arr[i + 1])
53
return false;
54
return true;
55 }
56
// 测试sort排序算法排序arr数组所得到结果的正确性和算法运行时间
57
template<typename T>
58
void testSort(const string &sortName, void (*sort)(T[], int), T arr[], int n) {
59
clock_t startTime = clock();
60
sort(arr, n);
61
clock_t endTime = clock();
62
cout << sortName << " : " << double(endTime - startTime) / CLOCKS_PER_SEC << " s"<<endl;
63
assert(isSorted(arr, n));
64
return;
65 }
66 };
67 #endif