把暑假作业发在这里……
排序算法 by:yao1995
给定一个数列a[1..n]，将其从小到大输出，这需要用到排序算法。常见的排序算法有下面几种。
1.选择排序
选择排序，顾名思义就是通过选择进行的排序。每次从数列中拿出最小的一个放在最前面，n个数都选出后，数列自然就是有序的了。
程序（按本人的理解，不过和标准的选择排序不太一样）：
var a:array[0..1001] of longint;
n,i,j,min,t:longint;
begin
assign(input,’sort1.in’);
assign(output,’sort1.out’);
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);//读入
a[0]:=maxlongint;
for i:=1 to n-1 do//共需选择n-1次最小值
begin
min:=0;//初始值为a[0]，即maxlongint
for j:=i to n do//前i-1个已经完成了，要从后n-i+1个中选出最小值
if a[j]<a[min] then min:=j;//如果a[j]小于当前的最小值，记录下a[j]
t:=a[i];a[i]:=a[min];a[min]:=t;//将最小值放在a[i]的位置上
end;
for i:=1 to n-1 do write(a[i],' ');
writeln(a[n]);
close(input);
close(output);
halt;
writeln(‘By: Yao Jiupeng’);
end.
时空分析：选择排序要进行n-1次选择，每次选择平均要进行n/2次比较，时间复杂度为O（n2），对于n比较小的情况适用，当n>5000时就可能会爆掉了。
选择排序是一种原地排序（既不需要开辟新的空间），空间复杂度为O（n）。
2.插入排序
有n张卡片，每张卡片上有一个数字，要求你一张一张地抓起卡片（就是说抓一张卡片时你不知道下一张上的数字是多少），并且保证最后你手中卡片上数字是有序的，该怎么办呢？全部抓完后再进行排序，太麻烦了吧？对了！每次抓完卡片后将它插在相应位置，使手中的卡片总是有序的。插入排序的模型大体就是这样。不过电脑没有人脑那么智慧，不能把数直接插在合适的位置，需要通过交换来找到应当插入的位置。
程 序：
var a:array[0..3001] of longint;
n,i,j,t:longint;
begin
assign(input,’sort2.in’);
assign(output,’sort2.out’);
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);
for i:=2 to n do//将第2~n个元素依次插入到正确的位置，开始时前i个元素已经是递增的
begin
j:=i;//用a[j]表示当前要插入的元素
while a[j]<a[j-1] do
begin
t:=a[j];a[j]:=a[j-1];a[j-1]:=t;//如果a[j]比前一个元素小，就把它和前一个交换
dec(j);
end; //上面的程序可以优化
end;
for i:=1 to n-1 do write(a[i],' ');
writeln(a[n]);
close(input);
close(output);
end.
时空分析：插入排序同样是一种原地排序，空间复杂度为Ο（n）。
按上面的做法，当输入数据已经排好序时，再好不过了，只需将a[i]与a[i-1]进行n-1次比较，不需要进行交换，时间复杂度为O（n）；
当输入数据同样是有序，不过是逆序，这个时候就惨了，每个a[i]都要不断进行交换一直交换到a[1]，时间复杂度为O（n^2）。
总的来说，插入排序比选择排序优一些，100000左右的数据还是能过一部分的。
3.冒泡排序
冒泡排序的思想也是比较简单的，在a[1]..a[n]中，从前到后依次将相邻两个数进行比较，如果前面的数比后面的大，那就不科学了，需要将两个数进行调换。这样下来，其中最大的数就可以像气泡一样“冒”到a[n]的位置了。这样下一轮只需将a[1]..a[n-1]再“冒泡”一次，确定出第二大的数。以此类推。


