two too small 问题，关于排序

1，n个数的无序序列，怎样排序，可以得到,n/2小的在左,n/2大的在右，就是左边的任何一个元素都比右边的任何一个元素小，左右两边个数相等，
（n为奇数是左右两边是：n-1/2），要求时间复杂度最小！
2，n<20,n->1000,算法有何不同？

7 个解决方案

#1

索引排序

#2

gz

#3

有程序为证吗？
复杂度？

#4

左右两边个数相等? 有这个必要吗？要是没有这个条件的话，就用快速排序法吧，那可是最快的一种排序算法呀 ！

#5

各种方法都行：
1.可以建立一棵二叉搜索树，也可以用快排，merge，bucket，shell，随便。

你这个要求是搞笑的吧。所有的数组排序，排好以后，从总元素数除2的位置看，得到的就是两边的数一样多，左边比右边小。

如果左右数列内部都不要排序的话，那就用O(n)的时间找到一个在中间的数（方法是，先保存最小和最大的数，再从两边逐渐往中间拉），然后再用O(n)的时间把小于这个数的数换到左边，就行了。

2.n=20的时候好像选择和插入排序都比这些O(nlogn)的排序来的快，1000的时候它们这些O(n^2)的就不行了。

#6

胖子兄，你能用O(n)找到正中间数吗？
所有的排序都可以达到一边小一边大，但是时间复杂度最小，可就不行了。
我只是怀疑找到中间数的O(n)是否存在。

#7

当然。找中值的Hoare算法如下（书上抄来的）：
find (k, left, right : INTEGER) is
-- find the kth smallest item
-- in the array segment A[left..right]
local
i, j : INTEGER
p : G
do
from
i := left
j : = right
until
i >= j
loop
p := A.item(k)
partition(i,j,p) -- L:=i; R:=j
-- finishes with R < L
if R < k then
-- kth smallest in right split
i := L
end
if k < L then
-- kth smallest in left split
j := R
end
end
end -- find
Partition (L0,R0 : INTEGER; P : G) is
do
from
L := L0
R := R0
until
L > R
loop
Left_Scan (P)
Right_Scan(P)
if L <= R then
exchange(L,R)
L := L+1
R := R-1
end
end
end -- Partition
Left_Scan (P : G) is
do
from
until
A.item(L) >= P
loop
L := L+1
end
end -- Left_Scan
Right_Scan (P : G) is
do
from
until
A.item(R) <= P
loop
R := R-1
end
end -- Right_Scan