Vb教程 Vb.net教程 Vfp教程 C/C++教程 Vc/Vc++教程 Delphi教程 Java教程 Powerbuilder
  杀毒频道 | 短信频道 | 网络电视 | 论文中心 | 学上网 | 学软件 | 网页特效 | 电脑基础 | 论坛  
  NCRE | 软考 | CET | 职称英语 | 司法考试 | 报关员 | 公务员 | CATTI | CPA考试  
  Html教程 | Css教程 | Xml教程 | Asp教程 | Asp.net | Php教程 | Jsp教程 | Linux教程 | QQ技巧  
Photoshop Illustrator ImageReady Maya教程 3D Max教程 Lightscape Coredraw教程 Authorware Autocad教程 Freehand教程
Access教程 Mysql教程 Sql server Oracle教程 Word教程 Excel教程 Powerpoint Frontpage Asp.net源码 Php源代码
Flash教程 Fireworks Dreamweaver C#教程 outlook教程 系统安装 vbscript教程 Javascript Jsp源代码 Asp源代码
您的位置:首页 >> C/C++教程 >> 正文

温故而知新:C++常用排序算法
文章来源:csdn 作者:yuguanglou

选择排序法SelectionSort(int arr[],int n)


  template <typename T>
   void SelectionSort(T arr[],int n)
   {
   int smallIndex;   //表中最小元素的下标
   int pass,j;       //用来扫描子表的下标
   T temp;           //用来交换表元素的临时变量
  
   //pass的范围是0~n-2
   for (pass=0;pass<n-1;pass++)
   {
   //从下标pass开始扫描子表
   smallIndex=pass;
  
   //j遍历整个子表arr[pass+1]到arr[n-1]
   for(j=pass+1;j<n;j++)
  
   //如果找到更小的元素,则将该位置赋值给smallIndex
   if(arr[j]<arr[smallIndex])
   smallIndex=j;
  
   //如果smallIndex和pass不在相同的位置
   //则将子表中的最小项与arr[pass]交换
   if(smallIndex!=pass)
   {
   temp=arr[pass];
   arr[pass]=arr[smallIndex];
   arr[smallIndex]=temp;
   }
   }
   }

  /************************************************************************
   双端选择排序算法:是上面选择排序算法的变种,可以定位每个子表中最小和最大元素
   并把它们分别放在子表的开头和结尾.
   ************************************************************************/
   //双端选择排序算法函数deSelSort()的实现


  template <typename T>
   void deSelSort(T arr[],int n)
   {
   int smallIndex,largeIndex;  //表中最小及最大元素的下标
   int leftPass=0,rightPass=n-1,i,j;     //用来从表左边及右边扫描子表的下标
   T temp;                        //用于交换元素的临时变量

  while (leftPass<=rightPass)
   {
   //从左边及右边开始扫描子表
   smallIndex=leftPass;
   largeIndex=rightPass;
  
   //j和i遍历整个子表arr[LeftPass]~arr[rightPass]
   for (i=leftPass+1;i<rightPass;i++)
   //如果找到更小的元素,则将该位置赋值给smallIndex
   if (arr[i]<arr[smallIndex])
   smallIndex=i;
  
   //如果smallIndex和leftPass不在相同的位置
   //则将子表中的最小项与arr[pass]交换
   if (smallIndex!=leftPass)
   {
   temp=arr[leftPass];
   arr[leftPass]=arr[smallIndex];
   arr[smallIndex]=temp;
   }
  
   for (j=rightPass-1;j>leftPass;j--)
   if(arr[j]>arr[largeIndex])
   largeIndex=j;
  
   if(largeIndex!=rightPass)
   {
   temp=arr[rightPass];
   arr[rightPass]=arr[largeIndex];
   arr[largeIndex]=temp;
   }
  
   //从两头收缩子表
   leftPass++;
   rightPass--;
   }
   }

  //自编冒泡法排序算法函数bubbleSort()的实现


  template <typename T>
   int bubbleSort(T arr[],int n)
   {
   bool exchanged=false; //是否发生交换
   int i,j;              //用于遍历子表的下标
   T temp;               //用于交换元素的临时变量

  //开始遍历过程,以下标j构成子表,共有n-1个子表
   for (j=n-1;j>=0;j--) //j从后往前收缩n-1~0,以构成子表0~n-1,0~n-2,0~n-3..0~1
   {
   exchanged=false;
   for (i=0;i<j;i++) //遍历子表范围0~j
   {
  
   if (arr[i]>arr[i+1])
   {
   temp=arr[i];
   arr[i]=arr[i+1];
   arr[i+1]=temp;
   exchanged=true;
   }
   }
   if (!exchanged) return n-j-1;//如果在一次遍历中没有发生交换,则表示已经
   //排序好,中断遍历过程
   }
   return n-1-j;
   }

  //冒泡法排序一般算法函数bubbleSortEx()的实现


  template <typename T>
   int bubbleSortEx(T arr[],int n)
   {
   int i,pass;              //用于遍历子表的下标
   T temp;               //用于交换元素的临时变量
  
   //开始遍历过程,以下标j构成子表,共有n-1个子表
   for (pass=0;pass<n;pass++) //pass从后往后扩大0~n-1,以构成子表0~n-1,0~n-2,0~n-3..0~1
   {
   for (i=0;i<n-pass;i++) //遍历子表范围0~n-pass
   {  
   if (arr[i]>arr[i+1])
   {
   temp=arr[i];
   arr[i]=arr[i+1];
   arr[i+1]=temp;
   }
   }
   }
   return pass;
   }
  

[返回]

编程语言 web开发 数据库 网络技术 操作系统 服务器 网页设计 图形设计 办公软件 常用软件 学电脑

Copyright© www.bianceng.cn Powered by 编程入门网 All Rights Reserved.
关于本站 | 版权声明 | 联系我们 | 友情链接 |
编程入门网 版权所有