2009年4月 总版技术专家分月排行榜第一
2009年11月 Linux/Unix社区大版内专家分月排行榜第一2009年6月 Linux/Unix社区大版内专家分月排行榜第一2009年4月 C/C++大版内专家分月排行榜第一2009年3月 C/C++大版内专家分月排行榜第一2009年3月 Linux/Unix社区大版内专家分月排行榜第一2009年2月 Linux/Unix社区大版内专家分月排行榜第一
本帖子已过去太久远了，不再提供回复功能。C++中十种内部排序算法的比较分析
投稿：hebedich
字体：[ ] 类型：转载 时间：
本文给大家分享的是个人写的一段对C++中十种内部排序算法的比较分析的代码，主要在于测试10种排序方法的性能，给大家参考下吧。
C++中十种内部排序算法的比较分析
#include&iostream&
#include&ctime&
#include&fstream&
#define MAXSIZE 1000
//可排序表的最大长度
#define SORTNUM 10
//测试10中排序方法
#define max 100
//基数排序时数据的最大位数不超过百位；
typedef struct node {
int data3;
typedef int DataType[MAXSIZE+2];
DataType data2;
DataType R1;
//可排序表的长度
int fr[10];
int re[10];
long compC//统计比较次数
long shiftC//统计移动次数
void BeforeSort()//对比较次数和移动次数清零
compCount=0;
shiftCount=0;
bool Less(int i,int j)//若表中第i个元素小于第j个元素，则返回True，否则返回False
compCount++;
return data[i]&data[j];
void Swap(int i,int j)//交换表中第i个和第j个元素
a=data[i];
data[i]=data[j];
data[j]=a;
shiftCount=shiftCount+3;
void Shift(DataType &R,DataType &R2,int i,int j)//将R2[j]赋给R[i]
R[i]=R2[j];
shiftCount++;
void CopyData(DataType list1,DataType list2)
for(i=1;i&=i++) list2[i]=list1[i];
void InverseOrder()//将可排序表置为逆序
for(i=1,j=i&=size/2;i++,j--)
a=data[i];
data[i]=data[j];
data[j]=a;
CopyData(data,data2);
void RandomizeList()//由系统随机一组数
srand(time(0));
for(i=1;i&=i++)
data[i]=rand()%(size+1);
CopyData(data,data2);
ofstream out_
out_stream.open("input.txt",ios::app);
if(out_stream.fail())
cout&&"input file opening failed.\n";
for(i=1;i&=i++) out_stream&&data[i]&&" ";
out_stream&&"\n";
out_stream.close();
void RecallList()//恢复最后一次用RandomizeList随机打乱的可排序表
CopyData(data2,data);
void output()//输出函数
ofstream out_
cout&&"\t"&&compCount&&"\t\t"&&shiftCount&&"\n";
out_stream.open("output.txt",ios::app);
if(out_stream.fail())
cout&&"Output file opening failed.\n";
out_stream&&"\t"&&compCount&&"\t\t"&&shiftCount&&"\n";
out_stream.close();
void BubbleSort()//冒泡排序
BeforeSort();
int swapped,i,m;
swapped=0;
for(i=1;i&=m;i++)
if(Less(i+1,i))
Swap(i+1,i);
swapped=1;
}while(swapped);
void InsertSort() //插入排序
BeforeSort();
for(i=2;i&=i++)
Shift(data,data,0,i);
while(Less(0,j))
Shift(data,data,j+1,j);
Shift(data,data,j+1,0);
void SelectSort()//选择排序
BeforeSort();
for(i=1;i&=size-1;i++)
for(j=i+1;j&=j++)
if(Less(j,min)) min=j;
if(i!=min) Swap(i,min);
int Partition(int low,int high)
Shift(data,data,0,low);
pivotkey=data[low];
while(low&high)
compCount++;
while(low&high&&data[high]&=pivotkey) {compCount++;--}
Shift(data,data,low,high);
compCount++;
while(low&high&&data[low]&=pivotkey) {compCount++;++}
Shift(data,data,high,low);
Shift(data,data,low,0);
void QSort(int low,int high)//QuickSort的辅助函数
if(low&high)
pivotloc=Partition(low,high);
QSort(low,pivotloc-1);
QSort(pivotloc+1,high);
void QuickSort()//快速排序
BeforeSort();
QSort(1,size);
void ShellSort()//希尔排序
BeforeSort();
int i,j,h;
while(i&=size)
while (h!=0)
while(i&=size)
while(j&0&&Less(j+h,j))
Swap(j,j+h);
h=(h-1)/2;
void Sift(int left,int right)//堆排序的调堆函数
int i,j,finished=0;
Shift(data,data,0,left);
Shift(data,data,MAXSIZE+1,left);
while(j&=right&&!finished)
if(j&right&&Less(j,j+1)) j=j+1;
if(!Less(0,j)) finished=1;
Shift(data,data,i,j);
Shift(data,data,i,MAXSIZE+1);
void HeapSort()//堆排序
BeforeSort();
for(left=size/2;left&=1;left--) Sift(left,size);
for(right=right&=2;right--)
Swap(1,right);
Sift(1,right-1);
void BInsertSort()//折半插入排序
BeforeSort();
int i,low,high,m,j;
for(i=2;i&=i++)
Shift(data,data,0,i);
while(low&=high)
m=(low+high)/2;
if(Less(0,m)) high=m-1;
else low=m+1;
for(j=i-1;j&=high+1;j--) Shift(data,data,j+1,j);
Shift(data,data,high+1,0);
void Binsort()//2-路插入排序
BeforeSort();
int i,k,j;
int first,
first=last=1;
Shift(R1,data,1,1);
for(i=2;i&=i++)
compCount++;
if(data[i]&=R1[1])
compCount++;
while(j&=1&&R1[j]&data[i])
Shift(R1,R1,j+1,j);
compCount++;
Shift(R1,data,j+1,i);
if(first==0) first=
j=first+1;
compCount++;
while(j&=size&&R1[j]&=data[i])
Shift(R1,R1,j-1,j);
compCount++;
Shift(R1,data,j-1,i);
while(k&=size)
Shift(data,R1,k,j);
j=(j+1)%(size+1);
if(j==0) j=j+1;
void Merge(int low,int m,int high)
int i=low,j=m+1,p=1;
while(i&=m&&j&=high)
if(Less(i,j)) Shift(R1,data,p++,i++);
else Shift(R1,data,p++,j++);
while(i&=m)
Shift(R1,data,p++,i++);
while(j&=high)
Shift(R1,data,p++,j++);
for(p=1,i=i&=p++,i++)
Shift(data,R1,i,p);
void MSort(int low, int high)
if (low&high){
mid=(low+high)/2;
MSort(low, mid);
MSort(mid+1,high);
Merge(low, mid, high);
void MergeSort()//归并排序
BeforeSort();
MSort(1,size);
void Distribute(node *a, int w)
for (i=0; i&10; i++) fr[i] = -1;
for (i= i!=-1; i=a[i].next)
int x = a[i].data3 / w % 10;
if (fr[x] == -1)
fr[x] = re[x] =
compCount++;
a[re[x]].next =
shiftCount++;
for (i=0; i&10; i++)
if (fr[i] != -1)
a[re[i]].next = -1;
void Collect(node *a)
last = -1;
for (i=0; i&10; i++)
if (fr[i] != -1)
if (last == -1)
head = fr[i];
last = re[i];
a[last].next = fr[i];
last = re[i];
shiftCount++;
a[last].next = -1;
void RadixSort()//基数排序算法。
BeforeSort();
ofstream out_
a=new node[size];
int i,j=1;
for (i=0; i& i++) {
a[i].data3=data[i+1];
a[i].next = i + 1;
a[size-1].next = -1;
for (i=1; i&= i*=10) {
Distribute(a, i);
Collect(a);
cout&&"\t"&&compCount&&"\t\t"&&shiftCount&&"\n";
while (head != -1)
data[j++]=a[head].data3;
head = a[head].
CopyData(data,data2);
cout&&"\n";
out_stream.open("output.txt",ios::app);
out_stream&&"\t"&&compCount&&"\t\t"&&shiftCount&&"\n\n";
out_stream.close();
void Initialization()//系统初始化
system("cls");//清屏
cout&&"***************************************************************************\n"
&&"***************** 《内部排序算法的比较》 ********************************\n"
&&"***************************************************************************\n"
&&"************************ *主菜单* ***************************************\n"
&&"******* 1.由系统随机产生待排序表 ****************************************\n"
&&"******* 2.手动输入待排序表 **********************************************\n"
&&"******* 3.返回主菜单 ****************************************************\n"
&&"******* 4.退出程序 ******************************************************\n"
&&"***************************************************************************\n"
&&"请输入要执行的步骤：";
void Interpret(int cmd)//调用各个算法
int i,j,m;
ofstream out_
out_stream.open("output.txt",ios::app);
if(out_stream.fail())
cout&&"Output file opening failed.\n";
switch(cmd)
out_stream&&"由系统随机产生待排序表的各个算法的比较次数和移动次数如下:\n";
out_stream&&"\tcompCount\tshiftCount\n";
out_stream.close();
cout&&"请输入待排序表的长度:";
cout&&"由系统随机产生待排序表的各个算法的比较次数和移动次数如下:\n";
RandomizeList();
for(m=0;m&3;m++)
if(m==2) InverseOrder();
cout&&"\t";
for(i=1;i&=i++) cout&&data[i]&&" ";
cout&&"\n";
cout&&"\tcompCount\tshiftCount\n";
for(j=0;j&SORTNUM;j++)
RecallList();
out_stream.open("output.txt",ios::app);
if(j==0) {cout&&"Bubbl: ";out_stream&&"Bubbl: ";out_stream.close();BubbleSort();}
if(j==1) {cout&&"Tnser: ";out_stream&&"Tnser: ";out_stream.close();InsertSort();}
if(j==2) {cout&&"Selec: ";out_stream&&"Selec: ";out_stream.close();SelectSort();}
if(j==3) {cout&&"Quick: ";out_stream&&"Quick: ";out_stream.close();QuickSort();}
if(j==4) {cout&&"Shell: ";out_stream&&"Shell: ";out_stream.close();ShellSort();}
if(j==5) {cout&&"Heap : ";out_stream&&"Heap : ";out_stream.close();HeapSort();}
if(j==6) {cout&&"BInse: ";out_stream&&"BInse: ";out_stream.close();BInsertSort();}
if(j==7) {cout&&"Merge: ";out_stream&&"Merge: ";out_stream.close();MergeSort();}
if(j==8) {cout&&"Bin : ";out_stream&&"Bin : ";out_stream.close();Binsort();}
if(j==9) {cout&&"Radix: ";out_stream&&"Radix: ";out_stream.close();RadixSort();}
cout&&"请输入待排序表的长度：";
cout&&"请输入"&&size&&"个数据:\n";
for(i=1;i&=i++) cin&&data[i];
CopyData(data,data2);
out_stream&&"手动输入待排序表的各个算法的比较次数和移动次数如下:\n";
out_stream&&"\tcompCount\tshiftCount\n";
out_stream.close();
cout&&"手动输入待排序表的各个算法的比较次数和移动次数如下:\n";
cout&&"\tcompCount\tshiftCount\n";
for(j=0;j&SORTNUM;j++)
RecallList();
out_stream.open("output.txt",ios::app);
if(j==0) {cout&&"Bubbl: ";out_stream&&"Bubbl: ";out_stream.close();BubbleSort();}
if(j==1) {cout&&"Tnser: ";out_stream&&"Tnser: ";out_stream.close();InsertSort();}
if(j==2) {cout&&"Selec: ";out_stream&&"Selec: ";out_stream.close();SelectSort();}
if(j==3) {cout&&"Quick: ";out_stream&&"Quick: ";out_stream.close();QuickSort();}
if(j==4) {cout&&"Shell: ";out_stream&&"Shell: ";out_stream.close();ShellSort();}
if(j==5) {cout&&"Heap : ";out_stream&&"Heap : ";out_stream.close();HeapSort();}
if(j==6) {cout&&"BInse: ";out_stream&&"BInse: ";out_stream.close();BInsertSort();}
if(j==7) {cout&&"Merge: ";out_stream&&"Merge: ";out_stream.close();MergeSort();}
if(j==8) {cout&&"Bin : ";out_stream&&"Bin : ";out_stream.close();Binsort();}
if(j==9) {cout&&"Radix: ";out_stream&&"Radix: ";out_stream.close();RadixSort();}
Initialization();
void main()
Initialization();
Interpret(cmd);
}while(cmd!=4);
以上就是本文所述的全部内容了，希望能够对大家熟悉掌握这十种排序算法有所帮助。
您可能感兴趣的文章:
大家感兴趣的内容
12345678910
最近更新的内容
常用在线小工具十种内部排序算法的比较 - 开源中国社区
当前访客身份：游客 [
当前位置：
发布于 日 19时,
代码片段(1)
1.&[代码]主文件&&&&
#include&iostream&
#include&ctime&
#include&fstream&
#define MAXSIZE 1000
//可排序表的最大长度
#define SORTNUM 10
//测试10中排序方法
//基数排序时数据的最大位数不超过百位；
typedef struct node {
int data3;
typedef int DataType[MAXSIZE+2];
DataType data2;
DataType R1;
//可排序表的长度
int fr[10];
int re[10];
long compC//统计比较次数
long shiftC//统计移动次数
void BeforeSort()//对比较次数和移动次数清零
compCount=0;
shiftCount=0;
bool Less(int i,int j)//若表中第i个元素小于第j个元素，则返回True，否则返回False
compCount++;
return data[i]&data[j];
void Swap(int i,int j)//交换表中第i个和第j个元素
a=data[i];
data[i]=data[j];
data[j]=a;
shiftCount=shiftCount+3;
void Shift(DataType &R,DataType &R2,int i,int j)//将R2[j]赋给R[i]
R[i]=R2[j];
shiftCount++;
void CopyData(DataType list1,DataType list2)
for(i=1;i&=i++) list2[i]=list1[i];
void InverseOrder()//将可排序表置为逆序
for(i=1,j=i&=size/2;i++,j--)
a=data[i];
data[i]=data[j];
data[j]=a;
CopyData(data,data2);
void RandomizeList()//由系统随机一组数
srand(time(0));
for(i=1;i&=i++)
data[i]=rand()%(size+1);
CopyData(data,data2);
ofstream out_
out_stream.open("input.txt",ios::app);
if(out_stream.fail())
cout&&"input file opening failed.\n";
for(i=1;i&=i++) out_stream&&data[i]&&" ";
out_stream&&"\n";
out_stream.close();
void RecallList()//恢复最后一次用RandomizeList随机打乱的可排序表
CopyData(data2,data);
void output()//输出函数
ofstream out_
cout&&"\t"&&compCount&&"\t\t"&&shiftCount&&"\n";
out_stream.open("output.txt",ios::app);
if(out_stream.fail())
cout&&"Output file opening failed.\n";
out_stream&&"\t"&&compCount&&"\t\t"&&shiftCount&&"\n";
out_stream.close();
void BubbleSort()//冒泡排序
BeforeSort();
int swapped,i,m;
swapped=0;
for(i=1;i&=m;i++)
if(Less(i+1,i))
Swap(i+1,i);
swapped=1;
}while(swapped);
void InsertSort() //插入排序
BeforeSort();
for(i=2;i&=i++)
Shift(data,data,0,i);
while(Less(0,j))
Shift(data,data,j+1,j);
Shift(data,data,j+1,0);
void SelectSort()//选择排序
BeforeSort();
for(i=1;i&=size-1;i++)
for(j=i+1;j&=j++)
if(Less(j,min)) min=j;
if(i!=min) Swap(i,min);
int Partition(int low,int high)
Shift(data,data,0,low);
pivotkey=data[low];
while(low&high)
compCount++;
while(low&high&&data[high]&=pivotkey)
{compCount++;--}
Shift(data,data,low,high);
compCount++;
while(low&high&&data[low]&=pivotkey)
{compCount++;++}
Shift(data,data,high,low);
Shift(data,data,low,0);
void QSort(int low,int high)//QuickSort的辅助函数
if(low&high)
pivotloc=Partition(low,high);
QSort(low,pivotloc-1);
QSort(pivotloc+1,high);
void QuickSort()//快速排序
BeforeSort();
QSort(1,size);
void ShellSort()//希尔排序
BeforeSort();
int i,j,h;
while(i&=size)
while (h!=0)
while(i&=size)
while(j&0&&Less(j+h,j))
Swap(j,j+h);
h=(h-1)/2;
void Sift(int left,int right)//堆排序的调堆函数
int i,j,finished=0;
Shift(data,data,0,left);
Shift(data,data,MAXSIZE+1,left);
while(j&=right&&!finished)
if(j&right&&Less(j,j+1)) j=j+1;
if(!Less(0,j)) finished=1;
Shift(data,data,i,j);
Shift(data,data,i,MAXSIZE+1);
void HeapSort()//堆排序
BeforeSort();
for(left=size/2;left&=1;left--) Sift(left,size);
for(right=right&=2;right--)
Swap(1,right);
Sift(1,right-1);
void BInsertSort()//折半插入排序
BeforeSort();
int i,low,high,m,j;
for(i=2;i&=i++)
Shift(data,data,0,i);
while(low&=high)
m=(low+high)/2;
if(Less(0,m)) high=m-1;
else low=m+1;
for(j=i-1;j&=high+1;j--) Shift(data,data,j+1,j);
Shift(data,data,high+1,0);
void Binsort()//2-路插入排序
BeforeSort();
int i,k,j;
int first,
first=last=1;
Shift(R1,data,1,1);
for(i=2;i&=i++)
compCount++;
if(data[i]&=R1[1])
compCount++;
while(j&=1&&R1[j]&data[i])
Shift(R1,R1,j+1,j);
compCount++;
Shift(R1,data,j+1,i);
if(first==0) first=
j=first+1;
compCount++;
while(j&=size&&R1[j]&=data[i])
Shift(R1,R1,j-1,j);
compCount++;
Shift(R1,data,j-1,i);
while(k&=size)
Shift(data,R1,k,j);
j=(j+1)%(size+1);
if(j==0) j=j+1;
void Merge(int low,int m,int high)
int i=low,j=m+1,p=1;
while(i&=m&&j&=high)
if(Less(i,j)) Shift(R1,data,p++,i++);
else Shift(R1,data,p++,j++);
while(i&=m)
Shift(R1,data,p++,i++);
while(j&=high)
Shift(R1,data,p++,j++);
for(p=1,i=i&=p++,i++)
Shift(data,R1,i,p);
void MSort(int low, int high)
if (low&high){
mid=(low+high)/2;
MSort(low, mid);
MSort(mid+1,high);
Merge(low, mid, high);
void MergeSort()//归并排序
BeforeSort();
MSort(1,size);
void Distribute(node *a, int w)
for (i=0; i&10; i++) fr[i] = -1;
for (i= i!=-1; i=a[i].next)
int x = a[i].data3 / w % 10;
if (fr[x] == -1)
fr[x] = re[x] =
compCount++;
a[re[x]].next =
shiftCount++;
for (i=0; i&10; i++)
if (fr[i] != -1)
a[re[i]].next = -1;
void Collect(node *a)
last = -1;
for (i=0; i&10; i++)
if (fr[i] != -1)
if (last == -1)
head = fr[i];
last = re[i];
a[last].next = fr[i];
last = re[i];
shiftCount++;
a[last].next = -1;
void RadixSort()//基数排序算法。
BeforeSort();
ofstream out_
a=new node[size];
int i,j=1;
for (i=0; i& i++) {
a[i].data3=data[i+1];
a[i].next = i + 1;
a[size-1].next = -1;
for (i=1; i&= i*=10) {
Distribute(a, i);
Collect(a);
cout&&"\t"&&compCount&&"\t\t"&&shiftCount&&"\n";
while (head != -1)
data[j++]=a[head].data3;
head = a[head].
CopyData(data,data2);
cout&&"\n";
out_stream.open("output.txt",ios::app);
out_stream&&"\t"&&compCount&&"\t\t"&&shiftCount&&"\n\n";
out_stream.close();
void Initialization()//系统初始化
system("cls");//清屏
cout&&"***************************************************************************\n"
&&"*****************
《内部排序算法的比较》
********************************\n"
&&"***************************************************************************\n"
&&"************************
***************************************\n"
&&"*******
1.由系统随机产生待排序表
****************************************\n"
&&"*******
2.手动输入待排序表
**********************************************\n"
&&"*******
3.返回主菜单
****************************************************\n"
&&"*******
4.退出程序
******************************************************\n"
&&"***************************************************************************\n"
&&"请输入要执行的步骤：";
void Interpret(int cmd)//调用各个算法
int i,j,m;
ofstream out_
out_stream.open("output.txt",ios::app);
if(out_stream.fail())
cout&&"Output file opening failed.\n";
switch(cmd)
out_stream&&"由系统随机产生待排序表的各个算法的比较次数和移动次数如下:\n";
out_stream&&"\tcompCount\tshiftCount\n";
out_stream.close();
cout&&"请输入待排序表的长度:";
cout&&"由系统随机产生待排序表的各个算法的比较次数和移动次数如下:\n";
RandomizeList();
for(m=0;m&3;m++)
if(m==2) InverseOrder();
cout&&"\t";
for(i=1;i&=i++) cout&&data[i]&&" ";
cout&&"\n";
cout&&"\tcompCount\tshiftCount\n";
for(j=0;j&SORTNUM;j++)
RecallList();
out_stream.open("output.txt",ios::app);
if(j==0) {cout&&"Bubbl: ";out_stream&&"Bubbl: ";out_stream.close();BubbleSort();}
if(j==1) {cout&&"Tnser: ";out_stream&&"Tnser: ";out_stream.close();InsertSort();}
if(j==2) {cout&&"Selec: ";out_stream&&"Selec: ";out_stream.close();SelectSort();}
if(j==3) {cout&&"Quick: ";out_stream&&"Quick: ";out_stream.close();QuickSort();}
if(j==4) {cout&&"Shell: ";out_stream&&"Shell: ";out_stream.close();ShellSort();}
if(j==5) {cout&&"Heap : ";out_stream&&"Heap : ";out_stream.close();HeapSort();}
if(j==6) {cout&&"BInse: ";out_stream&&"BInse: ";out_stream.close();BInsertSort();}
if(j==7) {cout&&"Merge: ";out_stream&&"Merge: ";out_stream.close();MergeSort();}
if(j==8) {cout&&"Bin
: ";out_stream&&"Bin
: ";out_stream.close();Binsort();}
if(j==9) {cout&&"Radix: ";out_stream&&"Radix: ";out_stream.close();RadixSort();}
cout&&"请输入待排序表的长度：";
cout&&"请输入"&&size&&"个数据:\n";
for(i=1;i&=i++) cin&&data[i];
CopyData(data,data2);
out_stream&&"手动输入待排序表的各个算法的比较次数和移动次数如下:\n";
out_stream&&"\tcompCount\tshiftCount\n";
out_stream.close();
cout&&"手动输入待排序表的各个算法的比较次数和移动次数如下:\n";
cout&&"\tcompCount\tshiftCount\n";
for(j=0;j&SORTNUM;j++)
RecallList();
out_stream.open("output.txt",ios::app);
if(j==0) {cout&&"Bubbl: ";out_stream&&"Bubbl: ";out_stream.close();BubbleSort();}
if(j==1) {cout&&"Tnser: ";out_stream&&"Tnser: ";out_stream.close();InsertSort();}
if(j==2) {cout&&"Selec: ";out_stream&&"Selec: ";out_stream.close();SelectSort();}
if(j==3) {cout&&"Quick: ";out_stream&&"Quick: ";out_stream.close();QuickSort();}
if(j==4) {cout&&"Shell: ";out_stream&&"Shell: ";out_stream.close();ShellSort();}
if(j==5) {cout&&"Heap : ";out_stream&&"Heap : ";out_stream.close();HeapSort();}
if(j==6) {cout&&"BInse: ";out_stream&&"BInse: ";out_stream.close();BInsertSort();}
if(j==7) {cout&&"Merge: ";out_stream&&"Merge: ";out_stream.close();MergeSort();}
if(j==8) {cout&&"Bin
: ";out_stream&&"Bin
: ";out_stream.close();Binsort();}
if(j==9) {cout&&"Radix: ";out_stream&&"Radix: ";out_stream.close();RadixSort();}
Initialization();
void main()
Initialization();
Interpret(cmd);
}while(cmd!=4);
开源中国-程序员在线工具：
相关的代码(2869)
3回/1006阅
这个看上去很规整
开源从代码分享开始
芝麻糖人的其它代码10种排序算法总结
来源：博客园

10种排序算法总结
排序算法有很多，所以在特定情景中使用哪一种算法很重要。为了选择合适的算法，可以按照建议的顺序考虑以下标准： （1）执行时间 （2）存储空间 （3）工作
对于数据量较小的情形，（1）（2）差别不大，主要考虑（3）；而对于数据量大的，（1）为首要。
主要排序法有： 一、冒泡（Bubble）排序——相邻交换 二、选择排序——每次最小/大排在相应的位置 三、插入排序——将下一个插入已排好的序列中 四、壳（Shell）排序——缩小增量 五、归并排序 六、快速排序 七、堆排序 八、拓扑排序 九、锦标赛排序 十、基数排序
一、冒泡（Bubble）排序



void BubbleSortArray() 
{ 
for(int i=1;i&n;i++) 
for(int j=0;i&n-i;j++) 
if(a[j]&a[j+1])//比较交换相邻元素 
temp=a[j];　　　　　　　　　　
a[j]=a[j+1]; 　　　　　　　　　　　a[j+1]= 
} 
} 


效率 O（n?）,适用于排序小列表。
二、选择排序 


void SelectSortArray() 
{ 
int min_ 
for(int i=0;i&n-1;i++) 
min_index=i; 
for(int j=i+1;j&n;j++)//每次扫描选择最小项 
if(arr[j]&arr[min_index]) 　　　　　　　　 min_index=j; 
if(min_index!=i)//找到最小项交换，即将这一项移到列表中的正确位置 
temp=arr[i]; 　　　　　　
arr[i]=arr[min_index];　　　　　　
arr[min_index]= 
　　　　　} 
　　 } 
}


 
效率O（n?），适用于排序小的列表。
三、插入排序 


void InsertSortArray() 
{ 
for(int i=1;i&n;i++)//循环从第二个数组元素开始，因为arr[0]作为最初已排序部分 
int temp=arr[i];//temp标记为未排序第一个元素 
int j=i-1; 
while (j&=0 && arr[j]&temp)/*将temp与已排序元素从小到大比较，寻找temp应插入的位置*/ 
arr[j+1]=arr[j]; 
j--; 
arr[j+1]= 
} 
} 


最佳效率O（n）；最糟效率O（n?）与冒泡、选择相同，适用于排序小列表 若列表基本有序，则插入排序比冒泡、选择更有效率。
四、壳（Shell）排序——缩小增量排序 


void ShellSortArray() 
{ 
for(int incr=3;incr&0;incr--)//增量递减，以增量3，2，1为例 
for(int L=0;L&(n-1)/L++)//重复分成的每个子列表 
for(int i=L+i&n;i+=incr)//对每个子列表应用插入排序 
int temp=arr[i]; 
int j=i- 
while(j&=0&&arr[j]&temp) 
arr[j+incr]=arr[j]; 
arr[j+incr]= 
} 
} 


适用于排序小列表。 效率估计O（nlog2^n）~O（n^1.5），取决于增量值的最初大小。建议使用质数作为增量值，因为如果增量值是2的幂，则在下一个通道中会再次比较相同的元素。 壳（Shell）排序改进了插入排序，减少了比较的次数。是不稳定的排序，因为排序过程中元素可能会前后跳跃。
五、归并排序 


void MergeSort(int low,int high) 
{ 
if(low&=high)
return;//每个子列表中剩下一个元素时停止 
else int mid=(low+high)/2;/*将列表划分成相等的两个子列表,若有奇数个元素，则在左边子列表大于右侧子列表*/ 
MergeSort(low,mid);//子列表进一步划分 
MergeSort(mid+1,high); 
int [] B=new int [high-low+1];//新建一个数组，用于存放归并的元素 
for(int i=low,j=mid+1,k=i&=mid && j&=k++)/*两个子列表进行排序归并，直到两个子列表中的一个结束*/ 
if (arr[i]&=arr[j];) 
B[k]=arr[i]; 
I++; 
{ B[k]=arr[j]; j++; } 
for(j&=j++,k++)//如果第二个子列表中仍然有元素，则追加到新列表 
B[k]=arr[j]; 
for(i&=i++,k++)//如果在第一个子列表中仍然有元素，则追加到新列表中 
B[k]=arr[i]; 
for(int z=0;z&high-low+1;z++)//将排序的数组B的 所有元素复制到原始数组arr中 
arr[z]=B[z]; 
} 


效率O（nlogn），归并的最佳、平均和最糟用例效率之间没有差异。 适用于排序大列表，基于分治法。
六、快速排序 


/*快速排序的算法思想：选定一个枢纽元素，对待排序序列进行分割，分割之后的序列一个部分小于枢纽元素，一个部分大于枢纽元素，再对这两个分割好的子序列进行上述的过程。*/
void swap(int a,int b){intt =a =b =} 
int Partition(int [] arr,int low,int high) 
{ 
int pivot=arr[low];//采用子序列的第一个元素作为枢纽元素 
while (low & high) 
//从后往前栽后半部分中寻找第一个小于枢纽元素的元素 
while (low & high && arr[high] &= pivot) 
//将这个比枢纽元素小的元素交换到前半部分 
swap(arr[low], arr[high]); 
//从前往后在前半部分中寻找第一个大于枢纽元素的元素 
while (low &high &&arr [low ]&=pivot ) 
swap (arr [low ],arr [high ]);//将这个枢纽元素大的元素交换到后半部分 
return//返回枢纽元素所在的位置 
} 
void QuickSort(int [] a,int low,int high) 
{ 
if (low &high ) 
int n=Partition (a ,low ,high ); 
QuickSort (a ,low ,n ); 
QuickSort (a ,n +1,high ); 
} 
} 


平均效率O（nlogn），适用于排序大列表。 此算法的总时间取决于枢纽值的位置；选择第一个元素作为枢纽，可能导致O（n?）的最糟用例效率。若数基本有序，效率反而最差。选项中间值作为枢纽，效率是O（nlogn）。 基于分治法。
七、堆排序 最大堆：后者任一非终端节点的关键字均大于或等于它的左、右孩子的关键字，此时位于堆顶的节点的关键字是整个序列中最大的。 思想： (1)令i=l,并令temp＝ (2)计算i的左孩子j=2i+1; (3)若j&＝n－1，则转(4),否则转(6); (4)比较kj和kj+1,若kj+1&kj,则令j＝j＋1，否则j不变； (5)比较temp和kj，若kj&temp，则令ki等于kj，并令i=j,j=2i+1,并转(3),否则转(6) (6)令ki等于temp，结束。 


void HeapSort(SeqIAst R) 
{ //对R[1..n]进行堆排序，不妨用R[0]做暂存单元
BuildHeap(R);//将R[1-n]建成初始堆
for(i=n;i&1;i--) //对当前无序区R[1..i]进行堆排序，共做n-1趟。
R[0]=R[1];
R[1]=R[i];
R[i]=R[0]; //将堆顶和堆中最后一个记录交换
Heapify(R,1,i-1);
//将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质

} 


堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。
堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为O(1)，
它是不稳定的排序方法。
堆排序与直接插入排序的区别:
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果，可减少比较次数。
八、拓扑排序 例 ：学生选修课排课先后顺序 拓扑排序：把有向图中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。 方法： 在有向图中选一个没有前驱的顶点且输出 从图中删除该顶点和所有以它为尾的弧 重复上述两步，直至全部顶点均已输出（拓扑排序成功），或者当图中不存在无前驱的顶点（图中有回路）为止。 


void TopologicalSort()/*输出拓扑排序函数。若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则返回ERROR*/ 
{ 
int indegree[M]; 
int i,k,j; 
char 
int count=0; 
FindInDegree(G,indegree);//对各顶点求入度indegree[0....num] 
InitStack(thestack);//初始化栈 
for(i=0;i&G.i++) 
Console.WriteLine("结点"+G.vertices[i].data+"的入度为"+indegree[i]); 
for(i=0;i&G.i++) 
if(indegree[i]==0) 
Push(thestack.vertices[i]); 
Console.Write("拓扑排序输出顺序为："); 
while(thestack.Peek()!=null) 
Pop(thestack.Peek()); 
j=locatevex(G,n); 
if (j==-2) 
Console.WriteLine("发生错误，程序结束。"); 
exit(); 
Console.Write(G.vertices[j].data); 
count++; 
for(p=G.vertices[j].p!=NULL;p=p.nextarc) 
k=p. 
if (!(--indegree[k])) 
Push(G.vertices[k]); 
if (count&G.num) 
Cosole.WriteLine("该图有环，出现错误，无法排序。"); 
Console.WriteLine("排序成功。"); 
} 


算法的时间复杂度O（n+e）。
九、锦标赛排序 锦标赛排序的算法思想与体育比赛类似。
首先将n个数据元素两两分组，分别按关键字进行比较，得到n／2个比较的优胜者(关键字小者)，作为第一步比较的结果保留下来，
然后对这n／2个数据元素再两两分组，分别按关键字进行比较，…，如此重复，直到选出一个关键字最小的数据元素为止。 


#include &stdio.h& 
#include &stdlib.h& 
#include &string.h& 
#include &math.h& 
#define SIZE 100000 
#define MAX 1000000 
struct node 
{ 
long//关键字 
char str[10]; 
int//最后胜的对手 
int//被击败的对手 
long//比赛次数 
}data[SIZE]; 
long CompareNum=0; 
long ExchangeNum=0; 
long Read(char name[])//读取文件a.txt中的数据，并存放在数组data[]中；最后返回数据的个数 
{ 
FILE * 
long i=1; 
fp=fopen(name,"rw"); 
fscanf(fp,"%d%s",&data[i].num,data[i].str); 
while(!feof(fp)) 
i++; 
fscanf(fp,"%d%s",&data[i].num,data[i].str);
return (i-1); 
} 
long Create(long num)//创建胜者树，返回冠军（最小数）在数组data[]中的下标 
{ 
int i,j1,j2,max,time=1; 
long//记录当前冠军的下标 
for(i=1;pow(2,i-1)&i++) 
 
max=pow(2,i-1);//求叶子结点数目 
for(i=1;i&=i++)//初始化叶子结点 
data[i].killer=0; 
data[i].lastwin=0; 
data[i].times=0; 
if(i&num) 
data[i].num=MAX; 
for(i=1;i&=i+=2)//第一轮比赛 
++CompareN 
if(data[i].num &= data[i+1].num) 
data[i].lastwin = i+1; 
data[i+1].killer=i; 
++data[i]. 
++data[i+1]. 
min=i; 
data[i+1].lastwin=i; 
data[i].killer=i+1; 
++data[i]. 
++data[i+1]. 
min=i+1; 
j1=j2=0;//记录连续的两个未被淘汰的选手的下标 
while(time &= (log(max)/log(2)))//进行淘汰赛 
for(i=1;i&=i++) 
if(data[i].times==time && data[i].killer==0)//找到一名选手 
j2=i;//默认其为两选手中的后来的 
if(j1==0)//如果第一位置是空的，则刚来的选手先来的 
j1=j2; 
else//否则刚来的选手是后来的，那么选手都已到场比赛开始 
++CompareN 
if(data[j1].num &= data[j2].num)//先来的选手获胜 
data[j1].lastwin = j2;//最后赢的是j2 
data[j2].killer=j1;//j2是被j1淘汰的 
++data[j1]. 
++data[j2].//两选手场次均加1
min=j1;//最小数下标为j1 
j1=j2=0;//将j1，j2置0 
else//同理 
data[j2].lastwin=j1; 
data[j1].killer=j2; 
++data[j1]. 
++data[j2].
min=j2; 
j1=j2=0; 
} 

time++;//轮数加1 
return//返回冠军的下标 
} 
void TournamentSort(long num)//锦标赛排序 
{ 
long tag=Create(num);//返回最小数下标 
FILE *fp1; 
fp1=fopen("sort.txt","w+");//为写入创建并打开文件sort.txt 
while(data[tag].num != MAX)//当最小值不是无穷大时 
printf("%d %s\n",data[tag].num,data[tag].str);//输出数据 
fprintf(fp1,"%d %s\n",data[tag].num,data[tag].str);//写入数据 
data[tag].num=MAX;//将当前冠军用无穷大替换 
tag=Create(num);//返回下一个冠军的下标
} 
} 
int main() 
{ 
char name[10]; 
printf("Input name of the file:"); 
gets(name); 
num=Read(name);//读文件 
TournamentSort(num);//锦标赛排序 
printf("CompareNum=%d\nExchangeNum=%d\n",CompareNum,ExchangeNum); 
return 0; 
} 


