网站地图 | RSS订阅 老铁博客 - 上海SEO优化|上海网站建设|蜘蛛池出租|站群代搭建
你的位置:首页 » 前端脚本 » 正文

排序算法总结,c++排序算法总结

2020-3-7 15:5:29 | 作者:老铁SEO | 0个评论 | 人浏览

  一、低级排序算法


  1.选择排序


  (1)排序过程


  给定一个数值集合,循环遍历集合,每次遍历从集合中选择出最小或最大的放入集合的开头或结尾的位置,下次循环从剩余的元素集合中遍历找出最小的并如上操作,最后直至所有原集合元素都遍历完毕,排序结束。


  (2)实现代码


  //选择排序法


  template


  voidSort::SelectSort(T*array,intsize)


  {


  intminIndex;


  for(inti=0;i<size;i++)


  {


  minIndex=i;


  for(intj=i+1;j<size;j++)


  {


  if(array[minIndex]>array[j])


  {


  minIndex=j;


  }


  }


  if(minIndex!=i)


  {


  Swap(array,i,minIndex);


  }


  }


  }


  (3)分析总结


  选择排序时间复杂度比较高,达到了O(n^2),每次选择都要遍历一遍无序区间。选择排序对一类重要的元素序列具有较好的效率,就是元素规模很大,而排序码却比较小的序列。另外要说明的是选择排序是一种不稳定的排序方法。


  2.冒泡排序


  (1)排序过程


  冒泡排序的过程形如其名,就是依次比较相邻两个元素,优先级高(或大或小)的元素向后移动,直至到达序列末尾,无序区间就会相应地缩小。下一次再从无序区间进行冒泡操作,依此循环直至无序区间为1,排序结束。


  (2)实现代码


  //冒泡排序法


  template


  voidSort::BubbleSort(T*array,intsize)


  {


  for(inti=0;i<size;i++)


  {


  for(intj=1;j<size-i;j++)


  {


  if(array[j]<array[j-1])


  {


  Swap(array,j,j-1);


  }


  }


  }


  }


  (3)分析总结


  冒泡排序的时间复杂度也比较高,达到O(n^2),每次遍历无序区间都将优先级高的元素移动到无序区间的末尾。冒泡排序是一种稳定的排序方式。


  二、高级排序算法


  (1)排序过程


  归并排序的原理比较简单,也是基于分治思想的。它将待排序的元素序列分成两个长度相等的子序列,然后为每一个子序列排序,然后再将它们合并成一个序列。


  (2)实现代码


  //归并排序


  template


  voidSort::MergeSort(T*array,intleft,intright)


  {


  if(left<right)


  {


  intmid=(left+right)/2;


  MergeSort(array,left,mid);


  MergeSort(array,mid+1,right);


  Merge(array,left,mid,right);


  }


  }


  //合并两个已排好序的子链


  template


  voidSort::Merge(T*array,intleft,intmid,intright)


  {


  T*temp=newT[right-left+1];


  inti=left,j=mid+1,m=0;


  while(i<=mid&&j<=right)


  {


  if(array[i]<array[j])


  {


  temp[m++]=array[i++];


  }


  else


  {


  temp[m++]=array[j++];


  }


  }


  while(i<=mid)


  {


  temp[m++]=array[i++];


  }


  while(j<=right)


  {


  temp[m++]=array[j++];


  }


  for(intn=left,m=0;n<=right;n++,m++)


  {


  array[n]=temp[m];


  }


  deletetemp;


  }


  (3)分析总结


  归并排序最好、最差和平均时间复杂度都是O(nlogn),是一种稳定的排序算法。


  c++排序算法总结


  选择排序


  #include


  usingnamespacestd;


  voidselect_sort(intarr[],intnum);


  voidoutput_array(intarr[],intnum);


  intmain()


  {


  inta[10];


  for(inti=0;i<10;i++)


  {


  cin>>a[i];


  }


  select_sort(a,10);


  output_array(a,10);


  return0;


  }


  voidselect_sort(intarray[],intn)//形参array是数组名


  {


  inti,j,k,t;


  for(i=0;i{


  k=i;//先设第i个就为最小


  for(j=i+1;jif(array[j]k=j;//通过循环,得到k为最小


  t=array[k];//交换a[i]和a[k]


  array[k]=array[i];


  array[i]=t;


  }


  return;


  }


  voidoutput_array(intarr[],intnum)


  {


  inti;


  for(i=0;i{


  cout<cout<}


  return;


  }<


  >


  2.冒泡排序


  #include


  intmain()


  {


  inti,j,a[10],t;


  for(i=0;i<10;i++)


  scanf("%d",&a[i]);


  for(i=0;i<10;i++)


  for(j=i+1;j<10;j++)


  if(a[i]>a[j])


  {


  t=a[j];


  a[j]=a[i];


  a[i]=t;


  }


  for(i=0;i<10;i++)


  printf("%d",a[i]);


  return0;


  }<


  >


  3.堆排序


  #include


  usingnamespacestd;


  voidpaidui(inta[20],inti,intm)


  {


  intk,t;


  t=a[i];


  k=2*i+1;


  while(k{


  if((kk++;


  if(t{


  a[i]=a[k];


  i=k;


  k=2*i+1;


  }


  elsebreak;


  }


  a[i]=t;


  }


  voidduipai(inta[20],intn)


  {


  inti,k;


  for(i=n/2-1;i>=0;i--)


  paidui(a,i,n);


  for(i=n-1;i>=1;i--)


  {


  k=a[0];


  a[0]=a[i];


  a[i]=k;


  paidui(a,0,i);


  }}


  intmain()


  {


  inta[10],i;


  for(i=0;i<10;i++)


  cin>>a[i];


  duipai(a,10);


  for(i=0;i<10;i++)


  cout<}<


  >


  4.快速排序


  #include


  usingnamespacestd;


  voidQuicksort(inta[],intlow,inthigh)


  {


  if(low>=high)


  {


  return;


  }


  intfirst=low;


  intlast=high;


  intkey=a[first];


  while(first{


  while(first=key)


  --last;


  a[first]=a[last];


  while(first++first;


  a[last]=a[first];


  }


  a[first]=key;


  Quicksort(a,low,first-1);


  Quicksort(a,last+1,high);


  }


  intmain()


  {


  inti,a[100],x,n=0;


  while(cin>>x)


  {


  a[n]=x;


  n++;


  }


  n--;


  Quicksort(a,0,n);


  for(i=0;i<=n;i++)


  cout<cout<return0;


  }<


  >


  5.基数排序


  #include


  #include


  intmain(){


  intdata[10]={73,22,93,43,55,14,82,65,39,81};//对十个数进行排序


  inttemp[10][10]={0};//构造一个临时二维数组,其值为0


  intorder[10]={0};//构造一维数组,其值为0


  inti,j,k,n,lsd;


  k=0;n=1;


  for(i=0;i<10;i++)printf("%d",data[i]);//在排序前,对这10个数打印一遍


  putchar('\n');


  while(n<=10){


  for(i=0;i<10;i++){


  lsd=((data[i]/n)%10);//lsd先对个位取余,然后再对十位取余,注意循环


  temp[lsd][order[lsd]]=data[i];//temp[3][0]=73,temp[2][0]=22,temp[3][1]=93,temp[3][2]=43,⋯⋯


  order[lsd]++;//需要区分的是lsd和order[lsd],这两个不是一样的概念嗷


  }


  printf("\n重新排列:");


  for(i=0;i<10;i++){


  if(order[i]!=0)


  for(j=0;j


  data[k]=temp[i][j];


  printf("%d",data[k]);


  k++;


  }


  order[i]=0;


  }


  n*=10;//第二次用十位


  k=0;


  }


  putchar('\n');


  printf("\n排序后:");


  for(i=0;i<10;i++)printf("%d",data[i]);


  return0;


  }<


  >


  6.希尔排序


  #include


  usingnamespacestd;


  voidshell_sort(inta[],intn);


  intmain()


  {


  intn,a[10000];


  cin>>n;


  for(inty=0;ycin>>a[y];


  shell_sort(a,n);


  for(inti=0;icout<cout<}


  voidshell_sort(inta[],intn)


  {


  intgap,k,temp;//定义增量;


  for(gap=3;gap>0;gap--)//设置初始增量,递减;


  {


  for(inti=0;i{


  for(intj=i+gap;j{


  if(a[j]{


  temp=a[j];


  k=j-gap;


  while(k>=0&&a[k]>temp)


  {


  a[k+gap]=a[k];


  k=k-gap;


  }


  a[k+gap]=temp;


  }


  }


  }


  }


  }<


  >


  7.归并排序


  #include


  usingnamespacestd;


  voidMergeSort(intp[],ints,intm,intt)


  {


  intq[100];//q[100]用来存放排好的序列


  inti=s;


  intj=m+1;


  intk=s;


  while(i<=m&&j<=t)


  {


  if(p[i]<=p[j])


  q[k++]=p[i++];


  else


  q[k++]=p[j++];


  }


  if(i<=m)


  while(i<=m)


  q[k++]=p[i++];


  elsewhile(j<=t)


  q[k++]=p[j++];


  for(intn=s;n<=t;n++)


  p[n]=q[n];


  }


  voidMerge(intp[],ints,intt)


  {


  if(s{


  intm=(s+t)/2;//将数组分成两半


  Merge(p,s,m);//递归拆分左数组


  Merge(p,m+1,t);//递归拆分右数组


  MergeSort(p,s,m,t);//合并数组


  }


  }


  intmain()


  {


  intn;


  intp[100];


  cin>>n;


  for(inti=0;icin>>p[i];


  Merge(p,0,n-1);


  for(intj=0;jcout<cout<return0;


  }<


  >


  排序方法基本就这些,还有双向冒泡这种拓展的排序方法,还有直接排序如桶排序


  排序算法总结python


  排序算法总结时间复杂度


  排序算法总结及面试题


  一、冒泡排序


  [java]viewplaincopy


  packagesort.bubble;


  importjava.util.Random;


  /**


  *依次比较相邻的两个数,将小数放在前面,大数放在后面


  *冒泡排序,具有稳定性


  *时间复杂度为O(n^2)


  *不及堆排序,快速排序O(nlogn,底数为2)


  *@authorliangge


  *


  */


  publicclassMain{


  publicstaticvoidmain(String[]args){


  Randomran=newRandom();


  int[]sort=newint[10];


  for(inti=0;i<10;i++){


  sort[i]=ran.nextInt(50);


  }


  System.out.print("排序前的数组为");


  for(inti:sort){


  System.out.print(i+"");


  }


  buddleSort(sort);


  System.out.println();


  System.out.print("排序后的数组为");


  for(inti:sort){


  System.out.print(i+"");


  }


  }


  /**


  *冒泡排序


  *@paramsort


  */


  privatestaticvoidbuddleSort(int[]sort){


  for(inti=1;ifor(intj=0;jif(sort[j]>sort[j+1]){


  inttemp=sort[j+1];


  sort[j+1]=sort[j];


  sort[j]=temp;


  }


  }


  }


  }


  }


  二、选择排序


  [java]viewplaincopy


  packagesort.select;


  importjava.util.Random;


  /**


  *选择排序


  *每一趟从待排序的数据元素中选出最小(或最大)的一个元素,


  *顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。


  *选择排序是不稳定的排序方法。


  *@authorliangge


  *


  */


  publicclassMain{


  publicstaticvoidmain(String[]args){


  Randomran=newRandom();


  int[]sort=newint[10];


  for(inti=0;i<10;i++){


  sort[i]=ran.nextInt(50);


  }


  System.out.print("排序前的数组为");


  for(inti:sort){


  System.out.print(i+"");


  }


  selectSort(sort);


  System.out.println();


  System.out.print("排序后的数组为");


  for(inti:sort){


  System.out.print(i+"");


  }


  }


  /**


  *选择排序


  *@paramsort


  */


  privatestaticvoidselectSort(int[]sort){


  for(inti=0;ifor(intj=i+1;jif(sort[j]inttemp=sort[j];


  sort[j]=sort[i];


  sort[i]=temp;


  }


  }


  }


  }


  }


  三、快速排序


  [java]viewplaincopy


  packagesort.quick;


  /**


  *快速排序通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,


  *然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。


  *@authorliangge


  *


  */


  publicclassMain{


  publicstaticvoidmain(String[]args){


  int[]sort={54,31,89,33,66,12,68,20};


  System.out.print("排序前的数组为:");


  for(intdata:sort){


  System.out.print(data+"");


  }


  System.out.println();


  quickSort(sort,0,sort.length-1);


  System.out.print("排序后的数组为:");


  for(intdata:sort){


  System.out.print(data+"");


  }


  }


  /**


  *快速排序


  *@paramsort要排序的数组


  *@paramstart排序的开始座标


  *@paramend排序的结束座标


  */


  publicstaticvoidquickSort(int[]sort,intstart,intend){


  //设置关键数据key为要排序数组的第一个元素,


  //即第一趟排序后,key右边的数全部比key大,key左边的数全部比key小


  intkey=sort[start];


  //设置数组左边的索引,往右移动判断比key大的数


  inti=start;


  //设置数组右边的索引,往左移动判断比key小的数


  intj=end;


  //如果左边索引比右边索引小,则还有数据没有排序


  while(i<j){


  while(sort[j]>key&&j>start){


  j--;


  }


  while(sort[i]<key&&i<end){


  i++;


  }


  if(i<j){


  inttemp=sort[i];


  sort[i]=sort[j];


  sort[j]=temp;


  }


  }


  //如果左边索引比右边索引要大,说明第一次排序完成,将sort[j]与key对换,


  //即保持了key左边的数比key小,key右边的数比key大


  if(i>j){


  inttemp=sort[j];


  sort[j]=sort[start];


  sort[start]=temp;


  }


  //递归调用


  if(j>start&&j<end){


  quickSort(sort,start,j-1);


  quickSort(sort,j+1,end);


  }


  }


  }


  [java]viewplaincopy


  /**


  *快速排序


  *


  *@parama


  *@paramlow


  *@paramhigh


  *voidTest


  */


  publicstaticvoidkuaisuSort(int[]a,intlow,inthigh)


  {


  if(low>=high)


  {


  return;


  }


  if((high-low)==1)


  {


  if(a[low]>a[high])


  {


  swap(a,low,high);


  return;


  }


  }


  intkey=a[low];


  intleft=low+1;


  intright=high;


  while(left<right)


  {


  while(left<right&&left<=high)//左边向右


  {


  if(a[left]>=key)


  {


  break;


  }


  left++;


  }


  while(right>=left&&right>low)


  {


  if(a[right]<=key)


  {


  break;


  }


  right--;


  }


  if(left<right)


  {


  swap(a,left,right);


  }


  }


  swap(a,low,right);


  kuaisuSort(a,low,right);


  kuaisuSort(a,right+1,high);


  }


  四、插入排序


  [java]viewplaincopy


  packagesort.insert;


  /**


  *直接插入排序


  *将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据


  *算法适用于少量数据的排序,时间复杂度为O(n^2)。是稳定的排序方法。


  */


  importjava.util.Random;


  publicclassDirectMain{


  publicstaticvoidmain(String[]args){


  Randomran=newRandom();


  int[]sort=newint[10];


  for(inti=0;i<10;i++){


  sort[i]=ran.nextInt(50);


  }


  System.out.print("排序前的数组为");


  for(inti:sort){


  System.out.print(i+"");


  }


  directInsertSort(sort);


  System.out.println();


  System.out.print("排序后的数组为");


  for(inti:sort){


  System.out.print(i+"");


  }


  }


  /**


  *直接插入排序


  *


  *@paramsort


  */


  privatestaticvoiddirectInsertSort(int[]sort){


  for(inti=1;i<sort.length;i++){


  intindex=i-1;


  inttemp=sort[i];


  while(index>=0&&sort[index]>temp){


  sort[index+1]=sort[index];


  index--;


  }


  sort[index+1]=temp;


  }


  }


  }


  顺便添加一份,差不多的


  [java]viewplaincopy


  publicstaticvoidcharuSort(int[]a)


  {


  intlen=a.length;


  for(inti=1;i<len;i++)


  {


  intj;


  inttemp=a[i];


  for(j=i;j>0;j--)//遍历i之前的数字


  {


  //如果之前的数字大于后面的数字,则把大的值赋到后面


  if(a[j-1]>temp)


  {


  a[j]=a[j-1];


  }else


  {


  break;


  }


  }


  a[j]=temp;


  }


  }


  把上面整合起来的一份写法:


  [java]viewplaincopy


  /**


  *插入排序:


  *


  */


  publicclassInsertSort{


  publicvoidsort(int[]data){


  for(inti=1;i<data.length;i++){


  for(intj=i;(j>0)&&(data[j]<data[j-1]);j--){


  swap(data,j,j-1);


  }


  }


  }


  privatevoidswap(int[]data,inti,intj){


  inttemp=data[i];


  data[i]=data[j];


  data[j]=temp;


  }


  }


  五、顺便贴个二分搜索法


  [java]viewplaincopy


  packagesearch.binary;


  publicclassMain{


  publicstaticvoidmain(String[]args){


  int[]sort={1,2,3,4,5,6,7,8,9,10};


  intmask=binarySearch(sort,6);


  System.out.println(mask);


  }


  /**


  *二分搜索法,返回座标,不存在返回-1


  *@paramsort


  *@return


  */


  privatestaticintbinarySearch(int[]sort,intdata){


  if(datasort[sort.length-1]){


  return-1;


  }


  intbegin=0;


  intend=sort.length;


  intmid=(begin+end)/2;


  while(begin<=end){


  mid=(begin+end)/2;


  if(data>sort[mid]){


  begin=mid+1;


  }elseif(data<sort[mid]){


  end=mid-1;


  }else{


  returnmid;


  }


  }


  return-1;


  }


  }

  • 本文来自: 老铁博客,转载请保留出处!欢迎发表您的评论
  • 相关标签:
  • 已有0位网友发表了一针见血的评论,你还等什么?

    必填

    选填

    记住我,下次回复时不用重新输入个人信息

    必填,不填不让过哦,嘻嘻。

    ◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

    相关推荐