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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
|
#include<iostream>
#include<vector>
using namespace std;
/**
*各种搜索方法
**/
//*****************************插入排序*************************************//
//直接插入排序,稳定排序
//最好O(n),最坏O(n^2),平均O(n^2)
void insertSort(vector<int> &raw_arr){
int n = int(raw_arr.size());
if(n==0)
return;
for(int i = 1;i<n;++i){
//保存当前元素
int temp = raw_arr[i];
int end = i-1;
//大的元素往后挪
while(end>=0 && raw_arr[end]>temp){
raw_arr[end+1] = raw_arr[end];
end--;
}
raw_arr[end+1] = temp;
}
}
//*****************************希尔排序*************************************//
//希尔排序,不稳定排序
//最好O(N),最坏O(N^2),平均O(N^1.3)
void shellSort(vector<int> &raw_arr){
int n = int(raw_arr.size());
int step = n;
while(step>1){
step = step/3 + 1;
for(int i = 0;i<n-step;++i){
int temp = raw_arr[i+step];
int end = i;
while(end>=0 && raw_arr[end]>temp){
raw_arr[end+step] = raw_arr[end];
end-=step;
}
raw_arr[end+step] = temp;
}
}
}
//*****************************选择排序*************************************//
//选择排序,不稳定排序 (每次循环找到最大值和最小值，然后缩小begin 和 end的范围)
//最好O(N^2),最坏O(N^2),平均O(N^2)
void selectSort(vector<int> &raw_arr){
int n = int(raw_arr.size());
int begin = 0, end = n-1;
while(begin<=end){
int min_idx = begin, max_idx = end;
for(int i = begin;i<=end;++i){
if(raw_arr[i]<raw_arr[min_idx])
min_idx = i;
if(raw_arr[i]>raw_arr[max_idx])
max_idx = i;
}
swap(raw_arr[begin], raw_arr[min_idx]);
//注意这个条件，因为存在最大值在“begin”处的可能性
if(max_idx == begin)
max_idx = min_idx;
swap(raw_arr[end], raw_arr[max_idx]);
begin++;
end--;
}
}
//*****************************堆排序*************************************//
void heapAjust(vector<int> &raw_arr, int root, int n){
int child = 2 * root + 1;
while(child<n){
//寻找值最大的叶子节点
if(child+1<n && raw_arr[child]<raw_arr[child+1])
child++;
//由于从最后一个非叶子节点开始遍历，当满足该条件时，一定保证该子堆是最大堆了(因为更小的子堆在之前就处理好了)
if(raw_arr[root]>raw_arr[child])
break;
swap(raw_arr[root], raw_arr[child]);
//下一级
root = child;
child = 2 * root + 1;
}
}
//堆排序，不稳定排序
//最好O(N*log(N)),最坏O(N*log(N)),平均O(N*log(N))
void heapSort(vector<int> &raw_arr){
int n = int(raw_arr.size());
//首先建一次大堆
//i=n/2 - 1是最后一个非叶子节点
for(int i = n/2 - 1;i>=0;--i){
heapAjust(raw_arr, i, n);
}
int end = n-1;
//把最大值交换到数组尾部，再执行n-1次heapAjust
while(end>0){
swap(raw_arr[0], raw_arr[end]);
//由于索引0处不满足最大堆定义，需要调整
heapAjust(raw_arr, 0, end);
end--;
}
}
//*****************************冒泡排序*************************************//
//冒泡排序,稳定排序
//最好O(N),最坏O(N^2),平均O(N^2)
void bubbleSort(vector<int> &raw_arr){
int n = int(raw_arr.size());
int end = n-1;
while(end>0){
for(int i = 0;i<=end;++i){
if(i>0 && raw_arr[i]<raw_arr[i-1])
swap(raw_arr[i], raw_arr[i-1]);
}
end--;
}
}
//*****************************快速排序*************************************//
int partion(vector<int> &raw_arr, int begin, int end){
if(begin>=end)
return begin;
//小技巧：如果key定在end, 要先递增begin;反之也成立。
//注意raw_arr[begin]<=raw_arr[key]的“<=”号，不可以写成"<"，否则对于有重复数字的排序会出错。
int key = end;
while(begin<end){
while(begin<end && raw_arr[begin]<=raw_arr[key])
begin++;
while(begin<end && raw_arr[end]>=raw_arr[key])
end--;
swap(raw_arr[begin], raw_arr[end]);
}
swap(raw_arr[begin], raw_arr[key]);
return end;
}
void _quickSort(vector<int> &raw_arr, int s_idx, int e_idx){
if(s_idx < e_idx){
int part = partion(raw_arr, s_idx, e_idx);
_quickSort(raw_arr, s_idx, part-1);
_quickSort(raw_arr, part+1, e_idx);
}
}
//快速排序,不稳定排序
//最好O(N*log(N)),,最坏O(N^2),平均O(N*log(N))
void quickSort(vector<int> &raw_arr){
int n = int(raw_arr.size());
_quickSort(raw_arr, 0, n-1);
}
//*****************************归并排序*************************************//
void _mergeSort(vector<int> &raw_arr, int *temp, int begin, int end){
if(begin>=end)
return;
//注意右移符号的优先级很低，需要用()括起来
int mid = begin + ((end-begin)>>1);
_mergeSort(raw_arr, temp, begin, mid);
_mergeSort(raw_arr, temp, mid+1, end);
//合并
int begin1 = begin, end1 = mid;
int begin2 = mid+1, end2 = end;
int temp_s_idx = begin;
while(begin1<=end1 && begin2<=end2){
if(raw_arr[begin1]<raw_arr[begin2])
temp[begin++] = raw_arr[begin1++];
else {
temp[begin++] = raw_arr[begin2++];
}
}
while(begin1<=end1){
temp[begin++] = raw_arr[begin1++];
}
while(begin2<=end2){
temp[begin++] = raw_arr[begin2++];
}
//复制到原来的数组
begin = temp_s_idx;
while(begin<=end){
raw_arr[begin] = temp[begin];
begin++;
}
}
//归并排序,稳定排序
//最好O(N*log(N)),,最坏O(N*log(N)),平均O(N*log(N))
void mergeSort(vector<int> &raw_arr){
int n = int(raw_arr.size());
int *temp = new int[n];
_mergeSort(raw_arr, temp, 0, n-1);
delete[] temp;
}
int main(){
vector<int> raw_arr = {3,3,15,4,1,3,24,8,45,7,1,65,9,17};
// insertSort(raw_arr);
// shellSort(raw_arr);
// selectSort(raw_arr);
// heapSort(raw_arr);
// bubbleSort(raw_arr);
// quickSort(raw_arr);
// mergeSort(raw_arr);
for(int ra:raw_arr){
cout<<ra<<" ";
}
cout<<endl;
return 0;
}
|