从小到大排序pascal

输入n个正整数，按从小到大的顺序输出。

Input

第一行只有一个正整数：n (1<=n<=1000)
第二行共有n个正整数，数与数之间用一个空格隔开，每一个正整数均不超过3000

Output

共有若干行，每行10个数据，每个数据占用5个字符位置（最后一行可以少于10个数据）

Sample Input

3 5 6 3

Sample Output

3 5 6

不用那么麻烦，最大数才3000，那么就开一个1到3000的数组，读到了加1，然后在跑一遍输出，程序如下：

var
a:array[1..3000] of longint;
i,j,k,m,n:longint;
begin
read(n);
for i:=1 to n do
begin
read(m);
inc(a[m]);
end;
for i:=1 to 3000 do for j:=1 to a[i] do begin write(i:5);inc(k);if k mod 10=0 then writeln;end;
end.

数据不大，使用冒泡排序算法即可，相信你会做（有鼓励成分）

program xxxyy；

var i,j,n,x:integer;

a:array [1..30000] of integer;

procedure getin;

begin

assign(input,'*.in');reset(input);

read(n);

for i:=1 to n do read(a[i]);

close(input);

end;

procedure do1;

begin

for i:=1 to n-1 do begin for j:=i+1 to n do begin if a[i]>a[j] then begin x:=a[i];a[i]:=a[j];a[j]:=x; end; end; end; end;

procedure getout;

begin

assign(output,'*.out');rewrite(output); i:=0; j:=0 repeat inc(i); write(a[i]:5); if (i div 10) > j then begin writeln; inc j; end; until i>=n close(output)

end;

begin

getin;

do1;

getout;

end.

PS:1. 这个程序我没有调试，其正确只能保证85%

2.input 和 output 的文件名是*，这个你自己改吧。

插入排序

插入排序的基本思想是:每次将一个待排序的记录，按其关键字大小插入到前面已经排好的文件中的适当位置，直到全部记录插入完成为止。

4直接插入排序 假设待排序的记录存放在数组R[n]中,排序过程的某一中间时刻,R被划分成两个子区间[R[1],R[i-1]]和[R[i],R[n]],其中:前一个子区间是已排好序的有序区;后一个子区间则是当前未排序的部分，称其为无序区。直接插入排序的基本操作是将当前无序区的第１个记录R[i]插入到有序区中适当位置，使得R[1]到R[i]变为新的有序区。

例如:设待排序的文件有八个记录,其关键字分别为:

49,38,65,97,76,13,27,49^'

为了区别两个相同的关键字49，我们在后一个49右上加了一撇以示区别。排序过程如 下。

[初始关键字] [49] 38 65 97 76 13 27 49^’

i=2(38) [38 49] 65 97 76 13 27 49^’

i=3(65) [38 49 65] 97 76 13 27 49^’

i=4(97) [38 49 65 97] 76 13 27 49^’

i=5(76) [38 49 65 76 97] 13 27 49^’

i=6(13) [13 38 49 65 76 97] 27 49^’

i=7(27) [13 27 38 49 65 76 97] 49^’

i=8(49^') [13 27 38 49 49^’65 76 97]

监视哨temp

算法可描述如下:

Procedure InsertSort(Var R : FileType); {对R[1..N]按递增序进行插入排序, temp是监视哨} Begin for I := 2 To N Do {依次插入R[2],...,R[N]} begin temp := R[I]; J := I - 1; While (temp < R[J]) and(j>0) Do {查找R[I]的插入位置} begin R[J+1] := R[J]; {将大于R[I]的元素后移} J := J - 1 end R[J + 1] := temp ; {插入R[I] } end End; {InsertSort }

参考算法

直接插入排序的时间复杂度为O(n² ),算法是稳定的排序算法

4希尔排序

希尔排序又称缩小增量排序 ，是由D.L.Shell在1959年提出来的。 它的基本思想是：先将整个待排记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次直接插入排序。 它的做法是：先取定一个小于n的整数d₁作为第一个增量 。把文件的全部记录分成d₁个组，所有距离为d1倍数的记录放在同一个组中 ，在各组内进行直接插入排序；然后 ，取第二个增量重复上述分组和排序，直至所取的增量d_t=1（d_t,d_t-1,…,d₂<d₁), 即所有记录放在同一组中进行直接插入排序为止。

