-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathmain.cpp
More file actions
123 lines (111 loc) · 3.17 KB
/
Copy pathmain.cpp
File metadata and controls
123 lines (111 loc) · 3.17 KB
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
//
// main.cpp
// QuickSort
//
// Created by Dewen Chao on 15/10/8.
// Copyright © 2015年 Dewen Chao. All rights reserved.
//
#include <iostream>
#include <ctime>
#include <cstdlib> // QuickSort
#define N 10
using namespace std;
// 时间复杂度O(NlogN)~O(N^2)
// 快速排序的基本思想是：每次从无序的序列中找出一个数作为中间点（可以把第一个数作为中间点）
// 然后把小于中间点的数放在中间点的左边，把大于中间点的数放在中间点的右边
// 对以上过程重复最好logN次、最差N次得到有序的序列
// 快速排序是通常被认为在同数量级O(NlogN)的排序方法中平均性能最好的
// 但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序
// 为改进之，通常以“三者取中法”来选取基准记录
// 即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录
// 快速排序是一个不稳定的排序方法
void quickSort(int arr[], int left, int right)
{
if(left < right)
{
int l = left, r = right;
// 此处可以调换第一个数和中间数，即选择不同的key
// swap(arr[l], arr[(l + r) / 2]);
int key = arr[l];
while(l < r)
{
while(l < r && arr[r] >= key)
{
r--;
}
if(l < r)
{
arr[l++] = arr[r];
}
while(l < r && arr[l] <= key)
{
l++;
}
if(l < r)
{
arr[r--] = arr[l];
}
}
arr[l] = key;
quickSort(arr, left, l - 1);
quickSort(arr, l + 1, right);
}
}
//int cmp(const void *pa, const void *pb)
//{
// return *(int *)pa - *(int *)pb;
//}
int main()
{
int myarr[N];
srand((unsigned)time(NULL));
for(int i = 0; i < N; i++)
{
myarr[i] = rand() % 100;
cout << myarr[i] << " ";
}
cout << endl;
quickSort(myarr, 0, N - 1);
for(int i = 0; i < N; i++)
{
cout << myarr[i] << " ";
}
cout << endl;
// 检查排序函数正确性
// int arr[N];
// for(int i = 0; i < 10000; i++)
// {
// for(int j = 0; j < N; j++)
// {
// arr[j] = rand() % 100;
// myarr[j] = arr[j];
// }
// qsort(arr, N, sizeof(int), cmp);
// quickSort(myarr, 0, N - 1);
// for(int j = 0; j < N; j++)
// {
// if(arr[j] != myarr[j])
// {
// cout << " qsort:";
// for(int k = 0; k < N; k++)
// {
// cout << arr[k] << " ";
// }
// cout << endl;
//
// cout << "QuickSort:";
// for(int k = 0; k < N; k++)
// {
// cout << myarr[k] << " ";
// }
// cout << endl;
//
// cout << "QuickSort Wrong!" << endl;
//
// return 0;
// }
// }
// }
// cout << "QuickSort Right!" << endl;
return 0;
}