一个朋友的面试题（有兴趣者请进） ( 积分: 0 )

同志们真爱钻牛角尖哦
今天为了这个问题烦恼了很久，终于搞定了
哎，用这种题会考死人的。
虽然我的算法没有采用额外数组，但是使用了递归，所以开销在堆栈中，我个人觉得
这个问题仅仅存在学术上的意义，没有什么实用价值
不想写思想了，同志们自己研究吧，算法代码如下
function GetOddCount(piInteger;ACount:Integer): integer;//计算奇数个数
var i:integer;
begin
Result:=0;
for i:=0 to ACount-1do
begin
if (pi^ mod 2)=1 then
Inc(Result);
Inc(pi);
end;
end;

procedure Swap(psi, pdi: pInteger);//交换两个整数
var tmp:Integer;
begin
tmp := psi^;
psi^ := pdi^;
pdi^ := tmp;
end;

procedure OddEvenDealV2(piInteger;ACount,OddCount:integer;
CurValue:integer;var CurpiInteger;var PreEvenCount:integer);
var pdiInteger;
ReplaceValue:Integer;
begin
if (Integer(CurPi)-Integer(pi))>=sizeof(Integer)*ACount then
exit;

if (CurValue mod 2)=1 then
//奇数
begin
//奇数只可能往前移动
pdi:=PInteger(Integer(Curpi)-sizeof(Integer)*PreEvenCount);
if pdi<>Curpi then
pdi^:=CurValue;
Inc(Curpi);
end
else
//偶数
begin
pdi:=PInteger(Integer(pi)+sizeof(Integer)*(ACount-1-PreEvenCount));
if pdi=Curpi then
begin
Inc(PreEvenCount);
Inc(Curpi);
end
else
begin
ReplaceValue:=pdi^;
pdi^:=CurValue;
Inc(PreEvenCount);
Inc(Curpi);
while Integer(pdi)-Integer(Curpi)>=0do
begin
if Integer(pdi)-Integer(Curpi)=0 then
OddEvenDealV2(pi,ACount,OddCount,ReplaceValue,Curpi,PreEvenCount)
else
OddEvenDealV2(pi,ACount,OddCount,Curpi^,Curpi,PreEvenCount);
end;
end;
end;
end;

procedure OddEvenDeal(piInteger;ACount:integer);
var TempPi,TempDPiinteger;
TempOddCount,TempPreEvenCount,i:integer;
begin
TempPi:=pi;
TempOddCount:=GetOddCount(pi,ACount);//O
TempPreEvenCount:=0;
//下面调用使：奇数按原来顺序排在前面，偶数按照原来的逆顺序排列在后面
//以下算法虽然采用了递归，但是时间效率为O
//因为每个入口都调用了Inc(TempPi),最多处理n次
while Integer(TempPi)-Integer(pi)<sizeof(Integer)*ACountdo
OddEvenDealV2(pi,ACount,TempOddCount,TempPi^,TempPi,TempPreEvenCount);
//最后调转偶数的顺序 O(n/2)
for i:=0 to (TempPreEvenCount div 2)-1do
begin
TempPi:=PInteger(Integer(pi)+sizeof(Integer)*(TempOddCount+i));
TempDPi:=PInteger(Integer(pi)+sizeof(Integer)*(ACount-1-i));
Swap(TempPi,TempDPi);
end;
end;

测试代码
type
TForm1 = class(TForm)
Memo1: TMemo;
Button1: TButton;
procedure Button1Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;
A:array[0..19] of Integer=(2,4,3,5,8,19,20,22,33,35,10,11,99,98,96,94,92,90,71,73);
implementation
{$R *.dfm}
procedure TForm1.Button1Click(Sender: TObject);
var i:integer;
begin
OddEvenDeal(@a[0],20);
for i:=0 to 19do
begin
Memo1.Lines.Add(IntToStr(a));
end;
end;