程 序：
var a:array[0..1001] of longint;
n,i,j,t:longint;
begin
assign(input,’sort3.in’);
assign(output,’sort3.out’);
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);
for i:=n downto 2 do//i代表对前i个元素进行排序
for j:=1 to i-1 do
if a[j]>a[j+1] then//相邻两个元素进行比较
begin
t:=a[j];a[j]:=a[j+1];a[j+1]:=t;//将较大的元素向后“冒泡”
end;
for i:=1 to n-1 do write(a[i],' ');
writeln(a[n]);
close(input);
close(output);
end.
这样需要进行n-1轮冒泡，平均每次需要进行n/2次比较，时间复杂度为O（n^2）。不过我们发现，如果在进行完n-1次冒泡前序列已经有序，那么之后就不会进行交换，也就是说我们做了很多无用功。可以稍加优化：
i:=n;
repeat
p:=0;//表示交换的次数
for j:=1 to i-1 do
if a[j]>a[j+1] then
begin
t:=a[j];a[j]:=a[j+1];a[j+1]:=t;inc(p);
end;
dec(i);
until (p=0) or (i=1);//没有进行交换或已经进行了n-1次冒泡，退出
这样如果某次冒泡没有进行交换，就可知排序已经完成。这样冒泡排序的时间复杂度应该介于选择排序与插入排序之间。
4.桶排序
桶排序可以分为几种，这里介绍最简单的一种。假设数列a1，a2，…，ai，…，an，其中0<ai<=10000且ai属于integer，那么就建立1，2，3，…10000共10000个桶，每读入一个数ai就将其放入第ai个桶，读入完毕后依次将10000个桶扫描一遍，将各个桶中元素输出即可。
程 序：
var a:array[0..1000001] of longint;
n,i,x,t,j:longint;
begin
assign(input,’sort4.in’);
assign(output,’sort4.out’);
reset(input);
rewrite(output);
fillchar(a,sizeof(a),0);
readln(n);
for i:=1 to n do
begin
read(x);
inc(a[x]);//将编号为x的桶中元素个数加1
end;
j:=0;//已输出元素的个数
for t:=1 to 1000000 do
begin
for i:=1 to a[t] do//第t个桶中有a[t]个t，输出a[t]次
begin
inc(j);
if j<n then write(t,' ')
else begin writeln(t);close(input);close(output);halt end;//j=n，输出完毕，退出
end;
end;
close(input);
close(output);
end.
时空分析：桶排序适用于数据范围比较小的情况，如果a[i]>3*107，要当心超空间。
读入、输出过程中均需要n次操作，因此桶排序时间复杂度为O(n)。
5.快速排序
快速排序采用了二分思想和递归的方法。在一组数据中，选出某个值，然后将其他值与这个值比较，较小的放在一边，较大的放在另一边。操作完毕后，得到的两组数据已经互不影响了，再分别对两组数据进行排序，这样下去直到分成的每一组只剩下一个数，排序完毕。如没有特殊要求，大多数情况下采用快速排序。
程 序：
var a:array[0..10000001] of longint;
i,n:longint;
procedure kp(l,r:longint);//快速排序
var i,j,t,x:longint;
begin
i:=l;j:=r;x:=a[(i+j) div 2];
repeat
while a[i]<x do inc(i);
while a[j]>x do dec(j);//找到a[i]>=x,a[j]<=x,进行交换
if i<=j then
begin//交换i、j
t:=a[i];a[i]:=a[j];a[j]:=t;
inc(i);dec(j);
end;


until i>j;//二分完毕，小于x的已经被移到x的左边，大于x的已被移到右边
if i<r then kp(i,r);
if l<j then kp(l,j);//递归，分成的两组继续进行排序
end;
begin//主程序
assign(input,’sort5.in’);
assign(output,’sort5.out’);
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do read(a[i]);
kp(1,n);//进行排序
for i:=1 to n-1 do write(a[i],' ');
writeln(a[n]);
close(input);
close(output);
end.
时空分析：快速排序属于原地排序，空间复杂度为O（n）。
由于采用了二分优化，快速排序平均时间复杂度为O（nlog2n）。最坏情况下，每次选择的x都是分组中的最大值或最小值，这样需要递归n-1次，时间复杂度为O（n2）。
6.堆排序
堆是一棵完全二叉树，分为大根堆（最大堆）和小根堆（最小堆）。我们这里采用大根堆。
对于节点数为n的大根堆，每个节点都有一个数值ai（i=1,2，…，n），且有
ai≥a（i*2）（2*i≤n），ai≥a（i*2+1）（2*i<n）。
我们可以利用这个性质进行建堆，并进行调整，每次取出a[1]即堆中的最大值，从而达到排序的目的。当我们需要维护一个数组中的最大值或最小值时，一般使用堆排序。
程 序：
var i,n,j,k,t:longint;
a:array[0..1000001] of longint;
begin
assign(input,’sort6.in’);
assign(output,’sort6.out’);
reset(input);
rewrite(output);
readln(n);
for i:=1 to n do//建堆
begin
read(a[i]);
j:=i;
while (a[j]>a[j div 2]) and (j>1) do
begin//当前节点比父节点的值大，不符合大根堆的性质，向上调整
t:=a[j];
a[j]:=a[j div 2];
a[j div 2]:=t;
j:=j div 2;end;
end;
for i:=n-1 downto 1 do//调整
begin
t:=a[1];a[1]:=a[i+1];a[i+1]:=t;//a[1]是a[1]到a[i+1]中最大的了，将其拿出，放在a[i+1]位置，堆的规模减少1
j:=2;//a[1]的子节点
while j<=i do//向下调整a[1]
begin
if (j<i) and (a[j]<a[j+1]) then inc(j);//两个子节点中较大的
if a[j]>a[j div 2] then//a[j]>a[j div 2]，不符合大根堆性质，将a[j div 2]向下调整
begin
t:=a[j];a[j]:=a[j div 2];a[j div 2]:=t;
j:=j*2;//调整完毕新的子节点
end
else j:=i+1;//a[j]<=a[j div 2]时，已满足大根堆性质，退出
end;
end;
for i:=1 to n-1 do write(a[i],' ');
writeln(a[n]);
close(input);
close(output);
end.
时空分析：空间复杂度O（n）；
因为采用二分，堆排序时间复杂度为O（nlogn）。
7.其他排序
除上面介绍的排序算法外，排序算法还有希尔排序、归并排序、计数排序等，大家如果感兴趣可以通过查找资料了解或者掌握。
在联赛、竞赛中，一般不会直接考察排序，而是将排序这个知识点隐藏在题目中，只有想到排序这一点，才能打开思路或者优化程序。大家应当学会灵活运用排序算法，并根据不同的题目选择恰当的排序方法。