做1306的sorting algorithm的時候
一開始寫的快排超時了
然后用ilovenwd師兄提供了下面的快排才過了
你快排寫得不好.
試試一組 1000000 個0的數(shù)據(jù).
參考一下下面這個
void
quick_sort(
int
*
a,
int
n)
{
int
i
=
0
,j
=
n
-
1
;
int
x
=
a[n
/
2
];
while
(i
<=
j)
{
while
(a[i]
<
x)i
++
;
//
注意<不是<=
while
(a[j]
>
x)j
--
;
if
(i
<=
j)swap(a[i],a[j]),
++
i,
--
j;
}
if
(j
>
0
)quick_sort(a,j
+
1
);
if
(i
<
n
-
1
)quick_sort(a
+
i,n
-
i);
}
關(guān)鍵的不是左邊或間.
而是 那個<和<=的區(qū)別.
你去看一些比較好的算法書.比如Robert Sedgewick那本.有詳細分析.
如果你覺得取中間有可能O(n^2)就一開始就隨機Shuffle一下.不過基本沒必要.
===============
void
sort(
int
l,
int
r)
{
int
i,j,x,t;
i
=
l;j
=
r;x
=
a[(l
+
r)
/
2
];
do
{
while
((a[i]
<
x)
&&
(i
<
r))i
++
;
while
((a[j]
>
x)
&&
(j
>
l))j
--
;
if
(i
<=
j)
{t
=
a[i];a[i]
=
a[j];a[j]
=
t;i
++
;j
--
;}
}
while
(i
<=
j);
if
(l
<
j)sort(l,j);
if
(r
>
i)sort(i,r);
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯(lián)系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