更简单的时间复杂度的算法这里有，时间复杂度绝对 = 0：
type
TArray = array [0..19] of Integer;
var
A: TArray =(2,4,3,5,8,19,20,22,33,35,10,11,99,98,96,94,92,90,71,73);
procedure Sort(var a: TArray;
CurEveCount: integer;
var OddCount: integer);
var
Value: Integer;
begin
if CurEveCount + OddCount > High(a) then
Exit;
Value := a[OddCount + CurEveCount];
if Value mod 2 = 1 then
begin
a[OddCount] := Value;
Inc(OddCount);
Sort(a, CurEveCount, OddCount);
end
else
begin
Sort(a, CurEveCount + 1, OddCount);
a[OddCount + CurEveCount] := Value;
end;
end;

procedure TForm1.Button1Click(Sender: TObject);
var
i, OddCount:integer;
begin
OddCount := 0;
Sort(A, 0, OddCount);
for i:= low(A) to High(A)do
Memo1.Lines.Add(IntToStr(A));
end;

要保存一半的数据，要是还符合题意那算我没说。

呵呵，递归的方式俺早就搞定了，结果被人pass了，说是时间复杂度大于0，我到现在也没有搞明白为啥大于，如果大于，时间复杂度是多少呢？

呵呵，放飞，你的递归是有问题的，得确时间复杂度不是0而是o(n2)
早上看了看jeffrey_s的算法，时间复杂度得确是o，呵呵
实际上就是在递归的时候把偶数的值全部压到堆栈里面了，最后一次性弹出
jeffrey_s的算法和我的思想基本上是一样的，但是他的算法更加简洁一点
我的算法也是ｏ（ｎ）的
大家可以在递归里面加入计数，我和jeffrey_s的算法都是20次就出来了.

不过递归的工作栈应该也是额外的存储空间

我查了一些资料，发现如果仅仅是函数调用，好像不影像时间复杂度
递归调用无非就是特殊的函数调用而已。
就像
for i := 0 to ndo
a := abs(a);
你不能说因为调用了abs函数就说时间复杂度就不是O了
在Delphi中没有内联函数，如果这个问题是在C++中
完全可以把我的那个px函数声明成内联函数，那你就不能说因为是递归调用内联函数而导致时间复杂度大于0了（内联函数在编译的时候会被展开并嵌入到调用的地方）
因此，我觉得，这个问题最好的解决方式就是递归

to lijun4183
你说我的程序有问题，请给出一个会产生错误的数组结够。
我再测试的时候，数组大小从1一直测试到100，数组的值全都是随机生成的，没有发现有什么问题（都被正常排序了）
（我说的是我最后一次给出的那个程序，在这之前的程序是因为我没有看明白问题）

呵呵，好像内联函数不能被递归调用[]

呵呵，放飞真执著哦！说你的有问题，不是说不能排出来，而是时间复杂度不对
请看测试代码:
1.我写的递归方法排序(在以前的方法上修改了，其实不用统计奇数个数)
Type TArray = array [0..19] of Integer;
var A:TArray=(2,4,3,5,8,19,20,22,33,35,10,11,99,98,96,94,92,90,71,73);
var Counter_NN:integer;//测试用的计数
//算法代码
procedure Swap(psi, pdi: pInteger);//交换两个整数
var tmp:Integer;
begin
tmp := psi^;
psi^ := pdi^;
pdi^ := tmp;
end;
procedure OddEvenDealV2(piInteger;ACount:integer;
CurValue:integer;var CurpiInteger;var PreEvenCount:integer);
var pdiInteger;
ReplaceValue:Integer;
begin
if (Integer(CurPi)-Integer(pi))>=sizeof(Integer)*ACount then
exit;
Counter_NN:=Counter_NN+1;//统计计数
if (CurValue mod 2)=1 then
//奇数
begin
//奇数只可能往前移动
pdi:=PInteger(Integer(Curpi)-sizeof(Integer)*PreEvenCount);
if pdi<>Curpi then
pdi^:=CurValue;
Inc(Curpi);
end
else
//偶数
begin
pdi:=PInteger(Integer(pi)+sizeof(Integer)*(ACount-1-PreEvenCount));
if pdi=Curpi then
begin
Inc(PreEvenCount);
Inc(Curpi);
end
else
begin
ReplaceValue:=pdi^;
pdi^:=CurValue;
Inc(PreEvenCount);
Inc(Curpi);
while Integer(pdi)-Integer(Curpi)>=0do
begin
if Integer(pdi)-Integer(Curpi)=0 then
OddEvenDealV2(pi,ACount,ReplaceValue,Curpi,PreEvenCount)
else
OddEvenDealV2(pi,ACount,Curpi^,Curpi,PreEvenCount);
end;
end;
end;
end;