十、基数排序 基数排序又被称为桶排序。与前面介绍的几种排序方法相比较，基数排序和它们有明显的不同。
前面所介绍的排序方法都是建立在对数据元素关键字进行比较的基础上，所以可以称为基于比较的排序；
而基数排序首先将待排序数据元素依次“分配”到不同的桶里，然后再把各桶中的数据元素“收集”到一起。 通过使用对多关键字进行排序的这种“分配”和“收集”的方法，基数排序实现了对多关键字进行排序。 ——————————————————————————————————————— 例：
每张扑克牌有两个“关键字”：花色和面值。其大小顺序为：
花色：§＜¨＜(C)＜?
面值：2＜3＜……＜K＜A
扑克牌的大小先根据花色比较，花色大的牌比花色小的牌大；花色一样的牌再根据面值比较大小。所以，将扑克牌按从小到大的次序排列，可得到以下序列：
§2，…，§A，¨2，…，¨A，(C)2，…，(C)A，?2，…，?A
这种排序相当于有两个关键字的排序，一般有两种方法实现。
其一：可以先按花色分成四堆（每一堆牌具有相同的花色），然后在每一堆牌里再按面值从小到大的次序排序，最后把已排好序的四堆牌按花色从小到大次序叠放在一起就得到排序的结果。 其二：可以先按面值排序分成十三堆（每一堆牌具有相同的面值），然后将这十三堆牌按面值从小到大的顺序叠放在一起，再把整副牌按顺序根据花色再分成四堆（每一堆牌已按面值从小到大的顺序有序），最后将这四堆牌按花色从小到大合在一起就得到排序的结果。 ——————————————————————————————————————— 实现方法： 　　最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。 　　最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。 


