Chinaunix首页 | 论坛 | 博客

编程之路qqrilxk.blog.chinaunix.net

首页　| 　博文目录　| 　关于我

qqrilxk

  • 博客访问： 494486
  • 博文数量： 133
  • 博客积分： 1235
  • 博客等级： 少尉
  • 技术积分： 1201
  • 用 户 组： 普通用户
  • 注册时间： 2010-09-08 19:59
文章分类

全部博文（133）

文章存档

2023年（12）

2022年（3）

2018年（2）

2017年（4）

2016年（4）

2015年（42）

2014年（1）

2013年（12）

2012年（16）

2011年（36）

2010年（1）

我的朋友
最近访客
推荐博文
相关博文
各种排序算法的讲解与代码实现

分类： 其他平台

2016-07-12 11:24:07

排序的分类：

1 内部排序

 内部排序：在整个排序过程中不需不访问外存便能完成，称这样的排序问题为内部排序；

1.1 插入排序

      插入排序： 将无序序列中的一个或几个记录“插入”到有序的序列中，从而增加记录的有序序列的长度。

     主要思想是将第一个元素看做是有序的，从第二个元素起将待排序的元素插入到有序序列中，使序列逐渐扩大，直到所有的元素都插入到有序序类中。

直接插入排序

    基本思想是将记录R[i]插入到有序序列R[1..i-1],使记录的有序序列从R[1..i-1]变为R[1..i]。

    直接插入排序最好情况下的时间复杂度为O(n),最坏情况的时间复杂度和平均时间复杂度为O(n^2)。