procedure OddEvenDeal(piInteger;ACount:integer);
var TempPi,TempDPiinteger;
TempPreEvenCount,i:integer;
begin
TempPi:=pi;
TempPreEvenCount:=0;
//下面调用使：奇数按原来顺序排在前面，偶数按照原来的逆顺序排列在后面
//以下算法虽然采用了递归，但是时间效率为O
//因为每个入口都调用了Inc(TempPi),最多处理n次
while Integer(TempPi)-Integer(pi)<sizeof(Integer)*ACountdo
OddEvenDealV2(pi,ACount,TempPi^,TempPi,TempPreEvenCount);
//最后调转偶数的顺序 O(n/2)
for i:=0 to (TempPreEvenCount div 2)-1do
begin
TempPi:=PInteger(Integer(pi)+sizeof(Integer)*(ACount-TempPreEvenCount+i));
TempDPi:=PInteger(Integer(pi)+sizeof(Integer)*(ACount-1-i));
Swap(TempPi,TempDPi);
end;
end;

//测试代码
procedure TForm1.Button1Click(Sender: TObject);
var i:integer;
begin
Counter_NN:=0;
OddEvenDeal(@a[0],20);
for i:=0 to 19do
begin
Memo1.Lines.Add(IntToStr(a));
end;
Edit1.Text:=IntToStr(Counter_NN);
end;
//最后结果
3
5
19
33
35
11
99
71
73
2
4
8
20
22
10
98
96
94
92
90
Edit1.text显示20

2.再看jeffrey_s的代码
TArray = array [0..19] of Integer;
var A:TArray=(2,4,3,5,8,19,20,22,33,35,10,11,99,98,96,94,92,90,71,73);
var Counter_NN:integer;;//测试用的计数
//算法代码
procedure Sort(var a: TArray;
CurEveCount: integer;
var OddCount: integer);
var
Value: Integer;
begin
if CurEveCount + OddCount > High(a) then
Exit;
Counter_NN:=Counter_NN+1;

Value := a[OddCount + CurEveCount];
if Value mod 2 = 1 then
begin
a[OddCount] := Value;
Inc(OddCount);
Sort(a, CurEveCount, OddCount);
end
else
begin
Sort(a, CurEveCount + 1, OddCount);
a[OddCount + CurEveCount] := Value;
end;
end;
//测试代码
procedure TForm1.Button2Click(Sender: TObject);
var
i, OddCount:integer;
begin
Counter_NN:=0;
OddCount := 0;
Sort(A, 0, OddCount);
for i:= low(A) to High(A)do
Memo1.Lines.Add(IntToStr(A));
Edit1.Text:=IntToStr(Counter_NN);
end;
//同样结果
3
5
19
33
35
11
99
71
73
2
4
8
20
22
10
98
96
94
92
90
Edit1.text显示20

以上都是基于这个数组
TArray = array [0..19] of Integer;
var A:TArray=(2,4,3,5,8,19,20,22,33,35,10,11,99,98,96,94,92,90,71,73);
请各为加上上面两行

3.再看你的代码
TArray = array [0..19] of Integer;
var A:TArray=(2,4,3,5,8,19,20,22,33,35,10,11,99,98,96,94,92,90,71,73);
var Counter_NN:integer;//我加入了计数，计算你交换的次数
//算法代码如下
//交换两个指针指向的整数
procedure jh(psi, pdi: PInteger);
var
tmp: Integer;
begin
tmp := psi^;
psi^ := pdi^;
pdi^ := tmp;
Inc(Counter_NN);
end;