using S 
using System.Collections.G 
using System.L 
using System.T 
namespace LearnSort 
{ 
class Program 
static void Main(string[] args) 
int[] arr = CreateRandomArray(10);//产生随机数组 
Print(arr);//输出数组 
RadixSort(ref arr);//排序 
Print(arr);//输出排序后的结果 
Console.ReadKey(); 
public static void RadixSort(ref int[] arr) 
int iMaxLength = GetMaxLength(arr); 
RadixSort(ref arr, iMaxLength); 
private static void RadixSort(ref int[] arr, int iMaxLength) 
List&int& list = new List&int&();//存放每次排序后的元素 
List&int&[] listArr = new List&int&[10];//十个桶 
char currnetC//存放当前的字符比如说某个元素123 中的2 
string currentI//存放当前的元素比如说某个元素123 
for (int i = 0; i & listArr.L i++)//给十个桶分配内存初始化。 
listArr[i] = new List&int&(); 
for (int i = 0; i & iMaxL i++)//一共执行iMaxLength次，iMaxLength是元素的最大位数。 
foreach (int number in arr)//分桶 
currentItem = number.ToString();//将当前元素转化成字符串 
try { currnetChar = currentItem[currentItem.Length-i-1]; }//从个位向高位开始分桶 
catch { listArr[0].Add(number); continue; }//如果发生异常，则将该数压入listArr[0]。比如说5 是没有十位数的，执行上面的操作肯定会发生越界异常的，这正是期望的行为，我们认为5的十位数是0，所以将它压入listArr[0]的桶里。 
switch (currnetChar)//通过currnetChar的值，确定它压人哪个桶中。 
case '0': listArr[0].Add(number); break; 
case '1': listArr[1].Add(number); break; 
case '2': listArr[2].Add(number); break; 
case '3': listArr[3].Add(number); break; 
case '4': listArr[4].Add(number); break; 
case '5': listArr[5].Add(number); break; 
case '6': listArr[6].Add(number); break; 
case '7': listArr[7].Add(number); break; 
case '8': listArr[8].Add(number); break; 
case '9': listArr[9].Add(number); break; 
default: throw new Exception("unknow error"); 
for (int j = 0; j & listArr.L j++)//将十个桶里的数据重新排列，压入list 
foreach (int number in listArr[j].ToArray&int&()) 
list.Add(number); 
listArr[j].Clear();//清空每个桶 
arr = list.ToArray&int&();//arr指向重新排列的元素 
//Console.Write("{0} times:",i); 
Print(arr);//输出一次排列的结果 
list.Clear();//清空list 
//得到最大元素的位数 
private static int GetMaxLength(int[] arr) 
int iMaxNumber = Int32.MinV 
foreach (int i in arr)//遍历得到最大值 
if (i & iMaxNumber) 
iMaxNumber = 
return iMaxNumber.ToString().L//这样获得最大元素的位数是不是有点投机取巧了... 
//输出数组元素 
public static void Print(int[] arr) 
foreach (int i in arr) 
System.Console.Write(i.ToString()+'\t'); 
System.Console.WriteLine(); 
//产生随机数组。随机数的范围是0到1000。参数iLength指产生多少个随机数 
public static int[] CreateRandomArray(int iLength) 
int[] arr = new int[iLength]; 
Random random = new Random(); 
for (int i = 0; i & iL i++) 
arr[i] = random.Next(0,1001); 
return 
} 
}


