Posted on 2009-02-21 14:16
tanzek 閱讀(577)
評論(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