◆稳定排序：假设在待排序的文件中，存在两个或两个以上的记录具有相同的关键字，在
用某种排序法排序后，若这些相同关键字的元素的相对次序仍然不变，则这种排序方法
是稳定的。其中冒泡，插入，基数，归并属于稳定排序，选择，快速，希尔，归属于不稳定排序。 [3]
则称为就地排序。
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比较a[3]与a[4]，以此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]~a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。降序排列与升序排列相类似，若a[1]小于a[2]则交换两者的值，否则不变，后面以此类推。 总的来讲，每一轮排序后最大（或最小）的数将移动到数据序列的最后，理论上总共要进行n(n-1）/2次交换。 [2]
优点：稳定。
缺点：慢，每次只能移动相邻两个数据。
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]<a[j+1] then
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个数进行从小到大排序：
#include <bits/stdc++.h>
using namespace std;
int a[101];
int main()
{
int n;
cin>>n;
for(int i=1;i<=n;i++)//输入数据
cin>>a[i];
for(int i=1;i<n;i++)
{
bool flag=true;
for(int j=1;j<=n-i;j++)
{
if(a[j+1]<a[j])//如果后面的数比前面的数小，则需要交换
{
swap(a[j+1],a[j]);//交换相邻的两个数
flag=false;
}
}
if(flag)//如果在这一轮都没有进行交换，则说明该序列已经有序，不需要进行下一轮
break;
}
for(int i=1;i<=n;i++)//输出排列后的数据
cout<<a[i]<<" ";
cout<<endl;
return 0;
}
指定个数排序：
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.Write(" {0}", num);
}
Console.ReadKey();
}
选择排序是不稳定的排序方法(很多教科书都说选择排序是不稳定的，但是，完全可以将其实现成稳定的排序方法)。
①初始状态：无序区为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-1次）。
缺点：比较次数多，不稳定。
#include<iostream>
#include<time.h>
#include<iomanip>
using namespace std;
const int N=10;
int main()
{
int a[N],i,j,temp,b;
srand(time(NULL));
for(i=0;i<N;i++)
a[i]=rand()%100;
for(i=0;i<N;i++)
cout<<setw(3)<<a[i];
cout<<endl;
for(i=0;i<N-1;i++)
{
temp=i;
for(j=i+1;j<N;j++)
{
if(a[temp]>a[j])
temp=j;
}
if(i!=temp)
{
b=a[temp];
a[temp]=a[i];
a[i]=b;}
}
for(i=0;i<N;i++)
cout<<setw(3)<<a[i];
cout<<endl;
}
public static void selectSort(int[]a)
{
int minIndex=0;
int temp=0;
if((a==null)||(a.length==0))
return;
for(int i=0;i<a.length-1;i++)
{
minIndex=i;//无序区的最小数据数组下标
for(intj=i+1;j<a.length;j++)
{
//在无序区中找到最小数据并保存其数组下标
if(a[j]<a[minIndex])
{
minIndex=j;
}
}
if(minIndex!=i)
{
//如果不是无序区的最小值位置不是默认的第一个数据，则交换之。
temp=a[i];
a[i]=a[minIndex];
a[minIndex]=temp;
}
}
}
插入排序：已知一组升序排列数据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]用相同方法插入。 [1]（若无数组a，可将b[1]当作n=1的数组a）
优点：稳定，快。
如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况。最好情况就是，序列已经是升序排列了，在这种情况下，需要进行的比较操作需（n-1）次即可。最坏情况就是，序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。插入排序的赋值操作是比较操作的次数加上 (n-1）次。平均来说插入排序算法的时间复杂度为O（n^2）。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小为量级小于千，那么插入排序还是一个不错的选择。
/**
*插入排序
*@paramarr
*@return
*/
private static int[] insertSort(int[]arr){
if(arr == null || arr.length < 2){
return arr;
}
for(inti=1;i<arr.length;i++){
for(intj=i;j>0;j--){
if(arr[j]<arr[j-1]){
//TODO:
int temp=arr[j];
arr[j]=arr[j-1];
arr[j-1]=temp;
}else{
break;
}
}
}
return arr;
}
#include<iterator>
template<typenamebiIter>
voidinsertion_sort(biIterbegin,biIterend)
{
typedeftypenamestd::iterator_traits<biIter>::value_typevalue_type;
biIterbond=begin;
std::advance(bond,1);
for(;bond!=end;std::advance(bond,1)){
value_typekey=*bond;
biIterins=bond;
biIterpre=ins;
std::advance(pre,-1);
while(ins!=begin&&*pre>key){
*ins=*pre;
std::advance(ins,-1);
std::advance(pre,-1);
}
*ins=key;
}
}
#include<iterator>
template<typenamebiIter>
voidinsertion_sort(biIterbegin,biIterend)
{
typedeftypenamestd::iterator_traits<biIter>::value_typevalue_type;
biIterbond=begin;
std::advance(bond,1);
for(;bond!=end;std::advance(bond,1)){
value_typekey=*bond;
biIterins=bond;
biIterpre=ins;
std::advance(pre,-1);
while(ins!=begin&&*pre>key){
*ins=*pre;
std::advance(ins,-1);
std::advance(pre,-1);
}
*ins=key;
}
}
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。发现当n不大时，插入排序的效果很好。首先取一增量d(d<n)，将a[1]、a[1+d]、a[1+2d]……列为第一组，a[2]、a[2+d]、a[2+2d]……列为第二组……，a[d]、a[2d]、a[3d]……列为最后一组以次类推，在各组内用插入排序，然后取d'<d，重复上述操作，直到d=1。
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.
int[] a = new int[] { 2, 0, 5, 9, 3, 1, 7 };
int n = a.Length;
int k = n / 2;
while (k > 0)
{
for (int i = k; i < n; i++)
{
int t = a[i];
int j = i - k;
while (j >= 0 && t < a[j])
{
a[j + k] = a[j];
j = j - k;
}
a[j + k] = t;
}
k /= 2;
}
优点：快，数据移动少。
缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。
不需要大量的辅助空间，和归并排序一样容易实现。希尔排序是基于插入排序的一种算法， 在此算法基础之上增加了一个新的特性，提高了效率。希尔排序的时间复杂度为 O(N*(logN)2)， 没有快速排序算法快 O(N*(logN))，因此中等大小规模表现良好，对规模非常大的数据排序不是 最优选择。但是比O（N2）复杂度的算法快得多。并且希尔排序非常容易实现，算法代码短而简单。 此外，希尔算法在最坏的情况下和平均情况下执行效率相差不是很多，与此同时快速排序在最坏 的情况下执行的效率会非常差。 专家门提倡，几乎任何排序工作在开始时都可以用希尔排序，若在实际使用中证明它不够快， 再改成快速排序这样更高级的排序算法. 本质上讲，希尔排序算法的一种改进，减少了其复制的次数，速度要快很多。 原因是，当N值很大时数据项每一趟排序需要的个数很少，但数据项的距离很长。 当N值减小时每一趟需要和动的数据增多，此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。 [1]
快速排序是大家已知的常用排序算法中最快的排序方法。 [4]
已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先任取数据a[x]作为基准。比较a[x]与其它数据并排序，使a[x]排在数据的第k位，并且使a[1]~a[k-1]中的每一个数据<a[x]，a[k+1]~a[n]中的每一个数据>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<j then
begin
a[i]:=a[j];
inc(i);
inc(l);
while (a[i]<t)and(i<j) do
begin
inc(k);
inc(i);
end;
if i<j then begin
a[j]:=a[i];
dec(j);
inc(l);
end;
end;
until i=j;
a[i]:=t;
inc(i);
dec(j);
inc(l);
if z<j then kp(z,j);
if i<y then kp(i,y);
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. [5]
//化分区间,找到最后元素的排序位置。并返回分隔的点（即最后一数据排序的位置）。
//划分的区间是[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;
}
1、箱排序的基本思想
箱排序也称桶排序(Bucket Sort)，其基本思想是：设置若干个箱子，依次扫描待排序的记录R[0]，R[1]，…，R[n-1]，把关键字等于k的记录全都装入到第k个箱子里(分配)，然后按序号依次将各非空的箱子首尾连接起来(收集)。
【例】要将一副混洗的52张扑克牌按点数A<2<…<J<Q<K排序，需设置13个"箱子"，排序时依次将每张牌按点数放入相应的箱子里，然后依次将这些箱子首尾相接，就得到了按点数递增序排列的一副牌。
若R[0..n-1]中关键字的取值范围是0到m-1的整数，则必须设置m个箱子。因此箱排序要求关键字的类型是有限类型，否则可能要无限个箱子。
一般情况下每个箱子中存放多少个关键字相同的记录是无法预料的，故箱子的类型应设计成链表为宜。
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个较小者之间再进行两两比较，如此重复，直至选出最小的记录为止。树形排序的要素就是让所有的左子树都比根及右子树大。 [1]
优点：效率高。
缺点：不稳定。
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.