基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。
10种排序算法总结
排序算法有很多，所以在特定情景中使用哪一种算法很重要。为了选择合适的算法，可以按照建议的顺序考虑以下标准： （1）执行时间 （2）存储空间 （3）工作
对于数据量较小的情形，（1）（2）差别不大，主要考虑（3）；而对于数据量大的，（1）为首要。
主要排序法有： 一、冒泡（Bubble）排序——相邻交换 二、选择排序——每次最小/大排在相应的位置 三、插入排序——将下一个插入已排好的序列中 四、壳（Shell）排序——缩小增量 五、归并排序 六、快速排序 七、堆排序 八、拓扑排序 九、锦标赛排序 十、基数排序
一、冒泡（Bubble）排序



void BubbleSortArray() 
{ 
for(int i=1;i&n;i++) 
for(int j=0;i&n-i;j++) 
if(a[j]&a[j+1])//比较交换相邻元素 
temp=a[j];　　　　　　　　　　
a[j]=a[j+1]; 　　　　　　　　　　　a[j+1]= 
} 
} 


效率 O（n?）,适用于排序小列表。
二、选择排序 


void SelectSortArray() 
{ 
int min_ 
for(int i=0;i&n-1;i++) 
min_index=i; 
for(int j=i+1;j&n;j++)//每次扫描选择最小项 
if(arr[j]&arr[min_index]) 　　　　　　　　 min_index=j; 
if(min_index!=i)//找到最小项交换，即将这一项移到列表中的正确位置 
temp=arr[i]; 　　　　　　
arr[i]=arr[min_index];　　　　　　
arr[min_index]= 
　　　　　} 
　　 } 
}


 
效率O（n?），适用于排序小的列表。
三、插入排序 


