做1306的sorting algorithm的时候
一开始写的快排超时了
然后用ilovenwd师兄提供了下面的快排才过了
你快排写得不好.
试试一组 1000000 个0的数据.
参考一下下面这个
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);
}
关键的不是左边或间.
而是 那个<和<=的区别.
你去看一些比较好的算法书.比如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);
}
