记录编号	345315	评测结果	AAAAAAAAAA
题目名称	排序测试	最终得分	100
用户昵称	yzc	是否通过	通过
代码语言	Pascal	运行时间	10.303 s
提交时间	2016-11-10 22:18:15	内存使用	6.24 MiB

Program cog637;
    Var
        A:Array[1..2000000]Of Longint;
        I,N,T:Longint;
    Procedure Q(L,R:Longint);
        Var
            I,J,M:Longint;
        Begin
            While L<R Do
                If R-L<7
                    Then Begin
                             For I:=L+1 To R Do
                                 Begin
                                     M:=A[I];
                                     J:=I;
                                     While J>L Do
                                         Begin
                                             If A[J-1]>M
                                                 Then A[J]:=A[J-1]
                                                 Else Break;
                                             Dec(J);
                                         End;
                                     A[J]:=M;
                                 End;
                             Exit;
                         End
                    Else Begin
                             I:=L;
                             J:=R;
                             M:=A[Random(R-L+1)+L];
                             Repeat
                                 While A[I]<M Do Inc(I);
                                 While A[J]>M Do Dec(J);
                                 If I<=J
                                     Then Begin
                                              T:=A[I];
                                              A[I]:=A[J];
                                              A[J]:=T;
                                              Inc(I);
                                              Dec(J);
                                          End;
                            Until I>J;
                            Q(L,J);
                            L:=I;
                        End;
        End;
    Begin
        Assign(Input,'sorttest.in');
        Assign(Output,'sorttest.out');
        Reset(Input);
        Rewrite(Output);
        Readln(N);
        For I:=1 To N Do Read(A[I]);
        Randomize;
        Q(1,N);
        For I:=1 To N-1 Do Write(A[I],' ');
        Writeln(A[N]);
        Close(Input);
        Close(Output);
    End.