第一节 排序概论

                 1.1 排序定义

     排序是计算机内经常进行的一种操作，其目的是将一组“无序”的记录序列调整为“有序”的记录序列。分内部排序和外部排序。若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。反之，若参加排序的记录数量很大，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。内部排序的过程是一个逐步扩大记录的有序序列长度的过程。

                  1.2 排序分类

     假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，ri=rj，且ri在rj之前，而在排序后的序列中，ri仍在rj之前，则称这种排序算法是稳定的；否则称为不稳定的。

                 1.3 排序算法

【1.3.1 冒泡排序】

      已知一组无序数据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次交换。实际，当一次排序过后没有发生交换，那么就算作排序成功，即可退出程序。

/*冒泡排序(改进后)*/ void BubbleSort(int a[],int n) {	while(n>0) {		int k;		k=n-1; n=0;		for(int i=1;i<=k;i++)			if(a[i]>a[i+1]) {			 	swap(a[i+1],a[i]);				n=i;			}	} }

【1.3.2 选择排序】　

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法(很多教科书都说选择排序是不稳定的，但是，完全可以将其实现成稳定的排序方法)。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趟直接选择排序得到有序结果。

/*选择排序*/void SelectSort(int a[],int n) {	for(int i=1;i

【1.3.3 插入排序】　　

    插入排序：已知一组升序排列数据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）

/*插入排序*/void InsertSort(int a[],int n) {	for(int i=2;i<=n;i++) {		int tmp,j;		tmp=a[i];j=i-1;		while(a[j]>tmp) {a[j+1]=a[j];j--;} 		a[j+1]=tmp; 	} }

【1.3.4 希尔排序】　　

　    由希尔在1959年提出。已知一组无序数据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。

/*希尔排序*/void ShellSort(int a[],int n) {	for(int i=n/2;i>0;i/=2)		for(int j=i+1;j<=n;j++) {			int key=a[j],k;			for(k=j-i;k>=0&&a[k]>key;k-=i) a[k+i]=a[k]; 			a[k+i]=key;		}}

【1.3.5 快速排序】　

      快速排序是目前已知的常用排序算法中最快的排序方法。已知一组无序数据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]两组数据进行快速排序。

/*快速排序*/ void QuickSort(int a[],int l,int r) {	int i,j,mid;	i=l;j=r;	mid=a[(l+r)/2];	while(i<=j) {		while(a[i]
     
      mid) j--;		if(i<=j) {			swap(a[i],a[j]);			i++;j--;		}	}	if(l>j) QuickSort(a,l,j);	if(i
     

　　

快速排序在C++中也有现成的，要用到STL模板。

#include 
     
      /*这是升序*/int cmpup(const void *x,const void *y) {    return *(int*) x - *(int*) y;}/**********************************//*这是降序*/int cmpdown(const void *x,const void *y) {    return *(int*) y - *(int*) x;}/**********************************/void Qsort(int a[],int n) {    qsort(a,n,sizeof(int),cmpup);//如果是降序，那么就是：    qsort(a,n,sizeof(int),cmpdown);}
     

【1.3.6 桶排序】　

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

#include 
     
      using namespace std;int b[101],k,n;int main() {	cin>>n;	for(int i=0;i<=100;i++) b[i]=0;	for(int i=1;i<=n;i++) {		cin>>k;		b[k]=b[k]+1;	}	for(int i=0;i<=100;i++)		while(b[i]>0) {			cout<
      <<' ';			b[i]--;		}	return 0; }
     

【1.3.7 归并排序】　　

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

#include 
      
       using namespace std;int n,m,s[101],r[101],a[101];int MergeSort() {	int i=0,j=0,k=0;	while ((i
       
        
         >n; for(int x=0;x
         
          >s[x];	cin>>m; for(int x=0;x
          
           >r[x];	MergeSort();	for(int x=0;x
          
         
        
       
      

【1.3.8 堆排序】　　

　　堆排序的要素就是让所有的左子树都比根及右子树大，但不太稳定。

#include 
      
       using namespace std;int a[1000001],n;void EditHeap(int i,int s) {	int j;	if (2*i<=s) {		a[0]=a[i];j=i;		if (a[2*i]>a[0]) {a[0]=a[2*i];j=2*i;}		if ((2*i+1<=s)&&(a[2*i+1]>a[0])) {a[0]=a[2*i+1];j=2*i+1;}		if (j!=i) {a[j]=a[i];a[i]=a[0];EditHeap(j,s);}	}}void BuildHeap() {	int i,j;	for (i=n/2;i>=1;i--) {		a[0]=a[i];j=i;		if (a[2*i]>a[0]) {a[0]=a[2*i];j=2*i;}		if ((2*i+1<=n)&&(a[2*i+1]>a[0])) {a[0]=a[2*i+1];j=2*i+1;}		if (j!=i) {a[j]=a[i];a[i]=a[0];EditHeap(j,n);}	}}void HeapSort() {	BuildHeap();	for(int i=n;i>=2;i--) {		a[0]=a[i]; 		a[i]=a[1]; 		a[1]=a[0];		EditHeap(1,i-1);	}}int main() {	cin>>n;	for(int i=1;i<=n;i++) cin>>a[i];	HeapSort();	for(int i=1;i<=n;i++) cout<
       
        <<' ';	cout<
       
      

【1.3.9 sort排序】　　

sort排序是指使用C++STL算法库中的sort函数进行任意类型数据排序。

#include 
      
       int sortsort(int a[],int n) {    sort(a,a+n);}
      

【1.3.10 基数排序】

    基数排序(radix sort）则是属于“分配式排序”（distribution sort），基数排序法又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O (nlog(r)m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的比较性排序法。也称“桶排序”，与1.3.6基本相同。

这里给出网上下载的基数排序的截图：