排序算法总结 比眉伴天荒 2022-05-18 09:36 147阅读 0赞 # 冒泡排序 # 时间复杂度为O(n2),最好情况下为O(n),空间复杂度为O(1)。稳定的 冒泡排序总结: void swap(int &a,int &b) { int temp=a; a=b; b=temp; } void buble_sort1(int A[],int n) { for(int i=0;i<n-1;++i) { for(int j=i+1;j<n;j++) { if(A[i]>A[j]) swap(A[i],A[j]); } } } //正宗的冒泡排序实现版本。 //对于n个数来说,总共需要经过n-1次扫描可以使其有序,一趟扫描使一个元素归位 void buble_sort2(int A[],int n) { for(int i=n-1;i>0;--i) { for(int j=0;j<i;++j) { if(A[j]>A[j+1]) //不断的比较相邻的元素,一趟扫描会使得最大位置的元素归位置 swap(A[j],A[j+1]); } } } //对于版本2的改进 如果原序列中后一段是顺序的即不用便利 增加一个flag来区分 void buble_sort3(int A[],int n) { bool flag=false; for(int i=n-1;i>0&&flag;--i) //flag=true 说明当前待排序的部分已经是有序的,不用在进行扫描 { flag=true; for(int j=0;j<i;++j) { if(A[j]>A[j+1]) { swap(A[j],A[j+1]); flag=false; } } } } # 归并排序 # 时间复杂度为O(nlogn),空间复杂度为O(n)。稳定的 归并排序总结: void merge(vector<int>&vec,int lo,int mid,int hi) { vector<int> temp=vec; int i=lo; int j=mid+1; int k=lo; while(i<mid&&j<hi) { if(temp[i]<=temp[j]) vec[k++]=temp[i++]; else vec[k++]=temp[j++]; } while(i<=mid) { vec[k++]=temp[i++]; } while(j<=hi) { vec[k++]=temp[i++]; } } void mergesort(vector<int> &vec,int lo,int hi) { if(lo<hi) { int mid=hi+(hi-lo)/2; mergesort(vec,lo,mid); mergesort(vec,mid+1,hi); merge(vec,lo,mid,hi); } } # 插入排序 # 最好情况下为O(n),最坏以及平均情况下为O(n^2),空间复杂度为O(1)。是稳定的 将整个序列分成两个部分有序的前缀,和无序的后缀, 通过迭代,反复地将后缀首元素转移至前缀中。 void insertsort(vector<int> &vec) { int i ,j; for(int i=1;i<vec.size();i++) { if(vec[i]<vec[i-1]) { int temp=vec[i];//temp 存放待排序的节点 for(j=i-1;j>=0&&vec[j]>temp;--j) vec[j+1]=vec[j]; //把比temp大的部分向前移动 vec[j+1]=temp; } } } # 选择排序 # 最好情况下为、最坏以及平均情况下为O(n^2),空间复杂度为O(1)。不是稳定的 //选择排序 在要排序的一组数中选择最小的一个与第一个交换,再在后面中选出最小的 与第二个交换,如此迭代下去直到全部有序。 void selectsort(vector<int> &vec) { int temp=0; for(int i=0;i<vec.size()-1;++i) { int min=i;//记录需要放置最小元素的位置 for(int j=i+1;j<vec.size();++j) { if(vec[j]<vec[min]) min=j; } if(min!=i) //此时需要交换 { temp=vec[i]; vec[i]=vec[min]; vec[min]=temp; } } } # 快速排序 # 最坏情况下为O(n^2),最好以及平均情况下为O(nlogn)。空间复杂度为O(1)。 int partition(int lo,int hi,vector<int> &vec) { int temp=vec[lo]; while(lo<hi) { while((lo<hi)&&temp<=vec[hi]) --hi; vec[lo]=vec[hi]; while((lo<hi)&&temp>vec[lo]) ++lo; vec[hi]=vec[lo]; } //退出时lo=hi //基准归位 vec[lo]=temp; return lo; } void quicksort(vector<int> &vec,int lo,int hi) { if(lo<=hi) return; //单元素自然有序 int mi=partition(lo,hi,vec); //选择基准点 quicksort(vec,lo,mi-1); //前缀递归 quicksort(vec,mi+1,hi); //后缀递归 }
还没有评论,来说两句吧...