AI 助理
文档备案控制台
开发者社区 人工智能 文章 正文

六种排序的C++实现

2013-08-10 705
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： class SortNum    {   public:    SortNum();    virtual ~SortNum();       void exchange(int& b,int& c);//交换数据       void listout(int a[],int n);/...
  1. class SortNum   
  2. {  
  3. public:  
  4.  SortNum();  
  5.  virtual ~SortNum();  
  6.     void exchange(int& b,int& c);//交换数据  
  7.     void listout(int a[],int n);//列出所有  
  8.  void selectSort(int a[],int n);//选择  
  9.  void bublbleSort(int a[],int n);//冒泡  
  10.  void insertSort(int a[],int n);//插入  
  11.  void baseSort(int a[],int n);//基数  
  12.  void quickSort(int a[],int n,int left,int right);//快速  
  13.    
  14.  void Merge(int *SR, int *TR, int i, int m, int n);//归并  
  15.  void Msort( int *SR, int *TR1, int s, int t );  
  16.  void Copy( int *S, int *T, int s, int t );  
  17.   
  18. };  

  

 

具体实现：

 

view plain copy to clipboard print ?
    1. #include "SortNum.h"  
    2. #include "iostream.h"  
    3. //////////////////////////////////////////////////////////////////////  
    4. // Construction/Destruction  
    5. //////////////////////////////////////////////////////////////////////  
    6.   
    7. SortNum::SortNum()  
    8. {  
    9.    
    10.   
    11. }  
    12.   
    13. SortNum::~SortNum()  
    14. {  
    15.   
    16. }  
    17.   
    18. //交换两个元素  
    19. void SortNum::exchange(int& b,int& c)  
    20. {  
    21.  int tem;  
    22.  tem=b;  
    23.  b=c;  
    24.  c=tem;  
    25. }  
    26. //输出数组所有元素  
    27. void SortNum::listout(int a[],int n)  
    28. {  
    29.  for(int i=0;i<n;i++)  
    30.   cout <<a[i]<<" ";  
    31.  cout <<endl;  
    32. }  
    33.   
    34.   
    35. //选择排序  
    36. void SortNum::selectSort(int a[],int n)  
    37. {  
    38.  for(int i=0;i<n-1;i++)  
    39.   {  
    40.    int k=i;  
    41.    for(int j=i+1;j<n;j++)  
    42.     if(a[j]<a[k])  
    43.      k=j;  
    44.    exchange(a[i],a[k]);  
    45.    listout(a,n);  
    46.      
    47.   }  
    48. }  
    49. //冒泡排序  
    50. void SortNum::bublbleSort(int a[],int n)  
    51. {  
    52.  for(int i=n;i>1;i--)  
    53.    for(int j=0;j<i-1;j++)  
    54.    {  
    55.     if(a[j]>a[j+1])  
    56.     {  
    57.      exchange(a[j],a[j+1]);  
    58.      listout(a,n);  
    59.        
    60.     }  
    61.    }  
    62. }  
    63. //插入排序  
    64. void SortNum::insertSort(int a[],int n)  
    65. {  
    66.  for(int i=1;i<n;i++)//从第二个元素开始  
    67.   {  
    68.    int tem=a[i];  
    69.    int j;  
    70.    for(j=i-1;j>=0 && tem<a[j];j--)//判断比其小的，因为前面已经排好序列了，所以可以比，然后后退  
    71.     a[j+1]=a[j];  
    72.    a[j+1]=tem;//插入  
    73.    listout(a,n);  
    74.     
    75.   }  
    76. }  
    77. //基数排序  
    78. void SortNum::baseSort(int a[],int n)  
    79. {  
    80.       int r=10;//基数为十  
    81.    int tem=1;  
    82.     
    83.     
    84.    int max=a[0];  
    85.    for(int i=0;i<n;i++)//找出最大的，以在while中确定结束的时机  
    86.    {  
    87.     if(a[i]>max)  
    88.      max=a[i];  
    89.    }  
    90.   while((max%r)/tem !=0)//若最大的运算完为0.则整个基数排序结束  
    91.   {  
    92.    for(int i=n;i>1;i--)  
    93.     for(int j=0;j<i-1;j++)  
    94.     {  
    95.      if((a[j]%r)/tem>(a[j+1]%r)/tem)  
    96.      {  
    97.       exchange(a[j],a[j+1]);  
    98.         
    99.      }  
    100.     }  
    101.    listout(a,n);  
    102.     
    103.    tem *=10;  
    104.    r *=10;  
    105.    
    106.   }  
    107.   
    108. }  
    109. //快速排序  
    110. void SortNum::quickSort(int a[],int n,int left,int right)  
    111. {  
    112.       int i,j;  
    113.   i=left;  
    114.   j=right;  
    115.   int middle=a[(left+right)/2];  
    116.   do  
    117.   {  
    118.    while(a[i]<middle && i<right)//在左右找出一对，然后交换  
    119.     i++;                        //问1：没成对怎么办？只有一个比中间小的，怎么弄？  
    120.   
    121.                                 //知道的吼！！  
    122.    while(a[j]>middle && j>left)  
    123.     j--;  
    124.    if(i<=j)  
    125.    {  
    126.     exchange(a[i],a[j]);  
    127.     i++;  
    128.     j--;  
    129.     listout(a,n);//输出有些问题，递归调用中也输出？？？  
    130.       
    131.    }  
    132.   }while(i<=j);  
    133.      
    134.   if(left<j)//递归调用排序左右两边，级级深入  
    135.    quickSort(a,n,left,j);  
    136.   if(right>i)  
    137.    quickSort(a,n,i,right);  
    138. }  
    139. //归并排序  
    140. //二路归并   问题～～无法输出详细过程  
    141. void SortNum::Merge(int *SR, int *TR, int i, int m, int n){  
    142.   
    143.     // 将有序的SR[i..m]和SR[m+1..n]归并为有序的TR[i..n]  
    144.   
    145.     int j = m+1;  
    146.   
    147.     int k = i;  
    148.   
    149.     for(; i<=m && j<=n; ++k){// 将SR中记录按关键字从小到大地复制到TR中  
    150.   
    151.         if (SR[i]<=SR[j]){  
    152.   
    153.             TR[k] = SR[i++];  
    154.   
    155.         }else{  
    156.   
    157.             TR[k] = SR[j++];  
    158.   
    159.         }  
    160.   
    161.     }  
    162.   
    163.     while (i<=m) TR[k++] = SR[i++];   // 将剩余的 SR[i..m] 复制到TR  
    164.   
    165.     while (j<=n) TR[k++] = SR[j++];   // 将剩余的 SR[j..n] 复制到TR  
    166.   
    167. }//Merge  
    168.   
    169. void SortNum::Msort( int *SR, int *TR1, int s, int t ){  
    170.   
    171.     // 对SR[s..t]进行归并排序，排序后的记录存入TR1[s..t]  
    172.   
    173.     if (s==t){  
    174.   
    175.         TR1[s] = SR[s];  
    176.   
    177.     }else {  
    178.   
    179.          
    180.         int TR2[7];//注：若main中数组改这里一定要改～～～～  
    181.         int m = (s+t)/2;   // 将 SR[s..t] 平分为 SR[s..m] 和 SR[m+1..t]  
    182.   
    183.         Msort(SR,TR2,s,m);  // 递归地将 SR[s..m] 归并为有序的 TR2[s..m]  
    184.   
    185.         Msort(SR,TR2,m+1, t); // 递归地将SR[m+1..t]归并为有序的TR2[m+1..t]  
    186.   
    187.         Merge(TR2,TR1,s,m,t); // 将TR2[s..m]和TR2[m+1..t] 归并到 TR1[s..t]  
    188.       Copy(SR,TR1,s,t);  
    189.   
    190.     }// else  
    191.   
    192. } // Msort  
    193. void SortNum::Copy( int *S, int *T, int s, int t )  
    194. {  
    195.     for(int i=s;i<=t;i++)  
    196.   S[i]=T[i];  
    197.     listout(S,7);  
    198. }  
    199.   
    200.    
    201.   
    202.   
    203. void main()  
    204. {  
    205.  int a[7]={81,129,655,543,987,26,794};//问题：数组中了length怎么解决  
    206.  SortNum so;  
    207.  cout <<"原始数据"<<endl;  
    208.  so.listout(a,7);  
    209.  //so.exchange(a[0],a[1]);//测试exchange方法  
    210.  //so.listout(a,7);  
    211.     cout <<"选择排序类型：1.选择，2.冒泡，3.插入，4.基数 5.快速 6.归并"<<endl;  
    212.  int n;  
    213.  cin >>n;  
    214.  int b[7];  
    215.  switch( n)  
    216.  {   
    217.   case 1:so.selectSort(a,7);break;  
    218.   case 2:so.bublbleSort(a,7);break;  
    219.   case 3:so.insertSort(a,7);break;  
    220.   case 4:so.baseSort(a,7);break;  
    221.   case 5:so.quickSort(a,7,0,6);break;  
    222.   case 6:so.Msort(a,b,0,6);break;  
    223.   
    224.  }  
    225.    
    226. }

img_e00999465d1c2c1b02df587a3ec9c13d.jpg
微信公众号： 猿人谷
如果您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】
如果您希望与我交流互动，欢迎关注微信公众号
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。

文章标签：
C++
人工智能
关键词：
C++排序
C++实现
heyonggang0811
目录
相关文章
闻缺陷则喜何志丹
|
人工智能 算法 测试技术
【数学】【排序】【C++算法】3027人员站位的方案数
【数学】【排序】【C++算法】3027人员站位的方案数
闻缺陷则喜何志丹
168 0
蒋星熠Jaxonic
|
5月前
|
C++
基本二叉树与排序二叉树（C++源码）
本程序实现二叉树基本操作与二叉排序树应用。支持前序建树、四种遍历、求深度、叶子数、第K层节点数及查找功能；并实现二叉排序树的构建、中序输出与查找比较次数统计，分析不同插入顺序对树形态和查找效率的影响。
蒋星熠Jaxonic
376 6
RossyYan
|
存储 人工智能 算法
【C++数据结构——内排序】二路归并排序（头歌实践教学平台习题）【合集】
本关任务是实现二路归并算法，即将两个有序数组合并为一个有序数组。主要内容包括： - **任务描述**：实现二路归并算法。 - **相关知识**： - 二路归并算法的基本概念。 - 算法步骤：通过比较两个有序数组的元素，依次将较小的元素放入新数组中。 - 代码示例（以 C++ 为例）。 - 时间复杂度为 O(m+n)，空间复杂度为 O(m+n)。 - **测试说明**：平台会对你编写的代码进行测试，提供输入和输出示例。 - **通关代码**：提供了完整的 C++ 实现代码。 - **测试结果**：展示代码运行后的排序结果。 开始你的任务吧，祝你成功！
RossyYan
420 10
RossyYan
|
搜索推荐 算法 数据处理
【C++数据结构——内排序】希尔排序（头歌实践教学平台习题）【合集】
本文介绍了希尔排序算法的实现及相关知识。主要内容包括： - **任务描述**：实现希尔排序算法。 - **相关知识**： - 排序算法基础概念，如稳定性。 - 插入排序的基本思想和步骤。 - 间隔序列（增量序列）的概念及其在希尔排序中的应用。 - 算法的时间复杂度和空间复杂度分析。 - 代码实现技巧，如循环嵌套和索引计算。 - **测试说明**：提供了测试输入和输出示例，帮助验证代码正确性。 - **我的通关代码**：给出了完整的C++代码实现。 - **测试结果**：展示了代码运行的测试结果。 通过这些内容，读者可以全面了解希尔排序的原理和实现方法。
RossyYan
296 10
RossyYan
|
搜索推荐 C++
【C++数据结构——内排序】快速排序（头歌实践教学平台习题）【合集】
快速排序是一种高效的排序算法，基于分治策略。它的主要思想是通过选择一个基准元素（pivot），将数组划分成两部分。一部分的元素都小于等于基准元素，另一部分的元素都大于等于基准元素。然后对这两部分分别进行排序，最终使整个数组有序。(第一行是元素个数，第二行是待排序的原始关键字数据。本关任务：实现快速排序算法。开始你的任务吧，祝你成功！
RossyYan
335 7
RossyYan
|
存储 算法 搜索推荐
【C++面向对象——群体类和群体数据的组织】实现含排序功能的数组类（头歌实践教学平台习题）【合集】
1. **相关排序和查找算法的原理**：介绍直接插入排序、直接选择排序、冒泡排序和顺序查找的基本原理及其实现代码。 2. **C++ 类与成员函数的定义**：讲解如何定义`Array`类，包括类的声明和实现，以及成员函数的定义与调用。 3. **数组作为类的成员变量的处理**：探讨内存管理和正确访问数组元素的方法，确保在类中正确使用动态分配的数组。 4. **函数参数传递与返回值处理**：解释排序和查找函数的参数传递方式及返回值处理，确保函数功能正确实现。 通过掌握这些知识，可以顺利地将排序和查找算法封装到`Array`类中，并进行测试验证。编程要求是在右侧编辑器补充代码以实现三种排序算法
RossyYan
332 5
好奇的菜鸟
|
C++ 容器
C++之deque容器(构造、赋值、大小、插入与删除、存取、排序)
C++之deque容器(构造、赋值、大小、插入与删除、存取、排序)
好奇的菜鸟
253 1
好奇的菜鸟
|
算法 搜索推荐 C++
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
C++之STL常用算法(遍历、查找、排序、拷贝、替换、算数生成、集合)
好奇的菜鸟
196 0
闻缺陷则喜何志丹
|
算法 测试技术 C#
【模拟】【C++算法】2826. 将三个组排序
【模拟】【C++算法】2826. 将三个组排序
闻缺陷则喜何志丹
122 0
泡沫o0
|
机器学习/深度学习 算法 调度
拓扑排序解析：计算机与数学的交汇点以及C++ 实现
拓扑排序解析：计算机与数学的交汇点以及C++ 实现
泡沫o0
508 0