function px(psi, pdi: PInteger;
n: Integer;
iCount: Integer): Boolean;
var
tmppdi: PInteger;
begin
Result := False;
if (psi^ mod 2) = 0 then
begin
if (pdi^ mod 2) = 1 then
jh(psi, pdi)
else
begin
if n < iCount - 2 then
begin
tmppdi := pdi;
Inc(tmppdi);
Result := px(pdi, tmppdi, n + 1, iCount);
if (n + 1 <> iCount - 1) then
jh(psi, pdi);
if n + 2 = iCount - 1 then
Result := True;
end
else
if n < iCount - 1 then
Result := True;
end;
end;
end;
//测试代码
procedure TForm1.PrintIntArray(pi: PInteger;
ACount: Integer);
var
i: Integer;
begin
Memo1.Lines.begin
Update;
try
for i := 0 to ACount - 1do
begin
Memo1.Lines.Add(IntToStr(pi^));
Inc(pi);
end;

Memo1.Lines.Add('*******************************')
finally
Memo1.Lines.EndUpdate;
end;
end;

procedure TForm1.Button3Click(Sender: TObject);
var
i: Integer;
iCount: Integer;
begin
Memo1.Clear;
iCount:=20;
Counter_NN:=0;
//输出原始数组
PrintIntArray(@a[0], iCount);
//排序:奇数在前，偶数在后，并且不改变原来的顺序
for i := 0 to iCount - 2do
begin
if px(@a, @a[i + 1], i, iCount) then
Break;
end;

//输出排序后的数组
PrintIntArray(@a[0], iCount);
Edit1.Text:=IntToStr(Counter_NN);
end;

//结果如下
3
5
19
33
35
11
99
71
73
2
4
8
20
22
10
98
96
94
92
90
//你的排序是正确的，但是请看
Edit1.text=51

lijun4183： 就算递归时间复杂度满足，但是递归用了栈空间，和N相关，空间不满足。
否则我开个数组就可以了，何必那么麻烦。

这个太简单了吧， 就是一般的排序算法而已，
只不过，你把 所有的奇数都 看得比偶数小就可以了

呵呵，楼主的意思就是不增加辅助数组空间。
估计jeffrey_s的代码就是最简洁的代码了，递归是使用了栈的空间不假，
而且从理论上讲使用了n个数中的偶数个数的空间，因为偶数是直到最后才被决定放入的。
我的代码也可以用，和jeffrey_s的思想差不多。
这应该就是最好的符合楼主意思的解法了。
我们没有显式的使用任何辅助空间。
》》不加额外的存储空间指的是不能新建数组、链表等大小与N有关的空间，常量级的空间，比如交换A、B变量的第三变量temp，或者循环控制变量i之类的，都是可以用的。
SS2000：谁都知道开个数组就可以，你这个人咋这么喜欢跟人较劲。你要是有本事，自己想一个你认为好的算法来试试。认真看看别人程序！！！
这个题本来就是一个钻牛角尖的题目，我估计出题者就只是为了考试递归的引用。相信大家在实际中谁也不会这样用。

我不知道这个题是否有正解，我现在也作不出来，如果说递归算可以，那就可以呗。
我不是考官，只是说明我的看法。递归是隐含用了空间的（栈空间），而且和N有关。
仅此而已。

我怀疑此题无解。不考虑顺序，倒是很简单的了。上面好多都给出了。

呵呵，俺承认俺的算法，最终交换的次数可能会多于n
函数调用不仅仅是函数内部声明的变量要占用栈空间，函数传递的变量、函数的返回地址都要使用栈的，所以，递归下来，栈空间的使用不一定就比开个同等大小的数组所使用的栈空间要小。
要是谁拿这样的问题面试我，那我会直接告诉它结果我可以给你整出来，但是别限制我用啥方法[]，要是非要可丁可卯，那我不会

要求时间复杂度为 O 确实比较难， 通过一遍扫描就得搞定，
而且，还要保证奇数和偶数原来的顺序
不知道有没有正解

呵呵，想不到0分的帖子竟然被点击上千次了 8-D
我觉得似乎可以在AI_Player兄的一遍扫描统计的基础上，将数组划分为两个部分，然后
用两个指针进行奇偶性扫描，进行互换。这样一来，两边的奇偶性就确定了，最后，我们再
对两边被“换”过来的数进行重排，让它们恢复到原来的次序——当然，这需要一点技巧
—— Working