Posted on 2009-02-21 14:16
tanzek 阅读(542)
评论(0) 编辑 收藏 所属分类:
技术学习
看Robert Sedgewick的《algorithms in c》一书时，在讲到冒泡算法的时候在练习中提到了“摇摆排序”（中文版书中的P206面的第30题），然而细细理解出来就是指的二路冒泡，其实在Donald E.Knuth的《计算机程序设计艺术 第三卷 排序与查找》里面也有讲过，名字记得不是很清楚了。
暂时来讲我自己实现了一个，里面的性能分析和调优留在以后再做，先把它放在这里和大家一起共享一下，欢迎指正。
/*
* by tanzek. 2009-02-21 .
* implement in dev cpp.
*/
#include
<
stdio.h
>
#include
<
stdlib.h
>
#define
n 10
void
print(
int
*
a,
int
m,
int
l,
int
r)
{
for
(
int
i
=
0
; i
<
m; i
++
)
{
printf(
"
%d
"
, a[i]);
}
printf(
"
--->l=%d, r=%d\n
"
, l, r);
}
int
count
=
0
;
int
main()
{
int
a[
10
]
=
{
104
,
21
,
33
,
4
,
8
,
102
,
7
,
89
,
91
,
11
};
int
l, r;
l
=
-
1
; r
=
n;
int
t
=
1
;
int
temp;
int
j;
while
(t
>
0
)
{
count
++
;
printf(
"
第%d趟\n
"
, count);
t
=
-
1
;
for
(j
=
r
-
1
; j
>
l
+
1
; j
--
)
{
if
(a[j]
<
a[j
-
1
])
{
temp
=
a[j]; a[j]
=
a[j
-
1
]; a[j
-
1
]
=
temp;
t
=
j
-
1
;
}
}
l
=
j;
for
(j
=
l
+
1
; j
<
r
-
1
; j
++
)
{
if
(a[j]
>
a[j
+
1
])
{
temp
=
a[j]; a[j]
=
a[j
+
1
]; a[j
+
1
]
=
temp;
t
=
j
+
1
;
}
}
r
=
j;
print(a, n, l, r);
}
printf(
"
\ncount = %d\n
"
, count);
system(
"
PAUSE
"
);
return
0
;
}
同时，通过GOOGLE搜索，也搜到一篇二路冒泡算法实现的文章，也放在这里供大家一起参考。
武林外传
http://qzone.qq.com/blog/53631006-1210520905