- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章C++实现八个常用的排序算法 插入排序、冒泡排序、选择排序、希尔排序等由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
本文实现了八个常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序 、快速排序、归并排序、堆排序和LST基数排序 。
首先是算法实现文件Sort.h,代码如下:
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
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
|
/*
* 实现了八个常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序
* 以及快速排序、归并排序、堆排序和LST基数排序
* @author gkh178
*/
#include <iostream>
template
<
class
T>
void
swap_value(T &a, T &b)
{
T temp = a;
a = b;
b = temp;
}
//插入排序:时间复杂度o(n^2)
template
<
class
T>
void
insert_sort(T a[],
int
n)
{
for
(
int
i = 1; i < n; ++i)
{
T temp = a[i];
int
j = i - 1;
while
(j >= 0 && a[j] > temp)
{
a[j + 1] = a[j];
--j;
}
a[j + 1] = temp;
}
}
//冒泡排序:时间复杂度o(n^2)
template
<
class
T>
void
bubble_sort(T a[],
int
n)
{
for
(
int
i = n - 1; i > 0; --i)
{
for
(
int
j = 0; j < i; ++j)
{
if
(a[j] > a[j + 1])
{
swap_value(a[j], a[j + 1]);
}
}
}
}
//选择排序:时间复杂度o(n^2)
template
<
class
T>
void
select_sort(T a[],
int
n)
{
for
(
int
i = 0; i < n - 1; ++i)
{
T min = a[i];
int
index = i;
for
(
int
j = i + 1; j < n; ++j)
{
if
(a[j] < min)
{
min = a[j];
index = j;
}
}
a[index] = a[i];
a[i] = min;
}
}
//希尔排序:时间复杂度介于o(n^2)和o(nlgn)之间
template
<
class
T>
void
shell_sort(T a[],
int
n)
{
for
(
int
gap = n / 2; gap >= 1; gap /= 2)
{
for
(
int
i = gap; i < n; ++i)
{
T temp = a[i];
int
j = i - gap;
while
(j >= 0 && a[j] > temp)
{
a[j + gap] = a[j];
j -= gap;
}
a[j + gap] = temp;
}
}
}
//快速排序:时间复杂度o(nlgn)
template
<
class
T>
void
quick_sort(T a[],
int
n)
{
_quick_sort(a, 0, n - 1);
}
template
<
class
T>
void
_quick_sort(T a[],
int
left,
int
right)
{
if
(left < right)
{
int
q = _partition(a, left, right);
_quick_sort(a, left, q - 1);
_quick_sort(a, q + 1, right);
}
}
template
<
class
T>
int
_partition(T a[],
int
left,
int
right)
{
T pivot = a[left];
while
(left < right)
{
while
(left < right && a[right] >= pivot)
{
--right;
}
a[left] = a[right];
while
(left < right && a[left] <= pivot)
{
++left;
}
a[right] = a[left];
}
a[left] = pivot;
return
left;
}
//归并排序:时间复杂度o(nlgn)
template
<
class
T>
void
merge_sort(T a[],
int
n)
{
_merge_sort(a, 0, n - 1);
}
template
<
class
T>
void
_merge_sort(T a[],
int
left,
int
right)
{
if
(left < right)
{
int
mid = left + (right - left) / 2;
_merge_sort(a, left, mid);
_merge_sort(a, mid + 1, right);
_merge(a, left, mid, right);
}
}
template
<
class
T>
void
_merge(T a[],
int
left,
int
mid,
int
right)
{
int
length = right - left + 1;
T *newA =
new
T[length];
for
(
int
i = 0, j = left; i <= length - 1; ++i, ++j)
{
*(newA + i) = a[j];
}
int
i = 0;
int
j = mid - left + 1;
int
k = left;
for
(; i <= mid - left && j <= length - 1; ++k)
{
if
(*(newA + i) < *(newA + j))
{
a[k] = *(newA + i);
++i;
}
else
{
a[k] = *(newA + j);
++j;
}
}
while
(i <= mid - left)
{
a[k++] = *(newA + i);
++i;
}
while
(j <= right - left)
{
a[k++] = *(newA + j);
++j;
}
delete
newA;
}
//堆排序:时间复杂度o(nlgn)
template
<
class
T>
void
heap_sort(T a[],
int
n)
{
built_max_heap(a, n);
//建立初始大根堆
//交换首尾元素,并对交换后排除尾元素的数组进行一次上调整
for
(
int
i = n - 1; i >= 1; --i)
{
swap_value(a[0], a[i]);
up_adjust(a, i);
}
}
//建立一个长度为n的大根堆
template
<
class
T>
void
built_max_heap(T a[],
int
n)
{
up_adjust(a, n);
}
//对长度为n的数组进行一次上调整
template
<
class
T>
void
up_adjust(T a[],
int
n)
{
//对每个带有子女节点的元素遍历处理,从后到根节点位置
for
(
int
i = n / 2; i >= 1; --i)
{
adjust_node(a, n, i);
}
}
//调整序号为i的节点的值
template
<
class
T>
void
adjust_node(T a[],
int
n,
int
i)
{
//节点有左右孩子
if
(2 * i + 1 <= n)
{
//右孩子的值大于节点的值,交换它们
if
(a[2 * i] > a[i - 1])
{
swap_value(a[2 * i], a[i - 1]);
}
//左孩子的值大于节点的值,交换它们
if
(a[2 * i - 1] > a[i - 1])
{
swap_value(a[2 * i - 1], a[i - 1]);
}
//对节点的左右孩子的根节点进行调整
adjust_node(a, n, 2 * i);
adjust_node(a, n, 2 * i + 1);
}
//节点只有左孩子,为最后一个有左右孩子的节点
else
if
(2 * i == n)
{
//左孩子的值大于节点的值,交换它们
if
(a[2 * i - 1] > a[i - 1])
{
swap_value(a[2 * i - 1], a[i - 1]);
}
}
}
//基数排序的时间复杂度为o(distance(n+radix)),distance为位数,n为数组个数,radix为基数
//本方法是用LST方法进行基数排序,MST方法不包含在内
//其中参数radix为基数,一般为10;distance表示待排序的数组的数字最长的位数;n为数组的长度
template
<
class
T>
void
lst_radix_sort(T a[],
int
n,
int
radix,
int
distance)
{
T* newA =
new
T[n];
//用于暂存数组
int
* count =
new
int
[radix];
//用于计数排序,保存的是当前位的值为0 到 radix-1的元素出现的的个数
int
divide = 1;
//从倒数第一位处理到第一位
for
(
int
i = 0; i < distance; ++i)
{
//待排数组拷贝到newA数组中
for
(
int
j = 0; j < n; ++j)
{
*(newA + j) = a[j];
}
//将计数数组置0
for
(
int
j = 0; j < radix; ++j)
{
*(count + j) = 0;
}
for
(
int
j = 0; j < n; ++j)
{
int
radixKey = (*(newA + j) / divide) % radix;
//得到数组元素的当前处理位的值
(*(count + radixKey))++;
}
//此时count[]中每个元素保存的是radixKey位出现的次数
//计算每个radixKey在数组中的结束位置,位置序号范围为1-n
for
(
int
j = 1; j < radix; ++j)
{
*(count + j) = *(count + j) + *(count + j - 1);
}
//运用计数排序的原理实现一次排序,排序后的数组输出到a[]
for
(
int
j = n - 1; j >= 0; --j)
{
int
radixKey = (*(newA + j) / divide) % radix;
a[*(count + radixKey) - 1] = newA[j];
--(*(count + radixKey));
}
divide = divide * radix;
}
}
|
然后是测试文件main.cpp,代码如下:
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
|
#include "Sort.h"
using
namespace
std;
template
<
class
T>
void
printArray(T a[],
int
n)
{
for
(
int
i = 0; i < n; ++i)
{
cout << a[i] <<
" "
;
}
cout << endl;
}
int
main()
{
for
(
int
i = 1; i <= 8; ++i)
{
int
arr[] = { 45, 38, 26, 77, 128, 38, 25, 444, 61, 153, 9999, 1012, 43, 128 };
switch
(i)
{
case
1:
insert_sort(arr,
sizeof
(arr) /
sizeof
(arr[0]));
break
;
case
2:
bubble_sort(arr,
sizeof
(arr) /
sizeof
(arr[0]));
break
;
case
3:
select_sort(arr,
sizeof
(arr) /
sizeof
(arr[0]));
break
;
case
4:
shell_sort(arr,
sizeof
(arr) /
sizeof
(arr[0]));
break
;
case
5:
quick_sort(arr,
sizeof
(arr) /
sizeof
(arr[0]));
break
;
case
6:
merge_sort(arr,
sizeof
(arr) /
sizeof
(arr[0]));
break
;
case
7:
heap_sort(arr,
sizeof
(arr) /
sizeof
(arr[0]));
break
;
case
8:
lst_radix_sort(arr,
sizeof
(arr) /
sizeof
(arr[0]), 10, 4);
break
;
default
:
break
;
}
printArray(arr,
sizeof
(arr) /
sizeof
(arr[0]));
}
return
0;
}
|
最后是运行结果图,如下:
以上就是C++实现八个常用的排序算法的全部代码,希望大家对C++排序算法有更进一步的了解.
最后此篇关于C++实现八个常用的排序算法 插入排序、冒泡排序、选择排序、希尔排序等的文章就讲到这里了,如果你想了解更多关于C++实现八个常用的排序算法 插入排序、冒泡排序、选择排序、希尔排序等的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
是否有某种方法可以使用 JPA 或 Hibernate Crtiteria API 来表示这种 SQL?或者我应该将其作为 native 执行吗? SELECT A.X FROM (SELECT X,
在查询中, select id,name,feature,marks from (....) 我想删除其 id 在另一个 select 语句中存在的那些。 从 (...) 中选择 id 我是 sql
我想响应用户在 select 元素中选择一个项目。然而这个 jQuery: $('#platypusDropDown').select(function () { alert('You sel
这个问题在这里已经有了答案: SQL select only rows with max value on a column [duplicate] (27 个回答) 关闭8年前。 我正在学习 SQL
This question already has answers here: “Notice: Undefined variable”, “Notice: Undefined index”, and
我在 php 脚本中调用 SQL。有时“DE”中没有值,如果是这种情况我想从“EN”中获取值 应该是这样的,但不是这样的 IF (EXISTS (SELECT epf_application_deta
这可能是一个奇怪的问题,但不知道如何研究它。执行以下查询时: SELECT Foo.col1, Foo.col2, Foo.col3 FROM Foo INNER JOIN Bar ON
如何在使用 Camera.DestinationType.FILE_URI. 时在 phonegap camera API 中同时选择或拾取多个图像我能够一次只选择一张图像。我可以使用 this 在
这是一个纯粹的学术问题。这两个陈述实际上是否相同? IF EXISTS (SELECT TOP 1 1 FROM Table1) SELECT 1 ELSE SELECT 0 相对 IF EXIS
我使用 JSoup 来解析 HTML 响应。我有多个 Div 标签。我必须根据 ID 选择 Div 标签。 我的伪代码是这样的 Document divTag = Jsoup.connect(link
我正在处理一个具有多个选择框的表单。当用户从 selectbox1 中选择一个选项时,我需要 selectbox2 active 的另一个值。同样,当他选择 selectbox2 的另一个值时,我需要
Acme Inc. Christa Woods Charlotte Freeman Jeffrey Walton Ella Hubbard Se
我有一个login.html其中form定义如下: First Initial Plus Last Name : 我的do_authorize如下: "; pri
$.get( 'http://www.ufilme.ro/api/load/maron_online/470', function(data
我有一个下拉列表“磅”、“克”、“千克”和“盎司”。我想要这样一种情况,当我选择 gram 来执行一个函数时,当我在输入字段中输入一个值时,当我选择 pounds 时,我想要另一个函数来执行时我在输入
我有一个 GLSL 着色器,它从输入纹理的 channel 之一(例如 R)读取,然后写入输出纹理中的同一 channel 。该 channel 必须由用户选择。 我现在能想到的就是使用一个 int
我想根据下拉列表中的选定值生成输入文本框。 Options 2 3 4 5 就在这个选择框之后,一些输入字段应该按照选定的数字出现。 最佳答案 我建议您使用响应式(Reac
我是 SQL 新手,我想问一下如何根据首选项和分组选择条目。 +----------+----------+------+ | ENTRY_ID | ROUTE_ID | TYPE | +------
我有以下表结构: CREATE TABLE [dbo].[UTS_USERCLIENT_MAPPING_USER_LIST] ( [MAPPING_ID] [int] IDENTITY(1,1
我在移除不必要的床单时遇到了问题。我查看了不同的论坛并将不同的解决方案混合在一起。 此宏删除工作表(第一张工作表除外)。 Sub wrong() Dim sht As Object Applicati
我是一名优秀的程序员,十分优秀!