void InsertSortArray() 
{ 
for(int i=1;i&n;i++)//循环从第二个数组元素开始，因为arr[0]作为最初已排序部分 
int temp=arr[i];//temp标记为未排序第一个元素 
int j=i-1; 
while (j&=0 && arr[j]&temp)/*将temp与已排序元素从小到大比较，寻找temp应插入的位置*/ 
arr[j+1]=arr[j]; 
j--; 
arr[j+1]= 
} 
} 


最佳效率O（n）；最糟效率O（n?）与冒泡、选择相同，适用于排序小列表 若列表基本有序，则插入排序比冒泡、选择更有效率。
四、壳（Shell）排序——缩小增量排序 


void ShellSortArray() 
{ 
for(int incr=3;incr&0;incr--)//增量递减，以增量3，2，1为例 
for(int L=0;L&(n-1)/L++)//重复分成的每个子列表 
for(int i=L+i&n;i+=incr)//对每个子列表应用插入排序 
int temp=arr[i]; 
int j=i- 
while(j&=0&&arr[j]&temp) 
arr[j+incr]=arr[j]; 
arr[j+incr]= 
} 
} 


适用于排序小列表。 效率估计O（nlog2^n）~O（n^1.5），取决于增量值的最初大小。建议使用质数作为增量值，因为如果增量值是2的幂，则在下一个通道中会再次比较相同的元素。 壳（Shell）排序改进了插入排序，减少了比较的次数。是不稳定的排序，因为排序过程中元素可能会前后跳跃。
五、归并排序 