根据希尔排序的思想，取d1=n/2，d_i+1=[d_i/2]

例：设待排序文件有10个记录,关键字分别是:49,38,65,97,76,13,27，49^',55,04。增量序列取值依次为：5,3,1。排序过程如图。

[初始关键字] 49 38 65 97 76 13 27 49^’55 04

一趟排序结果： 13 27 49^’55 04 49 38 65 97 76

二趟排序结果： 13 04 49^’38 27 49 55 65 97 76

三趟排序结果： 04 13 27 38 49^’49 55 65 76 97

从上述排序过程可见，希尔排序的一个特点是：子序列的构成不是简单地“逐段分割”，而是将相隔某个“增量”的记录组成一个子序列。如上例中，第一趟排序时的增量为5，第二趟排序时的增量为3。由于在前两趟的插入排序中记录的关键宇是和同一子序列中的前一个记录的关键字进行比较，因此关键字较小的记录就不是一步一步地往前挪动，而是跳跃式地往前移，从而使得在进行最后一趟增量为l的插入排序时，序列已基本有序，只要作记录的少量比较和移动即可完成排序，因此希尔排序的时间复杂度较直接插入排序低。下面用算法语言描述上述希尔排序的过程如下：

PROCEDURE Shellsort（VAR R：FileType); begin k:=1; repeat h:=d[k]; {h为增量值} FOR i:=h+1 TO n DO {将R[h+1]..R[n]分别插入各组当前的有序区} BEGIN temp:=R[i]; j:=i-h; WHILE (temp<R[j]) and (j>0) DO {搜索插入位置} BEGIN R[j+h]:=R[j]; j:=j-h; END; R[j+h]:=temp;{插入R[i]} END; k:=k+1; {取下一个增量} UNTIL h=1;{增量dt=1} END;

希尔排序的时间复杂度为O(nlog₂ n),算法是不稳定的排序算法。 希尔排序的分析是一个复杂的问题，因为它的时间是所取“增量”序列的函数，这涉及一些数学上尚未解决的难题。因此，到目前为止尚未有人求得一种最好的增量序列。但大量的研究已得出一些局部的结论。如有人指出，当增量序列为d[k]＝2^t-k+1-1时，希尔排序的运行时间为O(n^3/2)，其中t为排序趟数。1<=k<=t<=∣log₂(n+1)」。还有人在大量的实验基础上推出：当N在某个特定范围内，希尔排序所需的比较和移动次数约为n^1.3。当n→∞时，可减少到n(log₂n)²。增量序列可以有各种取法，但需注意：应使增量序列中的值没有除1之外的公因子，并且最后一个增量值必须等于1。

交换排序的基本思想：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。本节介绍两种交换排序：起泡排序和快速排序。

起泡排序

起泡排序的过程很简单。设想被排序的记录数组R[1]到 R[n]直竖立,将每个记录R[i]看作是重量为R[i].key的气泡。根据轻气泡不能在重气泡之下的原则，从下往上扫描数组R，凡扫描到违反本原则的轻气泡，就使其向上“飘浮”，如此反复进行，直到最后任何两个气泡都是轻者在上，重者在下为止。

初始时,R[1]到R[n]为无序区，第一趟扫描从该区底部向上依次比较相邻两个气泡的重量,若发现轻者在下，重者在上，则交换两者的位置。本趟扫描完毕时，“最轻”的气泡就飘浮到顶上面，即关键字最小的记录被放在最高位置 R[1]上。第二趟扫描时，只需扫视R[2]到R[n]，扫描完毕时，“次轻”的气泡飘浮到R[2]的位置上。一般地，第i趟扫描时，R[1]到 R[i-1]和R[i] 到R [n]分别为当前的有序区和无序区，扫描仍是从无序区底部向上直至该区顶部，扫描完毕时,该区中最轻的气泡飘浮到顶部位置R[i]上，结果是R[1]到R[i]变为新的有序区。例如:

