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
| #include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
void quick_sort(vector<int>& q, int l, int r)
{
if (l >= r) return;
int x = q[l + (r - l) / 2], i = l - 1, j = r + 1;
while (i < j)
{
while (q[++i] < x);
while (q[--j] > x);
if (i < j) swap(q[i], q[j]);
}
quick_sort(q, l, j);
quick_sort(q, j + 1, r);
}
void merge_sort(vector<int>& q, int l, int r)
{
if (l >= r) return;
int mid = l + (r - l) / 2;
merge_sort(q, l, mid);
merge_sort(q, mid + 1, r);
int i = l, j = mid + 1;
vector<int> temp;
while (i <= mid && j <= r)
{
if (q[i] < q[j]) temp.push_back(q[i++]);
else temp.push_back(q[j++]);
}
while (i <= mid) temp.push_back(q[i++]);
while (j <= r) temp.push_back(q[j++]);
for (i = l, j = 0; i <= r; i++, j++) q[i] = temp[j];
}
void bubble_sort(vector<int>& q, int l, int r)
{
if (l >= r) return;
for (int i = 0; i < r - l; i++)
{
int flag = 0;
for (int j = l; j < r - i; j++)
{
if (q[j] > q[j + 1])
{
swap(q[j], q[j + 1]);
flag = 1;
}
}
if (flag == 0) break;
}
}
void select_sort(vector<int>& q, int l, int r)
{
if (l >= r) return;
for (int i = l; i <= r; i++)
{
int mi = i;
for (int j = i + 1; j <= r; j++)
{
if (q[mi] > q[j]) mi = j;
}
if (mi != i) swap(q[i], q[mi]);
}
}
void insert_sort(vector<int>& q, int l, int r)
{
if (l >= r) return;
for (int i = l + 1; i <= r; i++)
{
int temp = q[i];
int j = i - 1;
while (j >= 0 && q[j] > temp)
{
q[j + 1] = q[j];
j--;
}
q[j + 1] = temp;
}
}
void Print(vector<int>& q)
{
for (unsigned int i = 0; i < q.size(); i++) cout << q[i] << " ";
cout << endl;
}
int main()
{
vector<int> vec;
int n = 0, t = 0;
cout << "输入数据个数：";
cin >> n;
srand((unsigned)time(NULL));
cout << "随机生成" << n << "个数据：";
for (int i = 0; i < n; i++)
{
t = rand() % 100 + 1;
vec.push_back(t);
}
Print(vec);
vector<int> v1(vec), v2(vec), v3(vec), v4(vec), v5(vec);
cout << "快速排序结果：";
quick_sort(v1, 0, v1.size() - 1);
Print(v1);
cout << "归并排序结果：";
merge_sort(v2, 0, v2.size() - 1);
Print(v2);
cout << "冒泡排序结果：";
bubble_sort(v3, 0, v3.size() - 1);
Print(v3);
cout << "选择排序结果：";
bubble_sort(v4, 0, v4.size() - 1);
Print(v4);
cout << "插入排序结果：";
insert_sort(v5, 0, v5.size() - 1);
Print(v5);
return 0;
}
|
微信