void MergeSort(int low,int high) 
{ 
if(low&=high)
return;//每个子列表中剩下一个元素时停止 
else int mid=(low+high)/2;/*将列表划分成相等的两个子列表,若有奇数个元素，则在左边子列表大于右侧子列表*/ 
MergeSort(low,mid);//子列表进一步划分 
MergeSort(mid+1,high); 
int [] B=new int [high-low+1];//新建一个数组，用于存放归并的元素 
for(int i=low,j=mid+1,k=i&=mid && j&=k++)/*两个子列表进行排序归并，直到两个子列表中的一个结束*/ 
if (arr[i]&=arr[j];) 
B[k]=arr[i]; 
I++; 
{ B[k]=arr[j]; j++; } 
for(j&=j++,k++)//如果第二个子列表中仍然有元素，则追加到新列表 
B[k]=arr[j]; 
for(i&=i++,k++)//如果在第一个子列表中仍然有元素，则追加到新列表中 
B[k]=arr[i]; 
for(int z=0;z&high-low+1;z++)//将排序的数组B的 所有元素复制到原始数组arr中 
arr[z]=B[z]; 
} 


效率O（nlogn），归并的最佳、平均和最糟用例效率之间没有差异。 适用于排序大列表，基于分治法。
六、快速排序 


/*快速排序的算法思想：选定一个枢纽元素，对待排序序列进行分割，分割之后的序列一个部分小于枢纽元素，一个部分大于枢纽元素，再对这两个分割好的子序列进行上述的过程。*/
void swap(int a,int b){intt =a =b =} 
int Partition(int [] arr,int low,int high) 
{ 
int pivot=arr[low];//采用子序列的第一个元素作为枢纽元素 
while (low & high) 
//从后往前栽后半部分中寻找第一个小于枢纽元素的元素 
while (low & high && arr[high] &= pivot) 
//将这个比枢纽元素小的元素交换到前半部分 
swap(arr[low], arr[high]); 
//从前往后在前半部分中寻找第一个大于枢纽元素的元素 
while (low &high &&arr [low ]&=pivot ) 
swap (arr [low ],arr [high ]);//将这个枢纽元素大的元素交换到后半部分 
return//返回枢纽元素所在的位置 
} 
void QuickSort(int [] a,int low,int high) 
{ 
if (low &high ) 
int n=Partition (a ,low ,high ); 
QuickSort (a ,low ,n ); 
QuickSort (a ,n +1,high ); 
} 
} 


