program name;

var

a:array[1..N] of 1..MAX;

temp,i,j:integer;

begin

randomize;

for i:=1 to N do a:=1+random(MAX);

writeln('Array before sorted:');

for i:=1 to N do write(a,' ');

writeln;

for i:=N-1 downto 1 do

for j:=1 to i do

if a[j]

begin

temp:=a[j];

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

a[j+1]:=temp

end;

writeln('Array sorted:');

for i:=1 to N do write(a,' ');

writeln;

writeln('End sorted.');

readln;

end.

对N个数进行从小到大排序：

指定个数排序：

static void Main(string[] args)

{

int[] arr = { 4, 2, 5, 7, 4, 9, 6, 21 };

for (int i = 0; i < arr.Length; i++)

{

for (int j = i + 1; j < arr.Length; j++)

{

int temp = 0;

if (arr[i] > arr[j])

{

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

}

}

foreach (int num in arr)

{

}

Console.ReadKey();

}

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

选择排序是不稳定的排序方法(很多教科书都说选择排序是不稳定的，但是，完全可以将其实现成稳定的排序方法)。

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

①初始状态：无序区为R[1..n]，有序区为空。

②第1趟排序

在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

……

③第i趟排序

第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

优点：移动数据的次数已知（n-1次）。

缺点：比较次数多，不稳定。

插入排序：已知一组升序排列数据a[1]、a[2]、……a[n]，一组无序数据b[1]、b[2]、……b[m]，需将二者合并成一个升序数列。首先比较b[1]与a[1]的值，若b[1]大于a[1]，则跳过，比较b[1]与a[2]的值，若b[1]仍然大于a[2]，则继续跳过，直到b[1]小于a数组中某一数据a[x]，则将a[x]~a[n]分别向后移动一位，将b[1]插入到原来a[x]的位置这就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若无数组a，可将b[1]当作n=1的数组a）

优点：稳定，快。

缺点：比较次数不一定，比较次数越多，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1）次。平均来说插入排序算法的时间复杂度为O（n^2）。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小为量级小于千，那么插入排序还是一个不错的选择。

由希尔在1959年提出，是对直接插入排序的优化，又称希尔排序(Shell Sort)。

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。发现当n不大时，插入排序的效果很好。首先取一增量d(d

program Shell;

type

arr=array[1..100] of integer;

var

a:arr;

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

bool:boolean;

begin

readln(n);

for i:=1 to n do

read(a[i]);

d:=n;

while d>1 do

begin

d:=d div 2;

for j:=d+1 to n do

begin

t:=a[j];

i:=j-d;

while (i>0) and (a[i]>t) do

begin

a[i+d]:=a[i];

i:=i-d;

end;

a[i+d]:=t;

end;

end;

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

end.

优点：快，数据移动少。

缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。

不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度为 O(N*(logN)2)， 没有快速排序算法快 O(N*(logN))，因此中等大小规模表现良好，对规模非常大的数据排序不是 最优选择。但是比O（N2）复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏 的情况下执行的效率会非常差。 专家门提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快， 再改成快速排序这样更高级的排序算法. 本质上讲，希尔排序算法的一种改进，减少了其复制的次数，速度要快很多。 原因是，当N值很大时数据项每一趟排序需要的个数很少，但数据项的距离很长。 当N值减小时每一趟需要和动的数据增多，此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。

快速排序是大家已知的常用排序算法中最快的排序方法。

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先任取数据a[x]作为基准。比较a[x]与其它数据并排序，使a[x]排在数据的第k位，并且使a[1]~a[k-1]中的每一个数据a[x]，然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n]两组数据进行快速排序。

优点：极快，数据移动少。

缺点：不稳定。

program kuaipai;

var

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

k,l,n,i:integer;

procedure kp(z,y:integer);

var

i,j,t:integer;

begin

i:=z;

j:=y;

t:=a[i];

repeat

while (a[j]>t)and(j>i) do

begin

inc(k);

dec(j);

end;

if i

begin

a[i]:=a[j];

inc(i);

inc(l);

while (a[i]

begin

inc(k);

inc(i);

end;

if i

a[j]:=a[i];

dec(j);

inc(l);

end;

end;

until i=j;

a[i]:=t;

inc(i);

dec(j);

inc(l);

if z

if i

end;

begin

readln(n);

for i:=1 to n do

read(a[i]);

k:=0;

l:=0;

kp(1,n);

for i:=1 to n do

write(a[i],' ');

end.

//化分区间,找到最后元素的排序位置。并返回分隔的点（即最后一数据排序的位置）。

//划分的区间是[nBegin, nEnd). pData是保存数据的指针

static int Partition(int[] pData, int nBeging, int nEnd)

{

int i = nBeging - 1; //分隔符号，最后nD保存在这里

--nEnd;

int nD = pData[nEnd]; //比较的数据。

int nTemp; // 交换用的临时数据

//遍历数据比较，找到nD的位置，这里注意，比较结果是,

//如果i的左边是小于等于nD的，i的右边是大于nD的

for (int j = nBeging; j < nEnd; ++j)

{

if (pData[j] <= nD) //如果数据比要比较的小，则在该数据的左边，与i+1交换

{

++i; //小于nD的数据多一个，所以要加1，i的左边数据都比nD小

nTemp = pData[i]; //交换数据

pData[i] = pData[j];

pData[j] = nTemp;

}

}

//最后不要忘了吧nD和i+1交换，因为这里就是nD的位置咯。

++i;

pData[nEnd] = pData[i];

pData[i] = nD;

return i; //返回nD的位置，就是分割的位置。

}

//排序的递归调用。

static int QuickSortRecursion(int[] pData, int nBeging, int nEnd)

{

if (nBeging >= nEnd -1) //如果区域不存在或只有一个数据则不递归排序

{

return 1;

}

//这里因为分割的时候，分割点处的数据就是排序中他的位置。

//也就是说他的左边的数据都小于等于他，他右边的数据都大于他。

//所以他不在递归调用的数据中。

int i = Partition(pData, nBeging, nEnd); //找到分割点

QuickSortRecursion(pData, nBeging, i); //递归左边的排序

QuickSortRecursion(pData, i + 1, nEnd); //递归右边的排序

return 1;

}

//快速排序

public static int QuickSort(int[] pData, int nLen)

{

//递归调用，快速排序。

QuickSortRecursion(pData, 0, nLen);

return 1;

}

已知一组无序正整数数据a[1]、a[2]、……a[n]，需将其按升序排列。首先定义一个数组x[m],且m>=a[1]、a[2]、……a[n]，接着循环n次，每次x[a]++。

1、箱排序的基本思想

箱排序也称桶排序(Bucket Sort)，其基本思想是：设置若干个箱子，依次扫描待排序的记录R[0]，R[1]，…，R[n-1]，把关键字等于k的记录全都装入到第k个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。

2、箱排序中，箱子的个数取决于关键字的取值范围。

若R[0..n-1]中关键字的取值范围是0到m-1的整数，则必须设置m个箱子。因此箱排序要求关键字的类型是有限类型，否则可能要无限个箱子。

3、箱子的类型应设计成链表为宜

一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的，故箱子的类型应设计成链表为宜。

4、为保证排序是稳定的，分配过程中装箱及收集过程中的连接必须按先进先出原则进行。

（1） 实现方法一

每个箱子设为一个链队列。当一记录装入某箱子时，应做人队操作将其插入该箱子尾部；而收集过程则是对箱子做出队操作，依次将出队的记录放到输出序列中。

（2） 实现方法二

若输入的待排序记录是以链表形式给出时，出队操作可简化为是将整个箱子链表链接到输出链表的尾部。这只需要修改输出链表的尾结点中的指针域，令其指向箱子链表的头，然后修改输出链表的尾指针，令其指向箱子链表的尾即可。

5、算法简析

分配过程的时间是O(n)；收集过程的时间为O(m) （采用链表来存储输入的待排序记录）或O(m+n)。因此，箱排序的时间为O(m+n)。若箱子个数m的数量级为O(n)，则箱排序的时间是线性的，即O(n)。箱排序实用价值不大，仅适用于作为基数排序的一个中间步骤。

优点：快，效率达到O(1)。

缺点：数据范围必须为正整数并且比较小。

归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。

归并排序是稳定的排序.即相等的元素的顺序不会改变。如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序，这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要，这也是它比快速排序优势的地方。

program guibing;

type

arr=array[1..100] of integer;

var

a,b,c:arr;

i:integer;

procedure gb(r:arr;l,m,n:integer;var r2:arr);

var

i,j,k,p:integer;

begin

i:=l;

j:=m+1;

k:=l-1;

while (i<=m)and (j<=n) do

begin

k:=k+1;

if r[i]<=r[j] then

begin

r2[k]:=r[i];

i:=i+1

end

else

begin

r2[k]:=r[j];

j:=j+1

end

end;

if i<=m then

for p:=i to m do

begin

k:=k+1;

r2[k]:=r[p]

end;

if j<=n then

for p:=j to n do

begin

k:=k+1;

r2[k]:=r[p]

end;

end;

procedure gp( var r,r1:arr;s,t:integer);

var

k:integer;

c:arr;

begin

if s=t then r1[s]:=r[s]

else

begin

k:=(s+t) div 2;

gp(r,c,s,k);

gp(r,c,k+1,t);

gb(c,s,k,t,r1)

end;

end;

begin

readln(n);

for i:= 1 to n do

read(a[i]);

gp(a,b,1,n);

for i:=1 to n do

write(b[i],' ');

writeln;

end.

树形选择排序又称锦标赛排序（Tournament Sort），是一种按照锦标赛的思想进行选择排序的方法。首先对n个记录的关键字进行两两比较，然后在n/2个较小者之间再进行两两比较，如此重复，直至选出最小的记录为止。树形排序的要素就是让所有的左子树都比根及右子树大。

优点：效率高。

缺点：不稳定。

program shupai;

type

point=^nod;

nod=record

w:integer;

right,left:point ;

end;

var

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

root,first:point;

k:boolean;

i:integer;

procedure hyt(d:integer;var p:point);

begin

if p=nil then

begin

new(p);

with p^ do begin

w:=d;

right:=nil;

left:=nil

end;

if k then

begin

root:=p;

k:=false

end;

end

else

with p^ do

if d>=w then

hyt(d,right)

else

hyt(d,left);

end;

procedure hyt1(p:point);

begin

with p^ do

begin

if left<>nil then

hyt1(left);

write(w,' ');

if right<>nil then hyt1(right);

end;

end;

begin

first:=nil;

k:=true;

readln(n);

for i:=1 to n do

read(a[i]);

for i:=1 to n do

hyt(a[i],first);

hyt1(root);

end.