forked from JiauZhang/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathquick_sort.cpp
More file actions
123 lines (109 loc) · 3 KB
/
quick_sort.cpp
File metadata and controls
123 lines (109 loc) · 3 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
/*
* Copyright(c) 2019 Jiau Zhang
* For more information see <https://github.com/JiauZhang/algorithms>
*
* This repo is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation
*
* It is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with THIS repo. If not, see <http://www.gnu.org/licenses/>.
*/
#include <iostream>
#include <cstdlib>
using namespace std;
// if you want more detail info, open `#define DEBUG`.
//#define DEBUG
#ifdef DEBUG
#define debug(data, start, end) print(data, start, end)
#else
#define debug(data, start, end)
#endif
int random_in_range(int start, int end)
{
if(start==end) {
return start;
} else {
int index = rand()%(end-start) + start;
return index;
}
}
template <typename T>
void swap(T* v1, T* v2)
{
T temp = *v1;
*v1 = *v2;
*v2 = temp;
}
void print(int data[], int start, int end)
{
if(start>end) {
cout << "invalid input" << endl;
} else {
while(start<=end) {
cout << data[start] << ' ';
start++;
}
}
cout << endl;
}
int partition(int data[], int length, int start, int end)
{
if(data==NULL || length<=0 || start<0 || end>=length) {
return false;
}
int index = random_in_range(start, end);
#ifdef DEBUG
cout << "random data[index]: " << data[index] << endl;
#endif
debug(data, start, end);
swap<int>(&data[index], &data[end]);
debug(data, start, end);
// small指针左侧的(包括当前指向的)是小于data[index]的数据
//右侧的(不包括指针指向的)到index之间的是大于data[index]的数据
//因此当遇到 < data[index]的数据时，small++，检查两个指针是否相等
//如果不等说明它们之间有 > data[index]的数据，那么就把小的交换到后方
//最后把data[index]从末尾置换到所有比它小的数之间，即small++
int small = start-1;
for(index=start; index<end; ++index) {
if(data[index]<data[end]) {
++small;
#ifdef DEBUG
cout << "small: " << small << " index: " << index << "--";
#endif
if(small!=index) {
swap<int>(&data[index], &data[small]);
}
debug(data, start, end);
}
}
++small;
swap<int>(&data[small], &data[end]);
debug(data, start, end);
return small;
}
void quick_sort(int data[], int length, int start, int end)
{
//原来 void 函数也是可以 return，但是不能带有任何返回参数，否则编译报错
if(start==end)
return;
//排序的实质性操作是在此函数中完成的
int index = partition(data, length, start, end);
if(index>start)
quick_sort(data, length, start, index-1);
if(index<end)
quick_sort(data, length, index+1, end);
}
int main(int argc, char** argv)
{
int data[10] = {9, 11, 5, 30, 7 ,13 ,22 ,4, 8, 18};
print(data, 0, 9);
quick_sort(data, 10, 0, 9);
print(data, 0, 9);
return 0;
}