平均效率O（nlogn），适用于排序大列表。 此算法的总时间取决于枢纽值的位置；选择第一个元素作为枢纽，可能导致O（n?）的最糟用例效率。若数基本有序，效率反而最差。选项中间值作为枢纽，效率是O（nlogn）。 基于分治法。
七、堆排序 最大堆：后者任一非终端节点的关键字均大于或等于它的左、右孩子的关键字，此时位于堆顶的节点的关键字是整个序列中最大的。 思想： (1)令i=l,并令temp＝ (2)计算i的左孩子j=2i+1; (3)若j&＝n－1，则转(4),否则转(6); (4)比较kj和kj+1,若kj+1&kj,则令j＝j＋1，否则j不变； (5)比较temp和kj，若kj&temp，则令ki等于kj，并令i=j,j=2i+1,并转(3),否则转(6) (6)令ki等于temp，结束。 


void HeapSort(SeqIAst R) 
{ //对R[1..n]进行堆排序，不妨用R[0]做暂存单元
BuildHeap(R);//将R[1-n]建成初始堆
for(i=n;i&1;i--) //对当前无序区R[1..i]进行堆排序，共做n-1趟。
R[0]=R[1];
R[1]=R[i];
R[i]=R[0]; //将堆顶和堆中最后一个记录交换
Heapify(R,1,i-1);
//将R[1..i-1]重新调整为堆，仅有R[1]可能违反堆性质

} 


堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成，它们均是通过调用Heapify实现的。
堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。
由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。
堆排序是就地排序，辅助空间为O(1)，
它是不稳定的排序方法。
堆排序与直接插入排序的区别:
直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
堆排序可通过树形结构保存部分比较结果，可减少比较次数。
八、拓扑排序 例 ：学生选修课排课先后顺序 拓扑排序：把有向图中各顶点按照它们相互之间的优先关系排列成一个线性序列的过程。 方法： 在有向图中选一个没有前驱的顶点且输出 从图中删除该顶点和所有以它为尾的弧 重复上述两步，直至全部顶点均已输出（拓扑排序成功），或者当图中不存在无前驱的顶点（图中有回路）为止。 


void TopologicalSort()/*输出拓扑排序函数。若G无回路，则输出G的顶点的一个拓扑序列并返回OK，否则返回ERROR*/ 
{ 
int indegree[M]; 
int i,k,j; 
char 
int count=0; 
FindInDegree(G,indegree);//对各顶点求入度indegree[0....num] 
InitStack(thestack);//初始化栈 
for(i=0;i&G.i++) 
Console.WriteLine("结点"+G.vertices[i].data+"的入度为"+indegree[i]); 
for(i=0;i&G.i++) 
if(indegree[i]==0) 
Push(thestack.vertices[i]); 
Console.Write("拓扑排序输出顺序为："); 
while(thestack.Peek()!=null) 
Pop(thestack.Peek()); 
j=locatevex(G,n); 
if (j==-2) 
Console.WriteLine("发生错误，程序结束。"); 
exit(); 
Console.Write(G.vertices[j].data); 
count++; 
for(p=G.vertices[j].p!=NULL;p=p.nextarc) 
k=p. 
if (!(--indegree[k])) 
Push(G.vertices[k]); 
if (count&G.num) 
Cosole.WriteLine("该图有环，出现错误，无法排序。"); 
Console.WriteLine("排序成功。"); 
} 


算法的时间复杂度O（n+e）。
九、锦标赛排序 锦标赛排序的算法思想与体育比赛类似。
首先将n个数据元素两两分组，分别按关键字进行比较，得到n／2个比较的优胜者(关键字小者)，作为第一步比较的结果保留下来，
然后对这n／2个数据元素再两两分组，分别按关键字进行比较，…，如此重复，直到选出一个关键字最小的数据元素为止。 


#include &stdio.h& 
#include &stdlib.h& 
#include &string.h& 
#include &math.h& 
#define SIZE 100000 
#define MAX 1000000 
struct node 
{ 
long//关键字 
char str[10]; 
int//最后胜的对手 
int//被击败的对手 
long//比赛次数 
}data[SIZE]; 
long CompareNum=0; 
long ExchangeNum=0; 
long Read(char name[])//读取文件a.txt中的数据，并存放在数组data[]中；最后返回数据的个数 
{ 
FILE * 
long i=1; 
fp=fopen(name,"rw"); 
fscanf(fp,"%d%s",&data[i].num,data[i].str); 
while(!feof(fp)) 
i++; 
fscanf(fp,"%d%s",&data[i].num,data[i].str);
return (i-1); 
} 
long Create(long num)//创建胜者树，返回冠军（最小数）在数组data[]中的下标 
{ 
int i,j1,j2,max,time=1; 
long//记录当前冠军的下标 
for(i=1;pow(2,i-1)&i++) 
 
max=pow(2,i-1);//求叶子结点数目 
for(i=1;i&=i++)//初始化叶子结点 
data[i].killer=0; 
data[i].lastwin=0; 
data[i].times=0; 
if(i&num) 
data[i].num=MAX; 
for(i=1;i&=i+=2)//第一轮比赛 
++CompareN 
if(data[i].num &= data[i+1].num) 
data[i].lastwin = i+1; 
data[i+1].killer=i; 
++data[i]. 
++data[i+1]. 
min=i; 
data[i+1].lastwin=i; 
data[i].killer=i+1; 
++data[i]. 
++data[i+1]. 
min=i+1; 
j1=j2=0;//记录连续的两个未被淘汰的选手的下标 
while(time &= (log(max)/log(2)))//进行淘汰赛 
for(i=1;i&=i++) 
if(data[i].times==time && data[i].killer==0)//找到一名选手 
j2=i;//默认其为两选手中的后来的 
if(j1==0)//如果第一位置是空的，则刚来的选手先来的 
j1=j2; 
else//否则刚来的选手是后来的，那么选手都已到场比赛开始 
++CompareN 
if(data[j1].num &= data[j2].num)//先来的选手获胜 
data[j1].lastwin = j2;//最后赢的是j2 
data[j2].killer=j1;//j2是被j1淘汰的 
++data[j1]. 
++data[j2].//两选手场次均加1
min=j1;//最小数下标为j1 
j1=j2=0;//将j1，j2置0 
else//同理 
data[j2].lastwin=j1; 
data[j1].killer=j2; 
++data[j1]. 
++data[j2].
min=j2; 
j1=j2=0; 
} 