1 2 3 4 5 6 7

49 13 13 13 13 13 13 13 38 49 27 27 27 27 27 27 65 38 49 38 38 38 38 38 97 65 38 49 49 49 49 49 76 97 65 49' 49' 49' 49' 49' 13 76 97 65 65 65 65 65 27 27 76 97 76 76 76 76 49' 49' 49' 76 97 97 97 97

整个起泡排序过程至多需要进行 n-1 趟排序。但是，若在某一趟排序中未发现气泡位置的交换，则说明待排序的无序区中所有气泡均满足轻者在上，重者在下的原则，因此，起泡排序过程可在此趟排序后终止.

为此，在下面给出的算法中， 引入一个布尔量 noswap，在每趟排序之前，先将它置为True。当一趟排序结束时，再检查noswap,若未曾换过记录便终止算法。

Procedure BubbleSort(Var R : FileType) {从下往上扫描} Begin For I := 1 To N-1 Do {做N-1趟排序} begin NoSwap := True; {置未排序的标志} For J := N - 1 DownTo 1 Do {从底部往上扫描} begin If R[J+1]< R[J] Then {交换元素} begin Temp := R[J+1]; R[J+1 := R[J]; R[J] := Temp; NoSwap := False end; end; If NoSwap Then break{本趟排序中未发生交换，则终止算法} end End; {BubbleSort}

参考程序

容易看出若文件的初始状态是正序的，则一趟扫描就可完成排序，关键字的比较次数为n-1，且没有记录移动。也就是说，起泡排序在最好情况下，时间复杂度是 O(n)。若初始文件是反序的，则需要进行 n-1 趟排序，每趟排序进行 n-i 次关键字的比较(0<=i<= n-2)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值：

Cmax=(n-i)=n(n-1)/2=O(n²)

Mmax=3(n-i)=3n(n-1)/2=O(n²)

因此，起泡排序的最坏时间复杂度为O(n²)。它的平均时间复杂度也是O(n²)。显然，起泡排序是稳定的。

上述起泡排序算法可以为如下的改进：

(１)在每趟扫描中，记住最后一次交换发生的位置k，因为该位置之前的相邻记录都已排了序，所以，下一趟扫描可以终止于位置k，而不必进行到预定的下界1。

(２)在排序过程中交替改变扫描方向。上面曾提到文件的初态为正序时只需做一趟扫描，而文件初态为反序时需做n-1趟扫描。实际上，如果只有最轻的泡位于R[n]的位置，其余的气泡均已排好序 ，那么也只需一趟扫描就可以完成排序。

快速排序

快速排序又称划分交换排序。 它的基本思想是，通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键宇均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。具体做法是在当前无序区R[1]到R[h]中任取一个记录作为比较的“基准”(不妨记为temp), 用此基准将当前无序区划分为左右两个较小的无序子区：R[1]到R[i-1]和R[i+1]到R[h]，且左边的无序子区中记录的关键字均小于或等于基准temp的关键字，右边的无序子区中记录的关键字均大于或等于基准temp的关键字，而基准temp则位于最终排序的位置上,即：R[1]到R[i-1]中关键字<=temp.key<=R[i+1]到R[h]的关键字(1<=i<=h)。当R[1]到R[i-1]和R[i+1]到R[h]均非空时，分别对它们进行上述的划分过程,直至所有无序子区中记录均已排好序为止。

下面是快速排序的过程。方括号表示无序区，上下划线表示基准temp的关键字，它未参加真正的交换，只是在划分完成时才将它放入正确的位置上。 初始关键字： [49 38 65 97 76 13 27 49^’]

一趟排序之后： [27 38 13] 49 [76 97 65 49^’]

二趟排序之后： [13] 27 [38] 49 [49^’ 65] 76 [97]

三趟排序之后： 13 27 38 49 49^’ [65] 76 97

最后的排序结果： 13 27 38 49 49^’ 65 76 97

对当前无序区R[1]到R[h]的划分具体做法：

设置两个指针i和j,它们的初值分为i=1和j=h.不妨取基准为无序的第1个记录R[i](即R[1]),并将它保存在变量temp 中。令j自h起向左扫描，直到找到第1个关键字小于 temp.key的记录R[j]，将R[j]移至i所指的位置上(这相当于交换了R[j]和基准R[i](即temp)的位置，使关键字小于基准关键字的记录移到了基准的左边)；然后，令i自i+1起向右扫描，直至找到第1个关键字大于temp.key的记录R[i],将R[i]移至j指的位置上(这相当于交换了R[i]和基准R[j](即temp)的位置，使关键字大于基准关键字的记录移到了基准的右边)；接着，令j自j-1起向左扫描，如此交替改变扫描方向，从两端各自往中间靠拢，直至i=j时，i便是基准temp的最终位置，将temp放在此位置上就完成了一次划分 。算法可描述如下：

Procedure Parttion(Var R : FileType; L, H : Integer; Var I : Integer); {对无序区R[L,H]做划分，执行算法之后，求得I（L<=I<=H），I为本次划分后已被定位的基准元素的位置。若L<I，则R[L..I-1]中记录的关键字均不大于R[I]的关键字，若I<H，则R[I+1..H]中记录的关键字均不小于R[I]的关键字， } Begin I := L; J := H; temp:= R[I] ;{初始化，temp为基准元素} Repeat While (R[J] >=temp) And (I < J) Do J := J - 1; {从右向左扫描，查找第一个小于 temp的元素} If I < J Then {已找到R[J] 〈temp} begin R[I] := R[J]; {相当于交换R[I]和R[J]} I := I + 1; end; While (R[I] <= temp) And (I < J) Do I := I + 1 {从左向右扫描，查找第一个大于 temp的元素} If I < J Then {已找到R[I] > temp } begin R[J] := R[I]; {相当于交换R[I]和R[J]} J := J - 1 end Until I = J; R[I] := temp {基准temp已被最终定位} End; {Parttion } Procedure QuickSort(Var R :FileType; S,T: Integer); {对R[S..T]快速排序} Begin If S < T Then {当R[S..T]为空或只有一个元素是无需排序} begin Parttion(R, S, T, I); {对R[S..T]做划分} QuickSort(R, S, I-1);{递归处理左区间R[S,I-1]} QuickSort(R, I+1,T);{递归处理右区间R[I+1..T] } end; End; {QuickSort}

快速排序算法性能分析：

最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的无序子区为空(或右边的无序子区为空)，而划分所得的另一个非空的无序子区中记录数目，仅仅比划分前的无序子区中记录个数减少一个。因此, 快速排序必须做n-1趟，每一趟中需进行n-i次比较，故总的比较次数达到最大值：

Cmax= (n-i)=n(n-1)/2=O(n²)

最好情况下，每次划分所取的基准都是当前无序区中的“中值”记录，划分的结果是基准的左、右两个无序子区的长度大致相等。假设文件长度n=2^k，那么总的比较次数为：O(nlog₂n)

因为快速排序的记录移动次数不大于比较的次数，所以，快速排序的最坏时间复杂度应为O(n²)，最好时间复杂度为 O(nlog₂n)。为了改善最坏情况下的时间性能，可采用"三者取中" 的规则，即在每一趟划分开始前，首先比较R[l].key,R[h].key和R[[(l+h)/2]].key,令三者中取中值的记录和R[l]交换。

可以证明：快速排序的平均时间复杂度也是 O(nlog₂n)，它是目前基于比较的内部排序方法中速度最快的，快速排序亦因此而得名。

快速排序是不稳定的。

第六节 线性排序

我们已经知道，通过比较确定两个元素之间相对位置的比较排序算法计算时间复杂性下界为O(nlogn)，要想改进这个下界，就必须对输入的数

计数排序(Counting Sort)

计数排序是一个非基于比较的线性时间排序算法。它对输入的数据有附加的限制条件：

1. 输入的线性表的元素属于有限偏序集S；
2. 设输入的线性表的长度为n，|S|=k（表示集合S中元素的总数目为k），则k=O(n)。

在这两个条件下，计数排序的复杂性为O(n)。

计数排序算法的基本思想是对于给定的输入序列中的每一个元素x，确定该序列中值小于x的元素的个数。一旦有了这个信息，就可以将x直接存放到最终的输出序列的正确位置上。例如，如果输入序列中只有17个元素的值小于x的值，则x可以直接存放在输出序列的第18个位置上。当然，如果有多个元素具有相同的值时，我们不能将这些元素放在输出序列的同一个位置上，因此，上述方案还要作适当的修改。

假设输入的线性表L的长度为n，L=L₁,L₂,..,L_n；线性表的元素属于有限偏序集S，|S|=k且k=O(n)，S={S₁,S₂,..S_k}；则计数排序算法可以描述如下：

1. 扫描整个集合S，对每一个S_i∈S，找到在线性表L中小于等于S_i的元素的个数T(S_i)；
2. 扫描整个线性表L，对L中的每一个元素L_i，将L_i放在输出线性表的第T(L_i)个位置上，并将T(L_i)减1。

具体的实现如下。在以下的讨论中，为了方便，我们假设线性表是用数组来实现的，并且假设线性表的元素类型TElement为整型，其值在1..k之间，线性表的长度为n，且k=O(n)。这些假设对计数排序算法没有实质的影响，但是可以使以下介绍的算法看起来容易理解。

在下面的计数排序算法中，我们假设L为输入的长度为n的线性表，输出的排序结果存放在线性表R中。算法中还用到一个辅助表tmp用于对输入元素进行计数。

Type TElement=1..k; TList=array [1..maxlength] of TElement; procedure Counting_Sort(var L,R:TList); var i,j:integer; tmp:array [1..maxlength] of 0..K-1; begin 1 for i:=1 to k do tmp[i]:=0; 2 for j:=1 to n do inc(tmp[L[j]]); //执行完上面的循环后，tmp[i]的值是L中等于i的元素的个数 3 for i:=2 to k do tmp[i]:=tmp[i]+tmp[i-1]; //执行完上面的循环后，tmp[i]的值是L中小于等于i的元素的个数 4 for j:=n downto 1 do //注意这里的downto保证了排序的稳定性 begin 5 R[tmp[L[j]]]:=L[j];//L[j]存放在输出数组R的第tmp[L[j]]个位置上 6 dec(tmp[L[j]]); //tmp[L[j]]表示L中剩余的元素中小于等于L[j]的元素的个数 end; end;

1. 冒泡排序（稳定排序）

var

a:array[1..10] of integer;

n,i,j,t:integer;

begin

readln(n);

for i:=1 to n do

read(a[i]);

for i:=1 to n-1 do

for j:=n-1 downto i 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 do write(a[i],' ');

writeln

end.

2. 选择排序（不稳定排序）

var

a:array[1..10] of integer;

n,i,k,j,t:integer;

begin

readln(n);

for i:=1 to n do

read(a[i]);

for i:=1 to n-1 do begin

k:=i;

for j:=i+1 to n do

if a[k]<a[j] then k:=j;

t:=a[k];a[k]:=a[i];a[i]:=t;

end;

for i:=1 to n do write(a[i],' ');

writeln

end.

3. 插入排序（稳定排序）

var

a:array[0..10] of integer;

n,i,k,j,t:integer;

begin

a[0]:=-1;

readln(n);

for i:=1 to n do

read(a[i]);

for i:=2 to n do begin

t:=a[i];k:=i-1;

while t<a[k] do begin

a[k+1]:=a[k];

dec(k);end;a[k+1]:=t;end;

for i:=1 to n do

write(a[i],' ');

writeln

end.

冒泡排序： var n:integer; i,j,t:integer; a:array of integer; begin readln(n); setlength(a,n); for i:=0 to n-1 do read(a[i]); readln; for i:=0 to n-1 do for j:=n-1 downto 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:=0 to n-1 do write(a[i],' '); readln; end. 望采纳