[cpp] view plain copy
  1. #include "stdafx.h"  
  2. #include "stdafx.h"  
  3. #include   
  4. using namespace std;  
  5.   
  6. void StrInsSort (int number  ,int r[])  
  7. {  
  8.     int temp;  
  9.     for(int i=1;i<=number;i++)  
  10.     {  
  11.         temp=r[i];int j=i-1;  
  12.         while(temp
  13.         {  
  14.             r[j+1]=r[j];  
  15.             j--;  
  16.         }  
  17.         r[j+1]=temp;  
  18.     }  
  19. }  
  20.   
  21. int _tmain(int argc, int argv[])  
  22. {  
  23.     std::cout<<"输入数组大小"<
  24.     std::cin>> argc;  
  25.     std::cout<<"输入数组内数据"<
  26.     for(int j=0;j
  27.     {    
  28.         std::cin>>argv[j];  
  29.     }  
  30.     StrInsSort (argc ,argv);  
  31.     for(int j=0;j
  32.     {    
  33.         std::cout << argv[j] << std::endl;   
  34.     }  
  35.     system("pause");  
  36.     return 0;  
  37. }  

次待排序数组是从0开始的，先假定第0个元素是有序的，从第一个元素起与前边的有序序列进行比较，T先和下标为i-1的数组比较，（生成的整个序列是从小到达排列的）如果

r[i]>r[i-1],则直接放在r[i]的位置，否则如果T

 

折半插入排序

    折半插入与直接插入比较，当第i 个记录要插入到前i-1个记录序列时，可以利用折半查找方式确定插入位置，以减少比较次数。

    折半查找明显减少了关键字的“比较”次数，单记录的移动次数不变，故时间复杂度仍为O(n^2)。

 

[html] view plain copy
  1. void BinSort (int count, int R[])  
  2. {  
  3.     for (int i=1;i<=count;i++)  
  4.     {  
  5.         int left=0;  
  6.         int right=i-1;  
  7.         int temp;  
  8.         while (right>=left)  
  9.         {  
  10.             temp=R[i] ;  
  11.             int mid =(left+right)/2;  
  12.             if (temp>R[mid])  
  13.             {  
  14.                 left=mid+1;  
  15.             }   
  16.             else  
  17.             {  
  18.                 right=mid-1;  
  19.             }  
  20.         }  
  21.         for (int j=i-1;j>=right+1;j--)  
  22.         {  
  23.             R[j+1]=R[j];  
  24.         }  
  25.         R[right+1]=temp;  
  26.     }  
  27. };  


函数写过程中，首先确定有多少个元素要参加排序，由于次数组是从下表0开始的，所以和直接插入排序一样，先假设第0个元素是有序的，则从下标为1的元素开始执行循环，即从1到count个元素都要执行对比循环过程；其循环内部基本思路是，把取到的第i个元素插入到前0到i-1个元素中，因为前i个元素是有序的，所以二分查找是拿第i元素和和前面有序数列中的第mid =(left+right)/2个元素比较，即有序数列中中间的那个元素，因为排序后要生成一个从小到大排序的数列，即升序数列，所以如果temp>R[mid]如下图所示，

0 2 4 6 7 9 11

 则要是插入 temp后整个数列依然有序，则temp必须在6的后面，所以要最左侧的数为left=mid+1;才能保证在后半部分寻找数据；

然后就要判断循环什么时候终止，因为在整个循环过程中不断缩小循环的范围，即left和right的距离越来越近，当left==right时，这时mid==left==righ, 这时，

如果      

  if (temp>R[mid])
   {
    left=mid+1;
   }     

如上图所示，mid在6的位置，此时的temp是>6而<7 的，应该把>=left的或>=mid+1的或>=right+1的元素向后移一位；

而如果   

else
   {
    right=mid-1;
   }

如上图所示，mid应该<6且>4，即放在4和6之间，这样更应该把>=left的后>=mid的或>=right+1的元素向后移一位；

  for (int j=i-1;j>=right+1;j--)
  {
   R[j+1]=R[j];
  }           即对应这段程序；

 经过上边分析，同样也可以写成下面程序，即把>=right+1,改成>=left;

 for (int j=i-1;j>=left;j--)
  {
   R[j+1]=R[j];
  }
  R[left]=temp;

 

二路插入排序

    基本思想是另设一数组d，将R[1]复制给d[1]，并将d[1]看做排好序的“中间”记录，从第二个起依次将关键字小于d[1]的记录插入到d[1]之前的有序序列中，将关键字大于d[1]的记录插入到d[1]之后的有序序列中。这里借助两个变量first和final来指示排序过程中有序序列第一个记录和最后一个记录在d中的位置。

       

[html] view plain copy
  1. int BiInsertSort()  
  2. {  
  3.     //二路插入排序算法  
  4.     int iRawBuff[6] ={0,9,6,7,3,2};  
  5.     int final = 0;  
  6.     int first = 0;  
  7.     const int iLenght = 5;  
  8.   
  9.     int iTempBuff[iLenght] = {0};  
  10.   
  11.     iTempBuff[0] = iRawBuff[0];  
  12.     for (int i = 1; i <= iLenght;i++)  
  13.     {  
  14.         if(iRawBuff[i] > iTempBuff[final])  
  15.         {  
  16.             //大于当前最大值，后插  
  17.             final++;  
  18.             iTempBuff[final] = iRawBuff[i];  
  19.   
  20.         }  
  21.         if(iRawBuff[i]< iTempBuff[first])  
  22.         {  
  23.             //小于当前最小值,前插  
  24.             first = (first-1+iLenght)%iLenght;  
  25.             iTempBuff[first] = iRawBuff[i];  
  26.   
  27.         }  
  28.         if(iRawBuff[i] < iTempBuff[final]&&iRawBuff[i] > iTempBuff[first])  
  29.         {  
  30.             //大于当前最小值，小于当前最大值，中间插  
  31.             int j = final++;  
  32.             while (iRawBuff[i] < iTempBuff[j])  
  33.             {  
  34.                 iTempBuff[(j+1)%iLenght] = iTempBuff[j];  
  35.                 j = (j-1+iLenght)%iLenght;  
  36.             }  
  37.             iTempBuff[j+1] = iRawBuff[i];  
  38.   
  39.         }  
  40.         printf("第%d趟：\n",i-1);  
  41.         for(int k = 0; k < iLenght; k++)  
  42.         {  
  43.             std::cout<<iTempBuff[k]<<"\t";  
  44.         }  
  45.         std::cout<<std::endl;  
  46.     }  
  47.     //导入输入到原始数组中  
  48.     for (int k = 0; k < iLenght; k++)  
  49.     {  
  50.         iRawBuff[k+1] = iTempBuff[(first++)%iLenght];  
  51.     }  
  52.     return 0;  
  53. }  


    运行结果：

           

 

 由于first在增加增加的过程中，没有最大值的限制，为了防止生成的数组发生越界，所以对这些数取iLenght的余数，即用%iLenght。

 

表插入排序

    为了减少在排序过程中“移动”记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序之后，一次性地调整各个记录之间的位置，即将每个记录都调整到他们应该在的位置上，这样的排序方法称为表插入排序。

基本思想：

使头结点的next域始终指示最小的那个元素，然后依次向下：每一个元素的next域都指示比它稍大的那个元素。最大的元素的next域指示头结点。

下面分三步给出具体的代码：

1、用数组初始化表结构。

2、修改next域形成有序的循环链表。

3、根据next域信息调整表结构中的数组，是数据从小到大排列。

 

[cpp] view plain copy
  1. #include "stdafx.h"  
  2. #define INT_MAX 100  
  3. #define number 100  
  4. #include  
  5. #include  
  6. #include  
  7. #include  
  8. #include  
  9.   
  10. //排序后按从小到大输出  
  11.   
  12. using namespace std;  
  13. typedef struct    
  14. {  
  15.     int key;  
  16.     int other;  //记录其他数据域  
  17.     int next;  
  18. }STListType;  
  19.   
  20. STListType SL[number+1];  
  21.   
  22.   
  23. void ListInsSort(STListType SL[],int n)  
  24. {  
  25.     //对记录序列SL[1..n]进行表插入排序  
  26.     SL[0].key = 10000;  
  27.     SL[0].next=1;  
  28.     SL[1].next=0;               //初始化，假定第一个记录有序  
  29.     int k;  
  30.     for (int i=2; i//查找插入位置  
  31.     {  
  32.         int j=0;  
  33.         for (k=SL[0].next;SL[k].key//保证[k].key>=[i].key  
  34.         {  
  35.             j=k, k=SL[k].next;                   //保证是SL[k]里的总是最大的                 
  36.         }  
  37.         SL[j].next=i;     //结点i插入在结点j和结点k之间  SL[j]<=SL[i]<=SL[k]   
  38.         SL[i].next =k;   
  39.   
  40.         cout<<"ListInsSort-key:\n";  
  41.         for(int count=0;count
  42.             cout<
  43.         cout<
  44.         cout<<"ListInsSort-next:\n";  
  45.         for(int count=0;count
  46.             cout<
  47.         cout<
  48.     }  
  49. }  
  50.   
  51. void Arrange(STListType SL[],int n)  
  52. {  
  53.     //根据静态表SL中各节点的指针值调整记录位置，使得SL中的记录关键字非递减有序顺序排列  
  54.     //p指示第i个记录的当前位置；i指示第i个记录应在的位置；q指示第i+1个记录的当前位置；  
  55.     int p=SL[0].next;                                  //p指示第一个记录的当前位置  
  56.     int q;  
  57.     for (int i=1;i
  58.     {  
  59.         //SL[1..i-1]中的记录关键字有序排列，第i个记录在SL中的当前位置应不小于i  
  60.         //为了保证  
  61.         while(p//找到第i个记录，并用p指示其在SL中的当前位置  
  62.             p=SL[p].next;  
  63.         q=SL[p].next;                      //q指示尚未调整的表尾  
  64.         if (p!=i)  
  65.         {  
  66.             STListType temp;  
  67.             temp = SL[p];  
  68.             SL[p] = SL[i];  
  69.             SL[i] = temp;                    //交换记录，使第i个记录到位   
  70.             SL[i].next=p;                       //指向被移走的记录，使得以后可以由while循环找到                            
  71.         }  
  72.         p=q;                                    //p指示尚未调整的表尾，为找第i+1个记录作准比  
  73.   
  74.         cout<<"Arrange-key:\n";  
  75.         for(int count=0;count
  76.             cout<
  77.         cout<
  78.         cout<<"Arrange-next:\n";  
  79.         for(int count=0;count
  80.             cout<
  81.         cout<
  82.     }     
  83. }  
  84.   
  85. int _tmain()  
  86. {  
  87.     STListType SL[100];  
  88.     int n;  
  89.     cout<<"ListInsSort.cpp运行结果:\n";  
  90.     int b[100],i;  
  91.     srand(time(0));  
  92.     cout<<"输入待排序元素个数n:";cin>>n;  
  93.     for(i=1;i
  94.     {  
  95.         b[i]=rand()%100;  
  96.         SL[i].key=b[i];  
  97.     }  
  98.     cout<<"排序前数组:\n";  
  99.     for(i=1;i
  100.         cout<
  101.     cout<
  102.     ListInsSort(SL,n);  
  103.     Arrange(SL,n);  
  104.     cout<<"排序后数组:\n";  
  105.     for(i=1;i
  106.         cout<
  107.     cout<
  108.     system("pause");     
  109. }  

 

希尔插入排序

    希尔排序又称缩小增量排序，（适用于待排序数列很无序的情况下）；基本思想是将待排序的记录划分成几组，从而减少参与直接插入排序的数据量，经过几次分组排序后，记录的排序已经基本有序，在对所有的记录实施最后的直接插入排序。

     对于希尔排序，具体步骤可以描述如下：假设待排序的记录为n个，先取整数d

Shell提出的选法：d1=n/2 , di+1=di/2

[html] view plain copy
  1. #include<iostream>  
  2. #include<iomanip>  
  3. #include<stdlib.h>  
  4. #include<time.h>  
  5. using namespace std;  
  6.   
  7. #define MAXI 11  
  8. typedef int KeyType;  
  9. typedef int ElemType;  
  10. struct rec   
  11. {  
  12.     KeyType key;  
  13.     ElemType data;  
  14. };  
  15. typedef rec sqlist[MAXI];  
  16.   
  17. void shellsort(sqlist b,int n)  
  18. {  
  19.     int i,j,gap,k;  
  20.     rec x;  
  21.     gap=n/2;  
  22.     while(gap>0)  
  23.     {  
  24.         for(i=gap+1;i<n;i++)  
  25.         {  
  26.             j=i-gap;  
  27.             while(j>0)  
  28.             if(b[j].key>b[j+gap].key)  
  29.             {  
  30.                 x=b[j];  
  31.                 b[j]=b[j+gap];  
  32.                 b[j+gap]=x;  
  33.                 j=j-gap;  
  34.             }  
  35.             else j=0;  
  36.             for(k=1;k<n;k++)  
  37.                 cout<<setw(4)<<b[k].key;  
  38.             cout<<endl;  
  39.         }  
  40.         gap=gap/2;  
  41.     }  
  42. }  
  43.   
  44. void main()  
  45. {cout<<"运行结果:\n";  
  46. sqlist a;int i,n=MAXI;  
  47. srand(time(0));  
  48. for(i=1;i<n;i++)  
  49. {a[i].key=rand()%80;  
  50. a[i].data=rand()%100;}  
  51. cout<<"排序前数组:\n";  
  52. for(i=1;i<n;i++)  
  53.     cout<<setw(4)<<a[i].key;  
  54. cout<<endl;  
  55. cout<<"数组排序过程演示:\n";  
  56. shellsort(a,n);  
  57. cout<<"排序后数组:\n";  
  58. for(i=1;i<n;i++)  
  59.     cout<<setw(4)<<a[i].key;  
  60. cout<<endl;cin.get();}  

1.2 交换排序

      交换排序：通过“交换”无序序列中的相邻记录从而得到其中关键字最小或最大的记录，并将他们加入到有序序列中，以增加记录的有序序列长度。

      主要思想是在排序过程中，通过比较待排序记录序列中元素的关键字，如果发现次序相反，则将存储位置交换来达到排序目的。

起泡排序

     它的基本思想是对所有相邻记录的关键字值进行比较，如果是逆序(a[j]>a[j+1]),则将其交换，最终达到有序。

  

[cpp] view plain copy
  1. #include "stdafx.h"  
  2. #include "stdafx.h"  
  3. #include   
  4. using namespace std;  
  5.   
  6. int bubbleSort (int number  ,int r[])  
  7. {  
  8.     int  temp;  
  9.     for (int i =0;i<=number-1;i++)  
  10.     {  
  11.         for (int j=0;j<=number-i-1;j++)  
  12.         {  
  13.             if (r[j]>r[j+1])  
  14.                 {  
  15.                 temp=r[j];  
  16.                 r[j]=r[j+1];  
  17.                 r[j+1]=temp;  
  18.             }  
  19.         }  
  20.     }  
  21.   
  22.     return 1;  
  23. }  
  24.   
  25. int _tmain(int argc, int argv[])  
  26. {  
  27.     std::cout<<"输入数组大小"<
  28.     std::cin>> argc;  
  29.     std::cout<<"输入数组内数据"<
  30.     for(int j=0;j
  31.     {    
  32.         std::cin>>argv[j];  
  33.     }  
  34.     bubbleSort (argc ,argv);  
  35.     for(int j=0;j
  36.     {    
  37.         std::cout << argv[j] << std::endl;   
  38.     }  
  39.     system("pause");  
  40.     return 0;  
  41. }  

在排序过程中，比较相邻的元素，如果第前个比后一个大，就交换他们两个。对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。针对所有的元素重复以上的步骤，除了最后一个。

for (int i =0;i<=number-1;i++)循环是指（一个元素向上冒泡，直到它找到合适的位置）这个过程的次数，即有多少个元素要进行冒泡操作；冒到上边的是最大的；

for (int j=0;j<=number-i-1;j++)循环是指进行冒泡操作的每一个元素，要经过做少次对比，才能找到合适的位置；

 快速排序

     快速排序的基本思想：首先将待排序记录序列中的所有记录作为当前待排序区域，从中任选一个记录（通常可选取第一个记录），以它的关键字作为枢纽，凡其关键字小于枢纽的记录均移到该记录之前，反之，凡关键字大于枢纽的记录均移至该纪录之后，这样一趟排序之后，记录的无序序列R[s..t]将分割成两部分：R[s..i-1]和R[i+1..t]，且R[j].key<=R[i].key<=R[k].key

 

[cpp] view plain copy
  1. #include "stdafx.h"  
  2. #include "stdafx.h"  
  3. #define number 100  
  4. #include  
  5. #include  
  6. #include  
  7. #include  
  8. #include  
  9.   
  10. //排序后按从小到大输出  
  11.   
  12. using namespace std;  
  13. typedef struct    
  14. {  
  15.     int key;  
  16.     int other;  //记录其他数据域  
  17.     int next;  
  18. }RecType;  
  19.   
  20. RecType S[number+1];  
  21.   
  22. int Partirion(RecType R[],int l,int h)  
  23. {  
  24.     //交换记录子序列R[1..h]中的记录，使枢纽记录交换到正确的位置，并返回其所在的位置  
  25.     int i=l;  
  26.     int j=h;              //用变量i,j记录待排序记录的首尾位置  
  27.     R[0]=R[i];            //以子表的第一个记录作为枢轴，将其暂存到记录R[0]中  
  28.     int x=R[i].key;       //用变量x存放枢纽记录的关键字  
  29.     while (i
  30.     {  
  31.         //从表的两端交替地向中间扫描  
  32.         while (i=x)  
  33.         {  
  34.             j--;  
  35.         }  
  36.         R[i]=R[j];          //将比枢纽小的记录移到低端  
  37.         while (i
  38.         {  
  39.             i++;  
  40.         }  
  41.         R[j]=R[i];          //将比枢纽大的记录移到高端  
  42.     }  
  43.     R[i]=R[0];              //枢纽记录到位  
  44.     return i;               //返回枢纽位置  
  45. }  
  46.   
  47.   
  48. void QuickSort(RecType R[],int s,int t)  
  49. {  
  50.     //对记录序列R[s..t]进行快速排序  
  51.     if (s
  52.     {  
  53.         int k,i;  
  54.         k=Partirion(R,s,t);  
  55.         QuickSort(R,s,k-1);  
  56.         QuickSort(R,k+1,t);  
  57.         cout<<"QuickSort:\n";  
  58.         for(i=2;i<=t;i++)  
  59.             cout<
  60.         cout<
  61.     }  
  62. }  
  63.   
  64. int _tmain()  
  65. {  
  66.     RecType SL[100];  
  67.     int n;  
  68.     cout<<"QuickSort.cpp运行结果:\n";  
  69.     int b[100],i;  
  70.     srand(time(0));  
  71.     cout<<"输入待排序元素个数n:";cin>>n;  
  72.     for(i=1;i
  73.     {  
  74.         b[i]=rand()%100;  
  75.         SL[i].key=b[i];  
  76.     }  
  77.     cout<<"排序前数组:\n";  
  78.     for(i=1;i
  79.         cout<
  80.     cout<
  81.     QuickSort(SL,1,n);  
  82.     cout<<"排序后数组:\n";  
  83.     for(i=2;i<=n;i++)  
  84.         cout<
  85.     cout<
  86.     system("pause");     
  87. }  

运行结果：

 

 

1.3 选择排序

      选择排序：从记录的无序序列中“选择”关键字最小或最大的记录，并将他加入到有序子序列中，以增加记录的有序序列的长度。

      基本思想是依次从待排序记录中选择出关键字值最小（或最大）的记录、关键字值次之的记录、...并分别将它们定位到序列左侧（或右侧）的第1位置、第2位置、...，从而使待排序的记录序列成为按关键字值由小到大（或有大到小）排列的有序序列。

直接选择排序

     有序序列中所有记录的关键字均小于无序序列中记录的关键字，则第i趟直接选择排序是从无序序列R[i..n]的n-i+1个记录中选择关键字最小的记录加入有序序列的末尾。

     

[cpp] view plain copy
  1. #include "stdafx.h"  
  2. #define number 100  
  3. #include  
  4. #include  
  5. #include  
  6. #include  
  7. #include  
  8. //排序后按从小到大输出  
  9. using namespace std;  
  10. typedef struct   
  11. {  
  12.     int key;  
  13.     int other; //记录其他数据域  
  14.     int next;  
  15. }RecType;  
  16. RecType S[number+1];  
  17. void SelectSort(RecType R[],int n)  
  18. {  
  19.     //对记录序列R[1..n]进行直接选择排序  
  20.     for (int i=1;i
  21.     {  
  22.         int k=i;  
  23.         for (int j=i+1;j<=n;j++)  
  24.         {  
  25.             if (R[k].key>R[j].key)  
  26.             {k=j;}  
  27.         }  
  28.     if (i!=k)  
  29.     {  
  30.         RecType temp;  
  31.         temp=R[i];  
  32.         R[i]=R[k];  
  33.         R[k]=temp;  
  34.     }  
  35.     }  
  36. }  
  37. int _tmain()  
  38. {  
  39.     RecType SL[100];  
  40.     int n;  
  41.     cout<<"SelectSort.cpp运行结果:\n";  
  42.     int b[100],i;  
  43.     srand(time(0));  
  44.     cout<<"输入待排序元素个数n:";  
  45.     cin>>n;  
  46.     for(i=1;i
  47.     {  
  48.         b[i]=rand()%100;  
  49.         SL[i].key=b[i];  
  50.     }  
  51.     cout<<"排序前数组:\n";  
  52.     for(i=1;i
  53.     cout<
  54.     cout<<"排序后数组:\n";  
  55.     for(i=2;i<=n;i++)  
  56.         cout<
  57.     cout<
  58.     system("pause");   
  59. }  


 

     

树形选择排序

     基本思想：首先是对n个待排序记录的关键字进行两两比较，从中选出[n/2]个较小者再两两比较，直到选出关键字最小的记录为止，此为一趟排序。

[html] view plain copy
  1. #include "stdafx.h"  
  2.   
  3. //锦标赛排序法  
  4. #include<iostream>  
  5. #include<iomanip>  
  6. #include<math.h>  
  7. #include<stdlib.h>  
  8. #include<time.h>  
  9.   
  10. using namespace std;  
  11. class DataNode //胜者树结点的类定义  
  12. {public:  
  13. int data;//数据值  
  14. int index;//树中的结点号  
  15. int active;//参选标志  
  16. };  
  17. //锦标赛排序中的调整算法;i是表中当前  
  18. //最小元素的下标,即胜者.从它开始向上调整  
  19. void UpdataTree(DataNode *tree,int i)  
  20. {int j;  
  21. if(i%2==0) //i为偶数,对手为左结点  
  22.     tree[(i-1)/2]=tree[i-1];//i为奇数,对手为右结点  
  23. else  
  24.     tree[(i-1)/2]=tree[i+1];  
  25. i=(i-1)/2; //i上升到双亲结点位置  
  26. while(i)  
  27. {if(i%2==0) j=i-1;//确定i的对手为左结点还是右结点  
  28. else j=i+1;  
  29. if(!tree[i].active||!tree[j].active)//比赛对手中间有一个空  
  30.     if(tree[i].active) tree[(i-1)/2]=tree[i];  
  31.     else tree[(i-1)/2]=tree[j]; //非空者上升到双亲结点  
  32. else                         //比赛对手都不为空  
  33.     if(tree[i].data<tree[j].data) tree[(i-1)/2]=tree[i];  
  34.     else tree[(i-1)/2]=tree[j];//胜者上升到双亲结点  
  35.     i=(i-1)/2; //i上升到双亲结点  
  36. }}  
  37. //建立树的顺序存储数组tree,将数组a[]中的元素复制到胜者树中,  
  38. //对它们进行排序,并把结果返回数组中,n是待排序元素个数  
  39. void TournmentSort(int a[],int n)  
  40. {DataNode *tree; //胜者树结点数组  
  41. DataNode item;  
  42. int m,i,j=0;  
  43. for(int k=0;k<n;k++)//计算满足>=n的2的最小次幂的数  
  44. {  
  45.     m=(int)pow((double) 2,(double)k);  
  46.     if(m>=n)  
  47.         break;  
  48. }  
  49. int bottomRowSize=m;  
  50. int TreeSize=2*bottomRowSize-1;//计算胜者树的大小:内结点+外结点数  
  51. int loadindex=bottomRowSize-1;//外结点开始位置  
  52. tree=new DataNode[TreeSize];  //动态分配胜者树结点数组空间  
  53. for(i=loadindex;i<TreeSize;i++)//复制数组数据到树的外结点中  
  54. {tree[i].index=i;//下标  
  55. if(j<n) {tree[i].active=1;tree[i].data=a[j++];}//复制数据  
  56. else tree[i].active=0; //后面的结点为空的外结点  
  57. }  
  58. i=loadindex;           //进行初始比较寻找最小的项  
  59. while(i)  
  60. {j=i;  
  61. while(j<2*i)          //处理各对比赛者  
  62. {if(!tree[j+1].active||tree[j].data<tree[j+1].data)  
  63. tree[(j-1)/2]=tree[j];  
  64. else tree[(j-1)/2]=tree[j+1];//胜者送入双亲  
  65. j+=2; //下一对参加比较的项  
  66. }  
  67. i=(i-1)/2;//i退到双亲,直到i=0为止  
  68. }  
  69. for(i=0;i<n-1;i++)//处理其他n-1个元素  
  70. {a[i]=tree[0].data;//当前最小元素送数组a  
  71. tree[tree[0].index].active=0;//该元素相应外结点不再比赛  
  72. UpdataTree(tree,tree[0].index);//从该处向上修改  
  73. }  
  74. a[n-1]=tree[0].data;  
  75. }  
  76. //锦标赛排序法的测试  
  77. void main()  
  78. {cout<<"JinBiaoSai.cpp运行结果:\n";  
  79. int n,b[100],i;  
  80. srand(time(0));  
  81. cout<<"输入待排序元素个数n:";cin>>n;  
  82. for(i=0;i<n;i++) b[i]=rand()%100;  
  83. cout<<"排序前数组:\n";  
  84. for(i=0;i<n;i++)  
  85.     cout<<setw(4)<<b[i];  
  86. cout<<endl;  
  87. TournmentSort(b,n);  
  88. cout<<"排序后数组:\n";  
  89. for(i=0;i<n;i++)  
  90.     cout<<setw(4)<<b[i];  
  91. cout<<endl;  
  92. cin.get();cin.get();  
  93. }  


 

 

 

树形选择排序：

[cpp] view plain copy
  1. #include "stdafx.h"  
  2. #include   
  3. #include   
  4. #include   
  5. #include   
  6. #include   
  7. #include   
  8. #include   
  9. #include   
  10. #include  
  11.   
  12. using namespace std;  
  13.   
  14. #define MAX_SIZE 20   
  15. typedef int KeyType;  
  16. typedef int InfoType; //定义其他数据类型   
  17. struct RedType{ KeyType key; InfoType otherinfo; };    
  18. struct SqList  
  19. {   
  20.     RedType r[MAX_SIZE];      
  21.     int length;   
  22. };  
  23. void print(SqList L)  
  24. {   
  25.     int i;   
  26.     for(i=1;i<=L.length;i++)   
  27.         cout<<"("<","<")";   
  28.     cout<
  29. }  
  30.   
  31. void TreeSort(SqList &L)  
  32. {   
  33.     int i,j,j1,k,k1,l;  
  34.     float n=L.length;   
  35.     RedType *t;   
  36.     l=(int)ceil(log(n)/log(2.0))+1; //完全二叉树的层数;ceil取上整，返回比x大的最小整数  
  37.     k=(int)pow(2.0,l)-1; //k为l层完全二叉树的结点总数   
  38.     k1=(int)pow(2.0,l-1)-1; //k1为l-1层二叉完全二叉树的结点总数   
  39.     t=(RedType*)malloc(k*sizeof(RedType)); //二叉树采用顺序存储   
  40.     for(i=1;i<=n;i++) //将L.r赋值给叶子结点   
  41.         t[k1+i-1]=L.r[i];   
  42.     for(i=k1+n;i//给多余的叶子结点的关键字赋无穷大值   
  43.         t[i].key=INT_MAX;   
  44.     j1=k1;   
  45.     j=k;   
  46.     while(j1)  
  47.     {   
  48.         //给非叶子结点赋值   
  49.         for(i=j1;i
  50.         {  
  51.             t[i].key
  52.         }         
  53.         j=j1; j1=(j1-1)/2;   
  54.         cout<<"给非叶子结点赋值:"<//循环一次，找到最小的  
  55.         print(L);   
  56.     }   
  57.     for(i=0;i
  58.     {   
  59.         L.r[i+1]=t[0]; //键当前最小值赋给L.r[i]   
  60.         j1=0;   
  61.         for(j=1;j//沿树根找到结点t[0]在叶子结中的序号j1   
  62.             t[2*j1+1].key==t[j1].key?(j1=2*j1+1):(j1=2*j1+2);   
  63.         t[j1].key=INT_MAX;   
  64.         while(j1)  
  65.         {   
  66.             j1=(j1+1)/2-1; //序号为j1的节点的双亲节点序号   
  67.             t[2*j1+1].key<=t[2*j1+2].key?(t[j1]=t[2*j1+1]):(t[j1]=t[2*j1+2]);   
  68.         }   
  69.         cout<<"循环排序:"<
  70.         print(L);   
  71.     }   
  72.     free(t);   
  73. }  
  74. #define N 8  
  75. void main()  
  76. {   
  77.     RedType d[N]={{49,1},{38,2},{65,3},{97,4},{76,5},{13,6},{27,7},{49,8}};   
  78.     SqList l;   
  79.     int i;   
  80.     for(i=0;i
  81.         l.r[i+1]=d[i];   
  82.     l.length=N;   
  83.     cout<<"排序前："<
  84.     print(l);   
  85.     TreeSort(l);   
  86.     cout<<"排序后："<
  87.     print(l);   
  88.     system("pause");   
  89. }  

 

排序过程中t[k1+i-1]=L.r[i];把L里的数据存储t[k1+i-1]中，为排序需要

k=(int)pow(2.0,l)-1; //k为l层完全二叉树的结点总数

t=(RedType*)malloc(k*sizeof(RedType)); //二叉树采用顺序存储

的存储空间；

运行结果：

 

堆排序

     其左右子树分别是堆，任何一个结点的值不大(或不小于)左右孩子节点，则最顶端元素必是序列中的最大值或最小值，分别称为小顶堆或大顶堆（小堆或大堆）。堆排序是利用堆的特性对记录序列进行排序的一种排序算法。其基本思想是：先建一个堆，即先选一个关键字最大或最小的记录，然后与序列中的最后一个记录交换，之后将序列中前n-1个记录重新调整为一个堆(调堆的过程称为“筛选”)，再将堆顶记录和第n-1个记录交换，如此反复至排序结束。注意：第i 次筛选的前提是从2到n-i 是一个堆，即筛选是对一棵左/右子树均为堆的完全二叉树“调整”根节点使整棵二叉树为堆的过程。

[html] view plain copy
  1. #include "stdafx.h"  
  2. #include <iostream>  
  3. using namespace std;  
  4.   
  5. void sift(int R[],int i,int m) //R[]要排序的数组;i是指是从堆的第几行的首元素 即i=1 2 4 8 16...;m是指数组中一共多少个元素  
  6. {  
  7.     //设R[i+1..m]中各元素满足堆的定义,本算法调整R[i]使序列R[i..m]中的元素满足堆的性质  
  8.     int temp = R [i];  
  9.     for (int j=2*i;j<=m;j*=2)  
  10.     {  
  11.          //在堆的同一层进行比较，如果右边的大于左边的，则继续向右查找 ，为了保证下面和temp比较的R[j],是这一层上最大的一个  
  12.         if ((j<m)&&(R[j]<R[j+1]))   
  13.         {  
  14.             j++;  
  15.         }  
  16.         if (temp<R[j]) //temp和每一层最大的数比较，如果小于最大的，则把最大的的值赋给R[i]  
  17.         {  
  18.             R[i]=R[j];  
  19.             i=j;         //修改i的值，此时R[i]=R[j]的值相同         
  20.         }   
  21.         else  
  22.         {  
  23.             break;  
  24.         }  
  25.     }  
  26.     R[i]=temp;         //最初要调整的节点放在正确的位置  
  27. }  
  28.   
  29. void  HeapSort( int R[],int n)  
  30. {  
  31.     int i ;  
  32.     int nCreateTime=1;  
  33.     for (i=n/2;i>0;i--)  
  34.     {  
  35.         sift(R,i,n);    //建堆时i从n/2起递减，是指i从从最底层起依次循环向顶层排序   
  36.         std::cout<<"建堆"<<nCreateTime<<endl;  
  37.         for(int j=1;j<9;j++)    
  38.         {   
  39.             std::cout << R[j];     
  40.         }  
  41.         nCreateTime++;  
  42.         std::cout<<endl;  
  43.     }  
  44.     int nAdjustTime=1;  
  45.     for (i=n;i>1;i--)  
  46.     {  
  47.         int temp ;  
  48.         temp=R[i];  
  49.         R[i]=R[1];  
  50.         R[1]=temp;  
  51.         sift(R,1,i-1);  
  52.         std::cout<<"重新调整"<<nAdjustTime<<endl;  
  53.         for(int j=1;j<9;j++)    
  54.         {   
  55.             std::cout << R[j];     
  56.         }  
  57.         nAdjustTime++;  
  58.         std::cout<<endl;  
  59.     }  
  60.   
  61. }  
  62.   
  63. int _tmain(int argc, _TCHAR* argv[])  
  64. {  
  65.     int data[9]={0,6,9,3,1,5,8,9};  
  66.     std::cout<<"初始序列"<<endl;  
  67.     for(int j=1;j<9;j++)    
  68.     {      
  69.         std::cout << data[j];     
  70.     }  
  71.     std::cout<<endl;  
  72.     HeapSort( data,8);  
  73.     std::cout<<"生成的有序序列"<<endl;  
  74.     for(int j=1;j<9;j++)    
  75.     {      
  76.         std::cout << data[j];     
  77.     }  
  78.     std::cout<<endl;  
  79.     system("pause");    
  80.     return 0;  
  81. }  

运行结果：


 

1.4 归并排序

      归并排序：通过“归并”两个或两个以上的有序序类，逐步增加有序序列的长度。

归并排序 2-路归并排序

     其基本思想是：将一个具有n个待排序记录的序列看成是n个长度为1的有序序列，然后进行两两归并，得到n/2个长度为2的有序序列，在进行两两归并，得到n/4个长度为4的有序序列，如此重复，直至得到一个长度为n的有序序列为止。

 

[cpp] view plain copy
  1. #include "stdafx.h"  
  2. #define number 100  
  3. #include  
  4. #include  
  5. #include  
  6. #include  
  7. #include  
  8.   
  9. //排序后按从小到大输出  
  10.   
  11. using namespace std;  
  12. typedef struct    
  13. {  
  14.     int key;  
  15.     int other;  //记录其他数据域  
  16.     int next;  
  17. }RecType;  
  18.   
  19. RecType S[number+1];  
  20.   
  21. void Merge(RecType R[],RecType R1[],int i,int l,int h)  
  22. {  
  23.     //将有序的R[i..l]和R[l+1..h]归并为有序的R1[i..h]  
  24.     int j;  
  25.     int k;  
  26.     for (j=l+1,k=i;i<=l && j<=h;k++)  
  27.     {  
  28.         //将R[]中记录由小到大地并入R1  
  29.         if (R[i].key<=R[j].key)  
  30.         {  
  31.             R1[k]=R[i++];  
  32.         }   
  33.         else  
  34.         {  
  35.             R1[k]=R[j++];  
  36.         }  
  37.     } //for  
  38.     if(i<=l)   
  39.     {  
  40.         R1[k++]=R[i++];         
  41.     }         
  42.     if(j<=h)  
  43.     {  
  44.         R1[k++]=R[j++];         //将剩余的R[j..h]复制到R1  
  45.     }  
  46. }//Merge  
  47.   
  48. void Msort(RecType R[],RecType R1[],int s,int t)  
  49. {  
  50.     //将R[s..t]2-路归并排序为R1[s..t]  
  51.     RecType R2[100];  
  52.     if (s==t)  
  53.     {  
  54.         R1[s]=R[s];  
  55.     }  
  56.     else  
  57.     {  
  58.         int m=(s+t)/2;          //将R[s..t]平分为R[s..m]和R[m+1..t]  
  59.         Msort(R,R2,s,m);        //递归的将R[s..m]归并为有序的R2[s..m]  
  60.         Msort(R,R2,m+1,t);      //递归的将R[m+1..t]归并为有序的R2[m+1..t]  
  61.         Merge(R2,R1,s,m,t);     //将R2[s..m]和R2[m+1..t]归并到R1[s..t]  
  62.     }//if  
  63. }//Msort  
  64.   
  65. int _tmain()  
  66. {  
  67.     int n;  
  68.     cout<<"MergingSort.cpp运行结果:\n";  
  69.     int b[100],i;  
  70.     RecType R1[100];  
  71.     srand(time(0));  
  72.     cout<<"输入待排序元素个数n:";cin>>n;  
  73.     RecType SL[100];  
  74.     for(i=1;i<=n;i++)  
  75.     {  
  76.         b[i]=rand()%100;  
  77.         SL[i].key=b[i];  
  78.     }  
  79.     cout<<"排序前数组:\n";  
  80.     for(i=1;i<=n;i++)  
  81.         cout<
  82.     cout<
  83.     Msort(SL,R1,1,n);  
  84.     cout<<"排序后数组:\n";  
  85.     for(i=1;i<=n;i++)  
  86.         cout<
  87.     cout<
  88.     system("pause");     
  89. }  


 

 

1.5 分配排序

      前面讨论的排序算法都是基于关键字之间的比较，通过比较判断出大小，然后进行调整。而分配排序则不然，它是利用关键字的结构，通过“分配”和“收集”的办法来实现排序。

      分配排序：通过对无序序列中的记录进行反复的“分配”和“收集”操作，逐步是无序序列变为有序序列。

分配排序分为：桶排序和基数排序两类。

计数排序

      

??计数排序的过程类似小学选班干部的过程,如某某人10票,作者9票,那某某人是班长,作者是副班长

大体分两部分,第一部分是拉选票和投票,第二部分是根据你的票数入桶

看下具体的过程,一共需要三个数组,分别是待排数组,票箱数组,和桶数组

var unsorted = new int[] { 6, 2, 4, 1, 5, 9 };  //待排数组

var ballot = new int[unsorted.Length];          //票箱数组

var bucket = new int[unsorted.Length];          //桶数组

最后再看桶数组,先看待排数组和票箱数组

初始状态,迭代变量i = 0时,待排数组[i] = 6,票箱数组[i] = 0,这样通过迭代变量建立了数字与其桶号(即票数)的联系

待排数组[ 6 2 4 1 5 9 ] i = 0时,可以从待排数组中取出6

票箱数组[ 0 0 0 0 0 0 ] 同时可以从票箱数组里取出6的票数0,即桶号

拉选票的过程

首先6出列开始拉选票,6的票箱是0号,6对其它所有数字说,谁比我小或与我相等,就给我投票,不然揍你

于是,2 4 1 5 分别给6投票,放入0号票箱,6得四票

待排数组[ 6 2 4 1 5 9 ]

票箱数组[ 4 0 0 0 0 0 ]

 

接下来2开始拉选票,对其它人说,谁比我小,谁投我票,不然弄你!于是1投了一票,其他人比2大不搭理,心想你可真二

于是2从1那得到一票

待排数组[ 6 2 4 1 5 9 ]

票箱数组[ 4 1 0 0 0 0 ]

 

再然后是,

4得到2和1的投票,共计两票

1得到0票,没人投他

5得到2,4,1投的三张票

9是最大,得到所有人(自己除外)的投票,共计5票(数组长度-1票)

 

投票完毕时的状态是这样

待排数组[ 6 2 4 1 5 9 ]

票箱数组[ 4 1 2 0 3 5 ]


入桶的过程

投票过程结束,每人都拥有自己的票数,桶数组说,看好你自己的票数,进入与你票数相等的桶,GO

6共计5票,进入5号桶

2得1票,进入1号桶,有几票就进几号桶

4两票,进2号桶,5三票进3号桶,9有5票,进5号桶

待排数组[ 6 2 4 1 5 9 ]

票箱数组[ 4 1 2 0 3 5 ]

-----------------------

入桶前 [ 0 1 2 3 4 5 ] //里边的数字表示桶编号

入桶后 [ 1 2 4 5 6 9 ] //1有0票,进的0号桶

排序完毕,顺序输出即可[ 1 2 4 5 6 9]

 

可以看到,数字越大票数越多,9得到除自己外的所有人的票,5票,票数最多所以9最大,

每个人最多拥有[数组长度减去自己]张票

1票数最少,所以1是最小的

 


 

[cpp] view plain copy
  1. #include "stdafx.h"  
  2. #include   
  3. #include    
  4. #include    
  5. #include    
  6. #include   
  7. #include   
  8. #include  
  9. #include  
  10. #include  
  11.   
  12. using namespace std;   
  13.   
  14. void CountingSort(int *A,int *B,int *Order,int N,int K)   
  15. {   
  16.     int *C=new int[K+1];   
  17.     int i;   
  18.     memset(C,0,sizeof(int)*(K+1));   
  19.     for (i=1;i<=N;i++) //把A中的每个元素分配   
  20.         C[A[i]]++;   
  21.     for (i=2;i<=K;i++) //统计不大于i的元素的个数      
  22.     {  
  23.         C[i]+=C[i-1];  
  24.     }  
  25.     for (i=N;i>=1;i--)   
  26.     {   
  27.         B[C[A[i]]]=A[i]; //按照统计的位置，将值输出到B中，将顺序输出到Order中   
  28.         Order[C[A[i]]]=i;   
  29.         C[A[i]]--;   
  30.     }   
  31. }   
  32. int main()   
  33. {   
  34.     int *A,*B,*Order,N=15,K=10,i;   
  35.     A=new int[N+1];   
  36.     B=new int[N+1];   
  37.     Order=new int[N+1];   
  38.     for (i=1;i<=N;i++) A[i]=rand()%K+1; //生成1..K的随机数   
  39.     cout<<"Before CS:\n";   
  40.     for (i=1;i<=N;i++)   
  41.         cout<
  42.     cout<
  43.     CountingSort(A,B,Order,N,K);   
  44.     printf("\nAfter CS:\n");   
  45.     for (i=1;i<=N;i++)   
  46.         cout<
  47.     cout<
  48.     cout<<"\nOrder:\n";   
  49.     for (i=1;i<=N;i++)   
  50.         cout<
  51.     cout<
  52.     system("pause");  
  53.     return 0;   
  54. }   


运行结果：


 

 

桶排序

     桶排序（Bucket Sort）也称箱排序（Bin Sort）,其基本思想是：设置若干个桶，依次扫描待排序记录R[1..n],把关键字等于k的记录全部都装到第k个桶里（分配），按序号依次将各非空的桶首尾连接起来（收集）。桶的个数取决于关键字的取值范围。

桶排序 (Bucket sort)或所谓的箱排序，是一个排序算法，工作的原理是将数组分到有限数量的桶子里。
基本思路：
1.设置一个定量的数组当作空桶子。
2.寻访串行，并且把项目一个一个放到对应的桶子去。
3.对每个不是空的桶子进行排序。
4.从不是空的桶子里把项目再放回原来的串行中。

 

无序数组有个要求,就是成员隶属于固定(有限的)的区间,如范围为[0-9](考试分数为1-100等)

例如待排数字[6 2 4 1 5 9]

准备10个空桶,最大数个空桶

[6 2 4 1 5 9]           待排数组

[0 0 0 0 0 0 0 0 0 0]   空桶

[0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

 

1,顺序从待排数组中取出数字,首先6被取出,然后把6入6号桶,这个过程类似这样:空桶[ 待排数组[ 0 ] ] = 待排数组[ 0 ]

[6 2 4 1 5 9]           待排数组

[0 0 0 0 0 0 6 0 0 0]   空桶

[0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

 

2,顺序从待排数组中取出下一个数字,此时2被取出,将其放入2号桶,是几就放几号桶

[6 2 4 1 5 9]           待排数组

[0 0 2 0 0 0 6 0 0 0]   空桶

[0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

 

3,4,5,6省略,过程一样,全部入桶后变成下边这样

[6 2 4 1 5 9]           待排数组

[0 1 2 0 4 5 6 0 0 9]   空桶

[0 1 2 3 4 5 6 7 8 9]   桶编号(实际不存在)

 

0表示空桶,跳过,顺序取出即可:1 2 4 5 6 9

[cpp] view plain copy
  1. /* 桶排序实现 */   
  2. #include "stdafx.h"  
  3. #include   
  4. #include    
  5. #include    
  6. #include    
  7. #include   
  8. #include   
  9. #include  
  10. #include  
  11. #include  
  12.   
  13. using namespace std;   
  14.   
  15. void BucketSort(int *A,int *B,int N,int K)   
  16. {   
  17.     int *C=new int[K+1];   
  18.     int i,j,k;   
  19.     memset(C,0,sizeof(int)*(K+1));   
  20.     for (i=1;i<=N;i++) //把A中的每个元素按照值放入桶中   
  21.         C[A[i]]++;   
  22.     for (i=j=1;i<=K;i++,j=k) //统计每个桶元素的个数，并输出到B   
  23.         for (k=j;k
  24.             B[k]=i;   
  25. }  
  26.   
  27. int main()   
  28. {   
  29.     int *A,*B,N=100,K=100,i;   
  30.     A=new int[N+1];   
  31.     B=new int[N+1];   
  32.     cout<<"排序前："<
  33.     for (i=1;i<=N;i++)   
  34.     {  
  35.         A[i]=rand()%K+1; //生成1..K的随机数   
  36.         cout<
  37.     }     
  38.     cout<
  39.     BucketSort(A,B,N,K);  
  40.     cout<<"排序后："<
  41.     for (i=1;i<=N;i++)   
  42.     {  
  43.         cout<
  44.     }  
  45.     cout<
  46.     system("pause");    
  47.     return 0;   
  48. }   

运行结果：


 

这种特殊实现的方式时间复杂度为O(N+K)，空间复杂度也为O(N+K)，同样要求每个元素都要在K的范围内。更一般的，如果我们的K很大，无法直接开出O(K)的空间该如何呢？
 
首先定义桶，桶为一个数据容器，每个桶存储一个区间内的数。依然有一个待排序的整数序列A，元素的最小值不小于0，最大值不超过K。假设我们有M个桶，第i个桶Bucket[i]存储iK/M至(i+1)K/M之间的数，有如下桶排序的一般方法：
 1.扫描序列A，根据每个元素的值所属的区间，放入指定的桶中(顺序放置)。
 2.对每个桶中的元素进行排序，什么排序算法都可以，例如快速排序。
 3.依次收集每个桶中的元素，顺序放置到输出序列中。
 
对该算法简单分析，如果数据是期望平均分布的，则每个桶中的元素平均个数为N/M。如果对每个桶中的元素排序使用的算法是快速排序，每次排序的时间复杂度为O(N/Mlog(N/M))。则总的时间复杂度为O(N)+O(M)O(N/Mlog(N/M)) = O(N+ Nlog(N/M)) = O(N + NlogN - NlogM)。当M接近于N是，桶排序的时间复杂度就可以近似认为是O(N)的。就是桶越多，时间效率就越高，而桶越多，空间却就越大，由此可见时间和空间是一个矛盾的两个方面。

 

[cpp] view plain copy
  1. /*桶排序实现 */   
  2. #include "stdafx.h"  
  3. #include    
  4. #include    
  5. #include    
  6. #include    
  7. #include    
  8. #include   
  9. #include  
  10. #include  
  11. #include  
  12.   
  13. using namespace std;   
  14. struct linklist   
  15. {   
  16.     linklist *next;   
  17.     int value;   
  18.     linklist(int v,linklist *n):value(v),next(n){}   
  19.     ~linklist() {if (next) delete next;}   
  20. };   
  21. inline int cmp(const void *a,const void *b)   
  22. {   
  23.     return *(int *)a-*(int *)b;   
  24. }   
  25. /* 为了方便，我把A中元素加入桶中时是倒序放入的，而收集取出时也是倒序放入序列的，所以不违背稳定排序。 */   
  26.   
  27. void BucketSort(int *A,int *B,int N,int K)   
  28. {   
  29.     linklist *Bucket[101],*p;  
  30.     //建立桶   
  31.     int i,j,k,M; M=K/100;   
  32.     memset(Bucket,0,sizeof(Bucket));   
  33.     for (i=1;i<=N;i++)   
  34.     {   
  35.         k=A[i]/M;   
  36.     //把A中的每个元素按照的范围值放入对应桶中   
  37.         Bucket[k]=new linklist(A[i],Bucket[k]);   
  38.     }   
  39.     for (k=j=0;k<=100;k++)   
  40.     {   
  41.         i=j;   
  42.         for (p=Bucket[k];p;p=p->next)   
  43.             B[++j]=p->value;   
  44.         //把桶中每个元素取出，排序并加入B   
  45.         delete Bucket[k];   
  46.         qsort(B+i+1,j-i,sizeof(B[0]),cmp);   
  47.     }   
  48. }   
  49. int main()   
  50. {   
  51.     int *A,*B,N=100,K=100,i;   
  52.     A=new int[N+1];   
  53.     B=new int[N+1];   
  54.     for (i=1;i<=N;i++)   
  55.     {  
  56.         A[i]=rand()%K+1; //生成1..K的随机数   
  57.         cout<
  58.     }     
  59.     cout<
  60.     BucketSort(A,B,N,K);  
  61.     cout<<"排序后："<
  62.     for (i=1;i<=N;i++)   
  63.     {  
  64.         cout<
  65.     }  
  66.     cout<
  67.     system("pause");   
  68.     return 0;   
  69. }   

运行结果：

 

基数排序

     基数排序（Radix Sort）是对桶排序的改进和推广。

     基本思想：将一个关键字分解成多个“关键字”，再利用多关键字排序的思想对记录序列进行排序。基数排序就是借助“多关键字排序”的思想来实现“单关键字排序”的算法。

     假设有n个记录的待排序序列{R1,R2,...,Rn},每个记录Ri中含有d个关键字，则称上述记录序列对关键字有序，是指对于序列中的任意两个记录Ri和Rj（1<=i

具体做法为：

     （1）待排序的记录以指针相链，构成一个链表。

     （2）“分配”时，按当前“关键字位”的取值，将记录分配到不同的“链队列”中，每个队列中记录的“关键字位”相同。

     （3）“收集”时，按当前关键字取值从小到大将各队首尾相链接成一个链表；对每个关键字位均重复2）和3）两步。如下所示：

p->369->367->167->239->237->138->230->139

第一次分配得到：

B[0].f->230<-B[0].e

B[7].f->367->167->237<-B[7].e

B[8].f->138<-B[8].e

B[9].f->369->239->139<-B[9].e

第一次收集得到：

p->230->367->167->237->138->369->239->139

第二次分配得到：

B[3].f->230->237->138->239->139<-B[3].e

B[6].f->367->167->369<-B[6].e

第二次收集得到：

p->230->237->138->239->139->367->167->369

第三次分配得到：

B[1].f->138->139->167<-B[1].e

B[2].f->230->237->239<=B[2].e

B[3].f->367->369<-B[3].e

第三次收集之后便得到记录的有序序列：

p->138->139->167->230->237->239->367->369


 

[cpp] view plain copy
  1. #include "stdafx.h"  
  2. #include     
  3. #include    
  4. #include    
  5. #include    
  6.   
  7. using namespace std;    
  8.   
  9. int maxbit(int data[],int n) //辅助函数，求数据的最大位数  
  10.   
  11. {  
  12.   
  13.     int d = 1; //保存最大的位数  
  14.   
  15.     int p =10;  
  16.   
  17.     for(int i = 0;i < n; ++i)  
  18.   
  19.     {  
  20.   
  21.         while(data[i] >= p)  
  22.   
  23.         {  
  24.   
  25.             p *= 10;  
  26.   
  27.             ++d;  
  28.   
  29.         }  
  30.   
  31.     }  
  32.   
  33.     return d;  
  34.   
  35. }  
  36.   
  37. void radixsort(int data[],int n) //基数排序  
  38.   
  39. {  
  40.   
  41.     int d = maxbit(data,n);  
  42.   
  43.     int * tmp = new int[n];  
  44.   
  45.     int * count = new int[10]; //计数器  
  46.   
  47.     int i,j,k;  
  48.   
  49.     int radix = 1;  
  50.   
  51.     for(i = 1; i<= d;i++) //进行d次排序  
  52.   
  53.     {  
  54.   
  55.         for(j = 0;j < 10;j++)  
  56.   
  57.             count[j] = 0; //每次分配前清空计数器  
  58.   
  59.         for(j = 0;j < n; j++)  
  60.   
  61.         {  
  62.   
  63.             k = (data[j]/radix)%10; //统计每个桶中的记录数  
  64.   
  65.             count[k]++;  
  66.   
  67.         }  
  68.   
  69.         for(j = 1;j < 10;j++)  
  70.   
  71.             count[j] = count[j-1] + count[j]; //将tmp中的位置依次分配给每个桶  
  72.   
  73.         for(j = n-1;j >= 0;j--) //将所有桶中记录依次收集到tmp中  
  74.   
  75.         {  
  76.   
  77.             k = (data[j]/radix)%10;  
  78.   
  79.             tmp[count[k]-1] = data[j];  
  80.   
  81.             count[k]--;  
  82.   
  83.         }  
  84.   
  85.         for(j = 0;j < n;j++) //将临时数组的内容复制到data中  
  86.   
  87.             data[j] = tmp[j];  
  88.   
  89.         radix = radix*10;  
  90.   
  91.     }  
  92.   
  93.     delete [] tmp;  
  94.   
  95.     delete [] count;  
  96.   
  97. }  
  98.   
  99. int _tmain(int argc, _TCHAR* argv[])    
  100. {    
  101.     int data[10]={267,6,9,679,0,999,99,9,22,11};    
  102.     std::cout<<"初始序列"<
  103.     for(int j=0;j<10;j++)      
  104.     {        
  105.             std::cout <
  106.     }    
  107.     std::cout<
  108.     radixsort( data,10);    
  109.     std::cout<<"生成的有序序列"<
  110.     for(int j=0;j<10;j++)      
  111.     {        
  112.          std::cout << setw(4)<
  113.     }    
  114.     std::cout<
  115.     system("pause");  system(class="string">"color:#0000ff;">"pause");        
  116.     return 0;    
  117. }    


 运行结果：

各种排序算法比较

 

排序法 平均时间 最差情形 稳定度 额外空间 备注
冒泡 O(n2)     O(n2) 稳定 O(1) n小时较好
交换     O(n2)     O(n2) 不稳定 O(1) n小时较好
选择 O(n2) O(n2) 不稳定 O(1) n小时较好
插入 O(n2) O(n2) 稳定 O(1) 大部分已排序时较好
基数 O(logRB) O(logRB) 稳定 O(n)

B是真数(0-9)，

R是基数(个十百)

Shell O(nlogn) O(ns) 1 不稳定 O(1) s是所选分组
快速 O(nlogn) O(n2) 不稳定 O(nlogn) n大时较好
归并 O(nlogn) O(nlogn) 稳定 O(1) n大时较好
堆 O(nlogn) O(nlogn) 不稳定 O(1) n大时较好


 

2 外部排序

外部排序：若参加排序的记录数量很大，整个排序过程不能一次在内存中完成，则称此类排序问题为外部排序；

 

 

 

 

      以上博客，如有参考使用，请标明出处；

 

参考:

 《》 第二版   陈守孔 著

参考的网上内容：

http://blog.csdn.net/onedreamer/article/details/6745006
http://blog.csdn.net/zhangkaihang/article/details/7394806
http://blog.csdn.net/yincheng01/article/category/1269370/1
http://blog.csdn.net/yincheng01/article/details/8205037

https://www.byvoid.com/blog/sort-radix
http://www.cnblogs.com/kkun/archive/2011/11/23/2260299.html
http://www.cnblogs.com/kkun/archive/2011/11/23/2260267.html
http://blog.csdn.net/hkx1n/article/details/3922249

阅读(1549) | 评论(0) | 转发(0) |
0

上一篇：各种排序算法的实现及其比较（c++实现）

下一篇：13种排序算法详解(相当清楚，还附有flash动画)

给主人留下些什么吧！~~
关于我们 | 关于IT168 | 联系方式 | 广告合作 | 法律声明 | 免费注册

Copyright 2001-2010 ChinaUnix.net All Rights Reserved 北京皓辰网域网络信息技术有限公司. 版权所有

感谢所有关心和支持过ChinaUnix的朋友们

16024965号-6