time++;//轮数加1 
return//返回冠军的下标 
} 
void TournamentSort(long num)//锦标赛排序 
{ 
long tag=Create(num);//返回最小数下标 
FILE *fp1; 
fp1=fopen("sort.txt","w+");//为写入创建并打开文件sort.txt 
while(data[tag].num != MAX)//当最小值不是无穷大时 
printf("%d %s\n",data[tag].num,data[tag].str);//输出数据 
fprintf(fp1,"%d %s\n",data[tag].num,data[tag].str);//写入数据 
data[tag].num=MAX;//将当前冠军用无穷大替换 
tag=Create(num);//返回下一个冠军的下标
} 
} 
int main() 
{ 
char name[10]; 
printf("Input name of the file:"); 
gets(name); 
num=Read(name);//读文件 
TournamentSort(num);//锦标赛排序 
printf("CompareNum=%d\nExchangeNum=%d\n",CompareNum,ExchangeNum); 
return 0; 
} 


十、基数排序 基数排序又被称为桶排序。与前面介绍的几种排序方法相比较，基数排序和它们有明显的不同。
前面所介绍的排序方法都是建立在对数据元素关键字进行比较的基础上，所以可以称为基于比较的排序；
而基数排序首先将待排序数据元素依次“分配”到不同的桶里，然后再把各桶中的数据元素“收集”到一起。 通过使用对多关键字进行排序的这种“分配”和“收集”的方法，基数排序实现了对多关键字进行排序。 ——————————————————————————————————————— 例：
每张扑克牌有两个“关键字”：花色和面值。其大小顺序为：
花色：§＜¨＜(C)＜?
面值：2＜3＜……＜K＜A
扑克牌的大小先根据花色比较，花色大的牌比花色小的牌大；花色一样的牌再根据面值比较大小。所以，将扑克牌按从小到大的次序排列，可得到以下序列：
§2，…，§A，¨2，…，¨A，(C)2，…，(C)A，?2，…，?A
这种排序相当于有两个关键字的排序，一般有两种方法实现。
其一：可以先按花色分成四堆（每一堆牌具有相同的花色），然后在每一堆牌里再按面值从小到大的次序排序，最后把已排好序的四堆牌按花色从小到大次序叠放在一起就得到排序的结果。 其二：可以先按面值排序分成十三堆（每一堆牌具有相同的面值），然后将这十三堆牌按面值从小到大的顺序叠放在一起，再把整副牌按顺序根据花色再分成四堆（每一堆牌已按面值从小到大的顺序有序），最后将这四堆牌按花色从小到大合在一起就得到排序的结果。 ——————————————————————————————————————— 实现方法： 　　最高位优先(Most Significant Digit first)法，简称MSD法：先按k1排序分组，同一组中记录，关键码k1相等，再对各组按k2排序分成子组，之后，对后面的关键码继续这样的排序分组，直到按最次位关键码kd对各子组排序后。再将各组连接起来，便得到一个有序序列。 　　最低位优先(Least Significant Digit first)法，简称LSD法：先从kd开始排序，再对kd-1进行排序，依次重复，直到对k1排序后便得到一个有序序列。 


using S 
using System.Collections.G 
using System.L 
using System.T 
namespace LearnSort 
{ 
class Program 
static void Main(string[] args) 
int[] arr = CreateRandomArray(10);//产生随机数组 
Print(arr);//输出数组 
RadixSort(ref arr);//排序 
Print(arr);//输出排序后的结果 
Console.ReadKey(); 
public static void RadixSort(ref int[] arr) 
int iMaxLength = GetMaxLength(arr); 
RadixSort(ref arr, iMaxLength); 
private static void RadixSort(ref int[] arr, int iMaxLength) 
List&int& list = new List&int&();//存放每次排序后的元素 
List&int&[] listArr = new List&int&[10];//十个桶 
char currnetC//存放当前的字符比如说某个元素123 中的2 
string currentI//存放当前的元素比如说某个元素123 
for (int i = 0; i & listArr.L i++)//给十个桶分配内存初始化。 
listArr[i] = new List&int&(); 
for (int i = 0; i & iMaxL i++)//一共执行iMaxLength次，iMaxLength是元素的最大位数。 
foreach (int number in arr)//分桶 
currentItem = number.ToString();//将当前元素转化成字符串 
try { currnetChar = currentItem[currentItem.Length-i-1]; }//从个位向高位开始分桶 
catch { listArr[0].Add(number); continue; }//如果发生异常，则将该数压入listArr[0]。比如说5 是没有十位数的，执行上面的操作肯定会发生越界异常的，这正是期望的行为，我们认为5的十位数是0，所以将它压入listArr[0]的桶里。 
switch (currnetChar)//通过currnetChar的值，确定它压人哪个桶中。 
case '0': listArr[0].Add(number); break; 
case '1': listArr[1].Add(number); break; 
case '2': listArr[2].Add(number); break; 
case '3': listArr[3].Add(number); break; 
case '4': listArr[4].Add(number); break; 
case '5': listArr[5].Add(number); break; 
case '6': listArr[6].Add(number); break; 
case '7': listArr[7].Add(number); break; 
case '8': listArr[8].Add(number); break; 
case '9': listArr[9].Add(number); break; 
default: throw new Exception("unknow error"); 
for (int j = 0; j & listArr.L j++)//将十个桶里的数据重新排列，压入list 
foreach (int number in listArr[j].ToArray&int&()) 
list.Add(number); 
listArr[j].Clear();//清空每个桶 
arr = list.ToArray&int&();//arr指向重新排列的元素 
//Console.Write("{0} times:",i); 
Print(arr);//输出一次排列的结果 
list.Clear();//清空list 
//得到最大元素的位数 
private static int GetMaxLength(int[] arr) 
int iMaxNumber = Int32.MinV 
foreach (int i in arr)//遍历得到最大值 
if (i & iMaxNumber) 
iMaxNumber = 
return iMaxNumber.ToString().L//这样获得最大元素的位数是不是有点投机取巧了... 
//输出数组元素 
public static void Print(int[] arr) 
foreach (int i in arr) 
System.Console.Write(i.ToString()+'\t'); 
System.Console.WriteLine(); 
//产生随机数组。随机数的范围是0到1000。参数iLength指产生多少个随机数 
public static int[] CreateRandomArray(int iLength) 
int[] arr = new int[iLength]; 
Random random = new Random(); 
for (int i = 0; i & iL i++) 
arr[i] = random.Next(0,1001); 
return 
} 
}


基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。
免责声明：本站部分内容、图片、文字、视频等来自于互联网，仅供大家学习与交流。相关内容如涉嫌侵犯您的知识产权或其他合法权益，请向本站发送有效通知，我们会及时处理。反馈邮箱&&&&。
学生服务号
在线咨询，奖学金返现，名师点评，等你来互动}