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

忙了半天，问题还是出在顺序上——不用递归和数组的话，时间复杂度始终是问题。
下面的代码通过一遍扫描将奇数和偶数分区（统计信息已经在上一步完成），通过简单的
“标记”方法，将每个分区中的数字都分为两种——一种是位置没有动过的“原住民”，另
一种是从另一个分区中交换过来的“拆迁户”，并且，后者的次序是反序排列的。
//Step2: 带标记的奇偶交换 O(N*1)
P_Div:=Low(IntAy)+JCount-1;
//奇偶分界点
P1:=P_Div;
P2:=High(IntAy);
while P2>P_Divdo
//在此，以偶指针P2为主动指针，奇指针P1为从动指针
begin
if IntAy[P2] and $1=0 then
Dec(P2) //偶指针遇到偶数 -> 向头部前进
else
begin
//偶指针遇到了奇数，需要进行奇偶交换
while IntAy[P1] and $1=1do
//奇指针遇到奇数 -- 同上
Dec(P1);
//数据交换——目标：将所有的奇数放都在偶数的左边
//在交换的同时对双方都执行加1的操作，以改变奇偶性，打上“交换标记”，以便后面的次序恢复
// -- 在此采用了两个中间变量，便于阅读 --
TmpInt1:=IntAy[P1]+1;
TmpInt2:=IntAy[P2]+1;
IntAy[P2]:=TmpInt1;
//+1后的偶数
IntAy[P1]:=TmpInt2;
//+1后的奇数
//交换完毕，奇偶指针都要继续前进
Dec(P2);
Dec(P1);
end;
end;

即便完成了奇偶交换，现在又形成了新的问题——将原有的以及被交换过来的数字进行重
组——还是没逃掉。我又写了一个原理简单的纯重组算法（相邻奇偶区块顺序互换），可惜
通过试验，复杂度为O(n*n)
不过，也许我们能够通过对数组元素的加减运算找到新的窍门也说不定
题目只是要求不能“定义”数组用于数据交换，并没有说要限制空间复杂度（个人认为算
法的指令空间以及执行时所需的运行空间都应该要考虑进去的），jeffrey_s兄的算法干净
利落，佩服啊

呵呵，不再分数多少，主要是问题有意思。
jeffrey_s的实现方式目前来说，应该是最合理的了

如果动用一个以上的辅助存储位置,如栈空间 或数组
可以做到时间复杂度为 O
如果只允许使用一个辅助存储空间,就用直接插入法进行排序,时间复杂度为 O(n*n)

不错的帖子

为何偶的不行?代码简单且循环绝没超过N次呀,哪位测试过的说说!

你的是双重循环，时间复杂度是 O(N*N)

这次绝对只使用了一次N值,只使用了一个while主循环,中间的数据移动使用的while应该不算吧(就是算进去,也不是N*N),各位看看合不合题意
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
type
TForm1 = class(TForm)
Button1: TButton;
Memo1: TMemo;
Edit1: TEdit;
procedure Button1Click(Sender: TObject);
procedure PrintIntArray(pi: PInteger;
ACount: Integer);
private
{ Private declarations }
public
{ Public declarations }
end;

var
Form1: TForm1;
implementation
{$R *.dfm}
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.Button1Click(Sender: TObject);
var
i: Integer;
iCount: Integer;
a: array of Integer;
tempinteger:integer;
j:integer;
jj:integer;
begin
Memo1.Clear;
try
iCount := StrToInt(Edit1.Text);
//可以用Edit中输入指定元素个的数组
except
iCount := 100;
end;
//初始化数组
SetLength(a, iCount);
Randomize;
for i := 0 to iCount - 1do
a := Random(iCount * 2) + 1;
//还是用随机数做测试
//a := i + 1;
//输出原始数组
PrintIntArray(@a[0], iCount);
//新的算法从此开始,只有一个循环,中间的数据移动不应算次数吧?
i:=0;
j:=0;
while i<icountdo
begin
if (a mod 2)=0 then
//是偶数
begin
if j=0 then
tempinteger:=a;
//保存待交换的数据,但暂不交换,仅做偏移记录
j:=j+1;

end else
//当遇到奇数
begin
//偏移变量>0时才交换
if j>0 then

begin
if j=1 then
//仅隔一位是偶数的情况,就直接做交换
begin
a[i-j]:=a;
//先前位数据=当前位数据
a:=tempinteger;
//当前位=先前位
end else
begin
//连续偶数的情况,先将偶数数据全部后移,然后再交换
tempinteger:=a;
//先保存当前位奇数值
jj:=0;

