O(n*logn)级别的算法之二（快速排序）的三种实现方法详解及其与归并排序的对比
一，单路快排
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
4 #include
5 #include
6 #include
7 #include
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
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
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
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"<
4 #include
5 #include "InsertionSort.h"
6 using namespace std;
7 // 将arr[l...mid]和arr[mid+1...r]两部分进行归并
8 template
9 void __merge(T arr[], int l, int mid, int r){
10 T aux[r-l+1];
11 //T *aux = new T[r-l+1];
12 for( int i = l ; i <= r; i ++ )
13 aux[i-l] = arr[i];
14 // 初始化，i指向左半部分的起始索引位置l；j指向右半部分起始索引位置mid+1
15 int i = l, j = mid+1;
16 for( int k = l ; k <= r; k ++ ){
17 if( i > mid ){ // 如果左半部分元素已经全部处理完毕
18 arr[k] = aux[j-l]; j ++;
19 }
20 else if( j > r ){ // 如果右半部分元素已经全部处理完毕
21 arr[k] = aux[i-l]; i ++;
22 }
23 else if( aux[i-l] < aux[j-l] ) { // 左半部分所指元素 < 右半部分所指元素
24 arr[k] = aux[i-l]; i ++;
25 }
26 else{ // 左半部分所指元素 >= 右半部分所指元素
27 arr[k] = aux[j-l]; j ++;
28 }
29 }
30 //delete[] aux;
31 }
32 // 使用优化的归并排序算法, 对arr[l...r]的范围进行排序
33 template
34 void __mergeSort(T arr[], int l, int r){
35 // 对于小规模数组, 使用插入排序
36 if( r - l <= 15 ){
37 insertionSort(arr, l, r);
38 return;
39 }
40 int mid = (l+r)/2;
41 __mergeSort(arr, l, mid);
42 __mergeSort(arr, mid+1, r);
43 // 对于arr[mid] <= arr[mid+1]的情况,不进行merge
44 // 对于近乎有序的数组非常有效,但是对于一般情况,有一定的性能损失
45 if( arr[mid] > arr[mid+1] )
46 __merge(arr, l, mid, r);
47 }
48 template
49 void mergeSort(T arr[], int n){
50 __mergeSort( arr , 0 , n-1 );
51 }
52 #endif
复制代码
3.优化时要用的插入排序：
复制代码
1 #ifndef INC_06_QUICK_SORT_DEAL_WITH_NEARLY_ORDERED_ARRAY_INSERTIONSORT_H
2 #define INC_06_QUICK_SORT_DEAL_WITH_NEARLY_ORDERED_ARRAY_INSERTIONSORT_H
3 #include
4 #include
5 using namespace std;
6 template
7 void insertionSort(T arr[], int n){
8 for( int i = 1 ; i < n ; i ++ ) {
9 T e = arr[i];
10 int j;
11 for (j = i; j > 0 && arr[j-1] > e; j--)
12 arr[j] = arr[j-1];
13 arr[j] = e;
14 }
15 return;
16 }
17 // 对arr[l...r]范围的数组进行插入排序
18 template
19 void insertionSort(T arr[], int l, int r){
20 for( int i = l+1 ; i <= r ; i ++ ) {
21 T e = arr[i];
22 int j;
23 for (j = i; j > l && arr[j-1] > e; j--)
24 arr[j] = arr[j-1];
25 arr[j] = e;
26 }
27 return;
28 }
29 #endif
复制代码
4.单路快排实现：
复制代码
1 #include
2 #include
3 #include
4 #include "SortTestHelper.h"
5 #include "MergeSort.h"
6 #include "InsertionSort.h"
7 using namespace std;
8 // 对arr[l...r]部分进行partition操作
9 // 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
10 template
11 int _partition(T arr[], int l, int r){
12 // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
13 swap( arr[l] , arr[rand()%(r-l+1)+l] );
14 T v = arr[l];
15 int j = l;
16 for( int i = l + 1 ; i <= r ; i ++ )
17 if( arr[i] < v ){
18 j ++;
19 swap( arr[j] , arr[i] );
20 }
21 swap( arr[l] , arr[j]);
22 return j;
23 }
24 // 对arr[l...r]部分进行快速排序
25 template
26 void _quickSort(T arr[], int l, int r){
27 // 对于小规模数组, 使用插入排序进行优化
28 if( r - l <= 15 ){
29 insertionSort(arr,l,r);
30 return;
31 }
32 int p = _partition(arr, l, r);
33 _quickSort(arr, l, p-1 );
34 _quickSort(arr, p+1, r);
35 }
36 template
37 void quickSort(T arr[], int n){
38 srand(time(NULL));
39 _quickSort(arr, 0, n-1);
40 }
41 // 比较Merge Sort和Quick Sort两种排序算法的性能效率
42 int main() {
43 int n = 100000;
44 // 测试1 一般性测试（随机数）
45 cout<<"Test for random array, size = "<
2 #include
3 #include
4 #include "SortTestHelper.h"
5 #include "MergeSort.h"
6 #include "InsertionSort.h"
7 using namespace std;
8 // 对arr[l...r]部分进行partition操作
9 // 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
10 template
11 int _partition(T arr[], int l, int r){
12 // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
13 swap( arr[l] , arr[rand()%(r-l+1)+l] );
14 T v = arr[l];
15 int j = l;
16 for( int i = l + 1 ; i <= r ; i ++ )
17 if( arr[i] < v ){
18 j ++;
19 swap( arr[j] , arr[i] );
20 }
21 swap( arr[l] , arr[j]);
22 return j;
23 }
24 // 双路快速排序的partition
25 // 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
26 template
27 int _partition2(T arr[], int l, int r){
28 // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
29 swap( arr[l] , arr[rand()%(r-l+1)+l] );
30 T v = arr[l];
31 // arr[l+1...i) <= v; arr(j...r] >= v
32 int i = l+1, j = r;
33 while( true ){
34 // 注意这里的边界, arr[i] < v, 不能是arr[i] <= v
35 while( i <= r && arr[i] < v )
36 i ++;
37 // 注意这里的边界, arr[j] > v, 不能是arr[j] >= v
38 while( j >= l+1 && arr[j] > v )
39 j --;
40 if( i > j )
41 break;
42 swap( arr[i] , arr[j] );
43 i ++;
44 j --;
45 }
46 swap( arr[l] , arr[j]);
47 return j;
48 }
49 // 对arr[l...r]部分进行快速排序
50 template
51 void _quickSort(T arr[], int l, int r){
52 // 对于小规模数组, 使用插入排序进行优化
53 if( r - l <= 15 ){
54 insertionSort(arr,l,r);
55 return;
56 }
57 // 调用双路快速排序的partition
58 int p = _partition2(arr, l, r);
59 _quickSort(arr, l, p-1 );
60 _quickSort(arr, p+1, r);
61 }
62 template
63 void quickSort(T arr[], int n){
64 srand(time(NULL));
65 _quickSort(arr, 0, n-1);
66 }
67 // 比较Merge Sort和双路快速排序两种排序算法的性能效率
68 int main() {
69 int n = 100000;
70 // 测试1 一般性测试
71 cout<<"Test for random array, size = "<
#include
#include
#include "InsertionSort.h"
using namespace std;
// 对arr[l...r]部分进行partition操作
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
template
int _partition(T arr[], int l, int r){
// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
swap( arr[l] , arr[rand()%(r-l+1)+l] );
T v = arr[l];
int j = l;
for( int i = l + 1 ; i <= r ; i ++ )
if( arr[i] < v ){
j ++;
swap( arr[j] , arr[i] );
}
swap( arr[l] , arr[j]);
return j;
}
// 双路快速排序的partition
// 返回p, 使得arr[l...p-1] < arr[p] ; arr[p+1...r] > arr[p]
template
int _partition2(T arr[], int l, int r){
// 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
swap( arr[l] , arr[rand()%(r-l+1)+l] );
T v = arr[l];
int i = l+1, j = r;
while( true ){
// 注意这里的边界, arr[i] < v, 不能是arr[i] <= v
while( i <= r && arr[i] < v )
i ++;
// 注意这里的边界, arr[j] > v, 不能是arr[j] >= v
while( j >= l+1 && arr[j] > v )
j --;
if( i > j )
break;
swap( arr[i] , arr[j] );
i ++;
j --;
}
swap( arr[l] , arr[j]);
return j;
}
// 对arr[l...r]部分进行快速排序
template
void _quickSort(T arr[], int l, int r){
// 对于小规模数组, 使用插入排序进行优化
if( r - l <= 15 ){
insertionSort(arr,l,r);
return;
}
// 调用双路快速排序的partition
int p = _partition2(arr, l, r);
_quickSort(arr, l, p-1 );
_quickSort(arr, p+1, r);
}
template
void quickSort(T arr[], int n){
srand(time(NULL));
_quickSort(arr, 0, n-1);
}
#endif
复制代码
2.三路快排实现：
复制代码
1 #include
2 #include
3 #include
4 #include "SortTestHelper.h"
5 #include "MergeSort.h"
6 #include "InsertionSort.h"
7 #include "QuickSort.h"
8 using namespace std;
9 // 递归的三路快速排序算法
10 template
11 void __quickSort3Ways(T arr[], int l, int r){
12 // 对于小规模数组, 使用插入排序进行优化
13 if( r - l <= 15 ){
14 insertionSort(arr,l,r);
15 return;
16 }
17 // 随机在arr[l...r]的范围中, 选择一个数值作为标定点pivot
18 swap( arr[l], arr[rand()%(r-l+1)+l ] );
19 T v = arr[l];
20 int lt = l; // arr[l+1...lt] < v
21 int gt = r + 1; // arr[gt...r] > v
22 int i = l+1; // arr[lt+1...i) == v
23 while( i < gt ){
24 if( arr[i] < v ){
25 swap( arr[i]