----C++ 冒泡排序算法
算法分析：
设数组长度为N。
1．比较相邻的前后二个数据，如果前面数据大于后面的数据，就将二个数据交换。
2．这样对数组的第0个数据到N-1个数据进行一次遍历后，最大的一个数据就"沉"到数组第N-1个位置。
3．N=N-1，如果N不为0就重复前面二步，否则排序完成。
程序代码：
|
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
|
#
include
<iostream>
using
namespace
std;
template<
class
T>
void
Swap(T &a,T &b)
{
T temp;
temp=a;
a=b;
b=temp;
}
//打印序列
template<
class
T>
void
print_info(T a[],
int
n)
{
cout<<
"排序后："
;
for
(
int
i=
0
;i<n;i++)
cout<<a[i]<<
" "
;
cout<<endl;
}
template<
class
T>
void
BubbleSort_01(T a[],
int
n)
{
int
i,j,k;
T t;
for
(i=n-
1
;i>
0
;i=k)
//将i设置为被交换的最后一对元素中较小的下标
for
(k=j=
0
;j<i;j++)
if
(a[j]>a[j+
1
])
{
t=a[j];
a[j]=a[j+
1
];
a[j+
1
]=t;
k=j;
//如有交换发生，记录较小元素的下标
}
}
//算法02 由小到大排序
template <
class
T>
void
BubbleSort_02(T a[],
int
n)
{
// T temp;
for
(
int
i=n-
1
;i>
0
;i--)
for
(
int
j=
0
;j<i;j++)
if
(a[j]>a[j+
1
])
Swap(a[j],a[j+
1
]);
}
//算法03
template <
class
T>
void
BubbleSort_03(T a[],
int
n)
{
for
(
int
i=
1
;i<n;i++)
for
(
int
j=
0
;j<n-i;j++)
if
(a[j]>a[j+
1
])
Swap(a[j],a[j+
1
]);
}
//优化后算法03
/*
设置一个标志，如果这一趟发生了交换，则为true，否则为false。
明显如果有一趟没有发生交换，说明排序已经完成。
*/
template <
class
T>
void
BubbleSort_04(T a[],
int
n)
{
bool flag=
true
;
int
k=n;
while
(flag)
{
flag=
false
;
for
(
int
i=
0
;i<k-
1
;i++)
if
(a[i]>a[i+
1
])
{
Swap(a[i],a[i+
1
]);
flag=
true
;
}
k--;
}
}
//优化后算法05
/*
如果有100个数的数组，仅前面10个无序，后面90个都已排好序且都大于前面10个数字，
那么在第一趟遍历后，最后发生交换的位置必定小于10，且这个位置之后的数据必定已经有序了，
记录下这位置，第二次只要从数组头部遍历到这个位置就可以了。
*/
template<
class
T>
void
BubbleSort_05(T a[],
int
n)
{
int
flag=n;
int
k=flag;
while
(flag>
0
)
{
k=flag;
flag=
0
;
for
(
int
i=
0
;i<k-
1
;i++)
if
(a[i]>a[i+
1
])
{
Swap(a[i],a[i+
1
]);
flag=i+
1
;
}
}
}
void
main()
{
int
a[]={
8
,
3
,
2
,
5
,
9
,
3
,
6
};
//BubbleSort_01(a,7);
//BubbleSort_02(a,7);
//BubbleSort_03(a,7);
//BubbleSort_04(a,7);
BubbleSort_05(a,
7
);
print_info(a,
7
);
}
|
本文转自arac 51CTO博客，原文链接：http://blog.51cto.com/skyarac/1314324，如需转载请自行联系原作者
