各种排序算法
1.选择排序法
每循环一次将最值挑出来放在前面,实践复杂度为O(n^2),不稳定排序,其基本的语法如下:
void selectsort(int a[],int n) { int i,j,k,temp; for(i=0;i<n-1;i++) { k=i; for(j=i+1;j<n;j++) if(a[k]>a[j]) k=j; //寻找本次的最小元素的下标 if(k!=i) { temp=a[i]; a[i]=a[k]; a[k]=temp; } } }
2.冒泡排序法
每循环一次将最值冒到尾部,时间复杂度为O(n^2),稳定排序,其基本的语法如下:
void Bubblesort(int a[],int n) { int i,j,temp,flag; for(i=0;i<n;i++) { flag=0; for(j=0;j<n-i-1;j++) { if(a[j]>a[j+1]) { temp=a[j]; a[j]=a[j+1]; a[j+1]=temp; flag=1; } } if(!flag) break; } }
3.C++STL之sort排序
sort排序可以捆绑结构体一起使用,求出原来的序号和排序后的序号,时间复杂度为n*log2(n),其基本的语法如下:
sort(a,a+n,cmp);
4.快速排序
快速排序是快速排序的改进版本,以一个数为基数两边进行排序,时间复杂度为n*log2(n),不稳定排序。其基本的语法如下:
void Quicksort(int a[],int x,int y) { int i=x,j=y,temp; int k=a[x]; //以k为基数 if(i>=j) return; while(i<j) { while(i<j&&a[j]>=k) //从右向左找到第一个比k小的 j--; temp=a[j]; a[j]=a[i]; a[i]=temp; while(i<j&&a[i]<k) //从左向右找到第一个比k大的 i++; temp=a[i]; a[i]=a[j]; a[j]=temp; } Quicksort(a,x,i-1); Quicksort(a,i+1,y); return; }
5.归并排序
归并排序利用分治策略,将问题分成一些小问题,用递归实现,其时间复杂度是O(n*log2n)(最好情况和最坏情况都是这个复杂度),是一种稳定排序。,其基本的语法如下:
void Merge(int a[],int left,int mid,int right) //归并数组,注意此函数要写在排序函数之前 { int temp[right-left+1]; //复制数组 for(int i=left;i<=right;i++) temp[i-left]=a[i]; int i=left,j=mid+1; for(int k=left;k<=right;k++) { if(i>mid) //判断i是否有效 { a[k]=temp[j-left]; j++; } else if(j>right) //判断j是否有效 { a[k]=temp[i-left]; i++; } else if(temp[i-left]<temp[j-left]) //开始排序 { a[k]=temp[i-left]; i++; } else //排序 { a[k]=temp[j-left]; j++; } } } void Mergesort(int a[],int left,int right) //归并排序 { if(left>=right) return; int mid=(right+left)/2; Mergesort(a,left,mid); //分组 Mergesort(a,mid+1,right); //分组 Merge(a,left,mid,right); //归并 }
好像实际上掌握sort排序和归并就够了, 其他的个人感觉用处不大qwq
相关推荐
数据与算法之美 2020-07-05
earthhouge 2020-06-25
randy0 2020-11-17
lixiaotao 2020-10-07
美丽的泡沫 2020-09-08
nongfusanquan0 2020-08-18
hang0 2020-08-16
earthhouge 2020-08-15
算法改变人生 2020-07-28
troysps 2020-07-19
Broadview 2020-07-19
chenfei0 2020-07-18
风吹夏天 2020-07-07
yangjingdong00 2020-07-05
shawsun 2020-07-04
数据与算法之美 2020-07-04
要知道时间复杂度只是描述一个增长趋势,复杂度为O的排序算法执行时间不一定比复杂度为O长,因为在计算O时省略了系数、常数、低阶。实际上,在对小规模数据进行排序时,n2的值实际比 knlogn+c还要小。
Evankaka 2020-07-04
田有朋 2020-06-28