while jj<=jdo
//将偶数数据后移
begin

a[i-jj]:=a[i-jj-1];//a:=a[i-1]
jj:=jj+1;
end;
a[i-j]:=tempinteger;
//先前位数据=当前位数据
end;
i:=i-j+1;
//原位置交换位的下一位
j:=0;
//交换后将偏移置为0
continue;

end;
end;
i:=i+1;
end;
//----------------算法结束--------------------------
//输出排序后的数组,查看结果是否正确
PrintIntArray(@a[0], iCount);
end;

end.

那你说直接插入法排序的时间复杂度是多少呢？
数据移动也是要有开销的

偶也不知道该如何算,因为本算法是因奇偶数的不同而运行的次数不同的.但可以将随机数组理想话(大量的随机数组测试的话,应该趋于奇偶均匀分布)，所以我们可以用数组1..100来作测试来计算算法的的运行次数．
如果我们的数组是1..100的话,N*N=10000,偶在程序中加入一个计数器X来计算回退指针的次数,得到的结果是1325次指针移动(0..N的主循环+x回退指针操作的次数),程序如下:
procedure TForm1.Button1Click(Sender: TObject);
var
i: Integer;
iCount: Integer;
a: array of Integer;
tempinteger:integer;
j:integer;
jj:integer;
x:integer;
//回退操作计数器
begin
Memo1.Clear;
try
iCount := StrToInt(Edit1.Text);

except
iCount := 100;
end;
//初始化数组
SetLength(a, iCount);
Randomize;
for i := 0 to iCount - 1do
//a := Random(iCount * 2) + 1;
//不用随机数做测试
a := i + 1;
//使用1..100数据,平均分布奇偶数
//输出原始数组
PrintIntArray(@a[0], iCount);
//新的算法从此开始
i:=0;
j:=0;
x:=0;
while i<icountdo
begin
if (a mod 2)=0 then
//是偶数
begin
if j=0 then
tempinteger:=a;
//保存待交换的数据,但暂不交换,仅做偏移记录
j:=j+1;

end else
//当遇到奇数
begin
//偏移变量>0时才交换
if j>0 then

begin
if j=1 then
//仅隔一位是偶数的情况,就直接做交换
begin
a[i-j]:=a;
//先前位数据=当前位数据
a:=tempinteger;
//当前位=先前位
x:=x+1;
//指针回退1位,计数器+1;
end else
begin
//连续偶数的情况,先将偶数数据全部后移,然后再交换
tempinteger:=a;
//先保存当前位奇数值
jj:=0;
while jj<=jdo
//将偶数数据后移
begin

a[i-jj]:=a[i-jj-1];//a:=a[i-1]
jj:=jj+1;
end;
a[i-j]:=tempinteger;
//先前位数据=当前位数据
x:=x+j;
//指针回退j位,这里计数
end;
i:=i-j+1;
//原位置交换位的下一位
j:=0;
//交换后将偏移置为0
continue;

end;
end;
i:=i+1;
end;
//----------------算法结束--------------------------
//输出排序后的数组,查看结果是否正确
PrintIntArray(@a[0], iCount);
showmessage(inttostr(icount+X));
//结果是1325次
end;

end.

再次想了想,觉得不能将数据移动的部份计入在内.否则,即便允许使用辅助空间,次数也绝对大于N(在有辅助空间时,先是检出偶数,已经遍列了一次,然后排序到另一空间,又是一次,最后覆盖回原数组，又是一次，这样岂不是N+N+N了，那么就永远无法满足题意了.当然，也不一定就是这样操作，也可以用二维数组来捡出来时同时记住原数组下标，然后直接覆盖回原数组的相应下标单元中，这样也是N+N，但这样也是N+N呀!)
push pop movsb sort 等操作也是要花时间的．要绝对的0(N)那就办不到了

用最苯的方法用一无限循环
每次循环都把奇数向前一位.并记录下有多少次向前移动奇数的次数.
直到到一次都没有的时候就退出来.这样奇数就跑到前面去了.

对于时间复杂度来说，3*N, 1000*N 都认为是 O（N）
说的是所用时间和 任务个数的关系，
O(N) 表示和 N成线性关系
O（N×N）表示和 N*N 成线性关系
这里区别就大了，尤其是随着元素个数的增加，

jeffrey_s 的算法我测了，数组长度 50000 以内的时间复杂度0，再长就溢出了，没测
个人认为这是最好的办法了

如果是排了還要按照順序的話，就沒有答案了，O（N）是什么概念噢。。。如果是從後面開始的話兩兩交換就可以實現了，但有序就不可能了