Question

pascal的问题

1.最快的排序.哪一个排序是最好，就是一遇到要排序的题目就可以立刻用。不会怕超时，或者规模过大。听说有的排序,例如快速排序不稳定，
但快速排序的最坏情况是不是也不会错呢?例如在NOIP遇到排序用什么排序就一定不会错呢？
2.指针对与NOIP来说有必要学吗?有的话请举例
冒泡几乎都是超时的.

Answer 1

排序
排序是数据处理中经常使用的一种重要运算。所谓排序就是将n个记录按某一个（也可以有多个）关键字大小递增或递减重新排列。常见的排序算法有：选择排序、交换排序（又可以分为冒泡排序、快速排序等）、插入排序（又可以分为直接插入排序、希尔排序等）、归并排序等。

1、选择排序
【例2】 从键盘输入若干个数，用选择排序法将它们按照从小到大的顺序存储并输出。
【问题分析】
假设n个数存放数组a中，下标编号从1到n。选择排序法的思想为：将整个排序过程分为n-1趟进行，每一趟排序的作用，是将当前剩下的数里面最小的找出来放在它应该在的位置上。即先用a[1]和其它各个元素a[j]（j从2到n，即从a[2]到a[n]）进行比较，如果a[j]<a[1]，则交换a[1]和a[j]，这称为“一趟”，一趟结束后a[1]中存放的便是所有元素中的最小数了。然后再用a[2]和其它剩下的各个元素a[j]（j从3到n，即从a[3]到a[n]）进行比较，如果a[j]<a[2]，则交换a[2]和a[j]，这一趟结束后a[2]中存放的便是剩下的元素中的最小数了（即原n个数中第2小的）。以此类推，经过n-1趟后，所有元素必然是从小到大排列的了。
算法实现时需要用一个两重循环，外层循环用来控制第几趟，内层循环用来逐个比较从剩余数中找出最小数。排序过程示例如下：
待排序的数据：53 33 19 13 3 63 82 20 9 39
第一趟排序后：3 53 33 19 13 63 82 20 9 39
第二趟排序后：3 9 53 33 19 63 82 20 13 39
第三趟排序后：3 9 13 53 33 63 82 20 19 39
第四趟排序后：3 9 13 19 53 63 82 33 20 39
第五趟排序后：3 9 13 19 20 63 82 53 33 39
第六趟排序后：3 9 13 19 20 33 82 63 53 39
第七趟排序后：3 9 13 19 20 33 39 82 63 53
第八趟排序后：3 9 13 19 20 33 39 53 82 63
第九趟排序后：3 9 13 19 20 33 39 53 63 82
这样10个数，在经过9趟排序后就全部有序了（带方框的数表示在某趟结束后已有序）。
参考程序如下：
program ex3（input,output）；
const n=10； {假设有10个数据需排序}
var a:array[1..n] of integer；
i,j,temp:integer；
begin
randomize； {启动随机数开关}
for i:=1 to n do a[i]:=random(100)； {产生n个0~100之间的随机整数}
writeln(‘array a:')；
for i:=1 to n do write(a[i]:3)；
writeln； {输出原始数据}
for i:=1 to n-1 do
for j:=i+1 to n do
if a[j]<a[i] then
begin
temp:=a[i]； a[i]:=a[j]； a[j]:=temp；{交换a[i]和a[j]}
end；
write(‘Result：')；
for i:=1 to n do write(a[i]:3)；
writeln； {输出排序结果}
end.
运行看结果：
array a:53 33 19 13 3 63 82 20 9 39
Result：3 9 13 19 20 33 39 53 63 82

2、冒泡排序
【例3】 用冒泡排序法把读入的n个元素按照非递减的顺序存放并输出。
【问题分析】
算法思想：相邻两个元素逐个比较（a[1]与a[2]，a[2]与a[3]，a[3]与a[4]，……，a[n-1]与a[n]），若“逆序”，即前面的元素大于后面的元素了，则交换两个数。就象水中的气泡一样，大的会不段往上冒（冒泡法概念的由来），这样一轮（俗称一趟）下来，我们会发现，最大的数一定存放在了数组的最后一个位置上了。
下一轮，再对a[1..n-1]按照这样的方法，进行同样的操作，则一定会把剩下的数里最大的一个放在了最后，这样经过n–1趟后，排序结束，数组一定是有序的了。
在程序实现时，为了提高效率还做了一个优化，即增加一个布尔型变量exchange，每趟排序前把exchange:=false，表示无交换，一旦发生了数据交换则把exchange:=true。当一趟结束后若exchange的值为false，则说明这一趟没有发生任何数据交换，那么所有数据都有序了，这是就不再需要后面的排序了，可以提前结束循环；否则值为true，则说明排序还未结束，继续做下一趟。
参考程序如下：
Program ex4(input，output)；
const n = 10；
var a:array[1..n] of integer；
i，k，t:integer；
exchange:boolean；
begin
for i:= 1 to n do read(a[i])；
readln；
k:=n； {k为计数器，控制n-1次}
repeat
exchange:=false；
for i:=1 to k-1 do
if a[i]>a[i+1] then
begin
t:=a[i+1]；a[i+1]:=a[i]；a[i]:=t；
exchange:=true；
end；
k:=k-1；
until (k = 1) or not exchange；
for i:=1 to n do write(a[i]:6)；
writeln
end.

【小结】 冒泡排序是基于“不断交换”的思想。如果原始数据本身就“有序”，需一趟排序即可完成，比较次数总共为n-1次；如果原始数据“逆序”，需n-1趟排序，比较次数总共为： 。

3、快速排序
【例4】 利用快速排序法把随机产生的max个元素按照非递减的顺序存放并输出。
【问题分析】
选择排序和冒泡算法的效率都不是很高，主要原因在于过多的比较（if）语句和交换语句，其实有很多这样的操作是多余的。而且他们都是从一边进行的，而快速排序是从两头进行的一种高效排序方法，对我们初学者和一般的比赛要求而言，快速排序是最理想、也是用的最多的一种排序方法。
快速排序的思想如下：假设要对A[1..n]进行排序，初始时设头指针i=1，尾指针j=n。先选择某一个元素X（一般取中间那个，即X=a[（i+j） div 2]），从两头(A[i]、A[j])开始逐个与X比较，找到左边比它大的那个元素A[i]和右边比它小的那个元素A[j]，则交换A[i]与A[j] ，一举两得，然后i：=i+1、j:=j-1，再继续进行，直到i>j。则这一趟结束，X一定排在了它应该在的位置上了。然后，对X左右两边的部分进行类似的递归操作。实际上是一种二分思想，即把大于某个数的所有数交换到它的右边，而把小于它的数都交换到左边。如此这般递归下去，直到都符合要求为止。
参考程序如下：
program ex5(input，output)；
const max = 100；
var a:array[1..max] of longint；
i:longint；

procedure qsort(l，r: longint)；
var i，j，mid，tmp: longint；
begin
i:=l；j:=r；
mid:=a[(l+r) div 2]；
repeat
while a[i]<mid do inc(i)； {i:=i+1}
while mid<a[j] do dec(j)； {j:=j-1}
if i<=j then begin
tmp:=a[i]；a[i]:=a[j]；a[j]:=tmp；
inc(i)；dec(j)；
end；
until i>j；
if l<j then qsort(l，j)；
if i<r then qsort(i，r)；
end；

begin {main}
writeln('Creating '，Max，' random numbers between 1 and 30000')；
randomize；
for i:=1 to max do a[i]:=random(30000)；
writeln('Sorting...')；
qsort(1，max)；
for i:=1 to max do write(a[i]:8)；
end.

4、直接插入排序
【问题分析】
假设待排序数据存放在数组A[1..n]中，则A[1]可看作是一个有序序列，让i从2开始，依次将A[i]插入到有序序列A[1..i-1]中，A[n]插入完毕则整个过程结束，A[1..n]成为有序序列。示例如下（用【 】表示有序序列）：
待排序数据： 【25】 54 8 54 21 1 97 2 73 15 （n=10）
i=2： 【25 54】 8 54 21 1 97 2 73 15
i=3： 【8 25 54】 54 21 1 97 2 73 15
i=4： 【8 25 54 54】 21 1 97 2 73 15
i=5： 【8 21 25 54 54】 1 97 2 73 15
i=6： 【1 8 21 25 54 54】 97 2 73 15
i=7： 【1 8 21 25 54 54 97】 2 73 15
i=8： 【1 2 8 21 25 54 54 97】 73 15
i=9： 【1 2 8 21 25 54 54 73 97】 15
i=10： 【1 2 8 15 21 25 54 54 73 97】 排序结束
算法实现时，可以在数组中增加元素A[0]作为关键值存储器和循环控制开关。第i趟排序，即A[i]的插入过程为：
① 保存A[0]：=A[i]；
② j:=j-1；
③ 如果A[j]<=A[0]（即待排序的A[i]），则A[j+1]：= A[0]，完成插入；
否则，将A[j]后移一个位置：A[j+1]：= A[j]；j:=j-1；继续执行③。
对于上面的数据实例，i从2依次变化到10的过程中，j值分别为{1，0，3，1，0，6，1，7，3}。参考程序如下：
program ex6(input，output)；
const n=100;
var a:array[0..n] of integer;
i,j:integer;
begin
randomize;
for i:=1 to n do a[i]:=random(1000);
for i:=2 to n do
begin
a[0]:=a[i];
j:=i-1;
while a[j]>a[0] do
begin
a[j+1]:=a[j];
j:=j-1;
end;
a[j+1]:=a[0];
end;
for i:=1 to n do write(a[i]:4);
readln;
end.

【小结】 如果原始数据本身“有序”，则总比较次数为：n-1次；如果原始数据“逆序”，总的比较次数为： 如果原始数据无序，第i趟平均比较次数= 次，总的比较次数为： 可见，原始数据越趋向正序，比较次数和移动次数越少。

5、希尔（Shell）排序
【问题分析】
（1）基本思想：
任取一个小于n的整数S1作为增量，把所有元素分成S1个组。所有间距为S1的元素放在同一个组中。
第一组：{A[1]，A[S1+1]，A[2*S1+1]，……}
第二组：{A[2]，A[S1+2]，A[2*S1+2]，……}
第三组：{A[3]，A[S1+3]，A[2*S1+3]，……}
……
第S1组：{A[S1]，A[2*S1]，A[3*S1]，……}
先在各组内进行直接插人排序；然后，取第二个增量S2（<S1）重复上述的分组和排序，直至所取的增量St=1（St<St-1<St-2<……<S2<S1），即所有记录放在同一组中进行直接插入排序为止。

（2）排序过程示例：
序 号 1 2 3 4 5 6 7 8 9 10
原始数据 12 89 57 32 96 37 54 5 79 57
S1=5 组 别 ① ② ③ ④ ⑤ ① ② ③ ④ ⑤
排序结果 12 54 5 32 57 37 89 57 79 96
S2=3 组 别 ① ② ③ ① ② ③ ① ② ③ ①
排序结果 12 54 5 32 57 37 89 57 79 96
S3=2 组 别 ① ② ① ② ① ② ① ② ① ②
排序结果 5 32 12 37 57 54 79 57 89 96
S4=1 组 别 ① ① ① ① ① ① ① ① ① ①
排序结果 5 12 32 37 54 57 57 79 89 96

（3）算法实现：
由于在分组内部使用的是直接插入排序，因此排序过程只要在直接插入排序的算法上对j的步长进行修改就可以了。

（4）参考程序如下：
program ex7(input，output)；
const n=100;
var a:array[0..n] of integer;
i,j,s,k:integer;
begin
randomize;
for i:=1 to n do a[i]:=random(1000);
s:=n;
repeat
s:=round(s/2); {设置增量S递减}
for k:=1 to s do {对S组数据分别进行直接插入排序}
begin
i:=k+s; {一组当中的第2个待排序数据}
while i<=n do {当i>n时，本组数据排序结束}
begin
a[0]:=a[i];
j:=i-s; {当前元素a[i]的前一个元素为a[j]}
while (j>=k) and (a[j]>a[0]) do
{如果这两个复合条件改成(j>=k) and (a[j]>a[0])，编译就会出问题，请思考为什么？}
begin
a[j+s]:=a[j];
j:=j-s;
end;
a[j+s]:=a[0];
i:=i+s;
end;
end;
until s=1;
for i:=1 to n do write(a[i]:4);
readln;
end.

（5）小结：
Shell排序的执行时间依赖于增量序列。如实例所示，选择增量系列为5-2-1的比较次数小于增量系列为5-3-2-1的比较次数，请自己分析看看。
在直接插入排序中，数据越趋向于有序，比较和移动次数越少，Shell排序的目的则是增加这种有序趋势。虽然看起来重复次数较多，需要多次选择增量，但开始时，增量较大，分组较多，但由于各组的数据个数少，则比较次数累计值也小，当增量趋向1时，组内数据增多，而所有数据已经基本接近有序状态，因此，Shell排序的时间性能优于直接插入排序。

6、归并排序
【问题分析】
归并排序是利用"归并"技术来进行排序。归并是指将若干个已排序的子文件合并成一个有序的文件。在学归并排序前，我们先来了解“两路归并算法”。
（1）两路归并算法
设有两个有序（假设为升序）序列存储在同一数组中相邻的位置上，不妨设为A[l..m]，A[m+1..h]，将它们归并为一个有序数列，并存储在A[l..h]。为了减少数据移动次数，不妨采用一个临时工作数组C，将中间排序结果暂时保存在C数组中，等归并结束后，再将C数组值复制给A。归并过程中，设置p1，p2和p3三个指针，其初值分别指向三个有序区的起始位置。归并时依次比较A[p1]和A[p2]的关键字，取关键字较小的记录复制到C[p3]中，然后将被复制记录的指针p1或p2加1，以及指向复制位置的指针p3加1。重复这一过程直至有一个已复制完毕，此时将另一序列中剩余数据依次复制到C中即可。请分析下面的程序：
program ex8;
var a,c:array[1..30] of integer;
i:integer;
procedure merge(L,M,H:integer);
var p1,p2,p3,j:integer;
begin
p1:=L; p2:=M+1;p3:=L;
while (p1<=M) and (p2<=H) do
begin
if a[p1]<=a[p2] then begin
c[p3]:=a[p1]; p1:=p1+1;
end
else begin
c[p3]:=a[p2]; p2:=p2+1;
end;
p3:=p3+1;
end;
if p1>M then for j:=p2 to H do begin c[p3]:=a[j]; p3:=p3+1; end;
if p2>H then for j:=p1 to M do begin c[p3]:=a[j]; p3:=p3+1; end;
for j:=l to H do a[j]:=c[j];
end;
begin {main}
for i:=1 to 10 do a[i]:=2*i-1;
for i:=11 to 30 do a[i]:=2*(i-10);
merge(1,10,30);
for i:=1 to 30 do write(a[i]:8);
readln;
end.

（2）归并排序
归并排序有两种实现方法：自底向上和自顶向下。
自底向上的基本思想是：第1趟归并排序时，将数列A[1..n]看作是n个长度为1的有序序列，将这些序列两两归并，若n为偶数，则得到[n/2]个长度为2的有序序列；若n为奇数，则最后一个子序列不参与归并。第2趟归并则是将第1趟归并所得到的有序序列两两归并。如此反复，直到最后得到一个长度为n的有序文件为止。
上述的每次归并操作，均是将两个有序序列合并成一个有序序列，故称其为“二路归并排序”。类似地有k(k>2)路归并排序。
procedure mergesort;
var i,s,k:integer;
begin
s:=1;
while s<n do
begin
i:=1;
repeat
merge(s*(i-1)+1,s*i,s*(i+1));
i:=i+2;
until i>n;
s:=s*2;
end;
end;

采用分治法进行自顶向下的算法设计，形式更为简洁。设归并排序的当前区间是A[l..h]，分治法的三个步骤是：
分解：将当前区间一分为二，即求分裂点m=(l+h)/2
求解：递归地对两个子区间A[l..m]和A[m+1..h]进行归并排序；
组合：将已排序的两个子区间A[l..m]和A[m+1..h]归并为一个有序的区间A[l..h]。
递归的终结条件：子区间长度为1（一个数据组成的区间必然有序）。
procedure mergesort(l,h:integer);
var m:integer;
begin
if h>l then
begin
m:=(h+l) div 2;
mergesort(l,m); mergesort(m+1,h);
merge(l,m,h);
end;
end;

（3）小结
对于长度为n的数组，需进行[log2n]趟二路归并，每趟归并的时间为O(n)，故其时间复杂度无论是在最好情况下还是在最坏情况下均是O(nlog2n)。

Answer 2

强烈推荐快排，不要怕它不稳定，因为竞赛题目中的数据很少出现快排的最坏情况，而指针是一定要看的，其链表排序也是相当快的。

Answer 3

快速排序比较实用,一般情况下也不会退化,只要把每次选中间的数改成每次随机选数就可以基本避免退化的情况.
指针这种东西,其实不会也没什么,NOIP里面任何需要用指针的地方都可以用数组什么的代替的.

祝LZ好运!

Answer 4

快速排序一定能过。我每次都是用那个，不懂问我。指针都可以用数组代替

Answer 5

看起来你要参加NOIP的竞赛了。Pascal肯定是不错了，快速排序其实不失为一种好的办法，不过求稳还是可以用冒泡的，不过规模很大就是了。

另外，对于你所说的指针，在NOIP中也是有一定的涉及的，学习一下并没有坏处。

NOIP对数据结构的要求挺高的，钻研一下吧