常见排序算法（比较排序）及比较

2025-01-03 技术教程

#include<iostream>usingnamespacestd;#include<assert.h>//稳定性：指两个相同数排序后位置是否变化//冒泡排序思想：相邻两数据比较交换，外层循环控制次数，内层比较//voidBubbleSort(int*a,size_tlen)//{//assert(a);//for(size_ti=0;i<len-1;++i)//{//相邻位置数据进行比较，每趟排序都会排出一个最大或最小数//for(size_tj=0;j<len-i-1;++j)//{//if(a[j]>a[j+1])//{//swap(a[j],a[j+1]);//}//}//}//}////鸡尾酒排序思想：即就是双向冒泡排序，一趟排序就可以找到一个最大的和最小元素voidcooktail_sort(int*arr,size_tsize){assert(arr);inttail=size-1;inti,j;for(i=0;i<tail;++i){for(intj=tail;j>i;--j){if(arr[j]<arr[j-1]){swap(arr[j],arr[j-1]);}}++i;for(j=i;j<tail;++j){if(arr[j]>arr[j+1])swap(arr[j],arr[j+1]);}--tail;}}//思想：将当前位置的下一个数据插入到前边以有序的块中，再将该数与前边有序的数据逐一比较。//每插入一个该位置以前的数据都已有序//voidInsertSort(int*a,size_tlen)//插入排序//{//assert(a);//for(size_ti=0;i<len-1;++i)//当i=len-1时，tmp访问的位置越界//{//intend=i;//inttmp=a[end+1];//while(end>=0&&a[end]>tmp)//最后一次进去end=0位置要比//{//a[end+1]=a[end];//--end;//}//a[end+1]=tmp;//}//}//思想：将一个数组分成两半，再将每一半分半，递归类推，当分出来的只有一个数据时，可认为该小组组内已经有序，然后合并相邻小组，即先递归分解数列，在合并数列voidMergesort(int*arr,intbegin1,intend1,intbegin2,intend2){//assert(arr);//if(begin1>=end1||begin2>=end2)//return;//intone=end1-begin1;//inttwo=end2-begin2;//int*L=newint[one];//开辟两个数组，一个保存前半部分，一个保存后半部分//int*R=newint[two];//inti=0,j=0;//for(;i<one;++i)//{//L[i]=arr[begin1+i];//}//for(i=0;i<two;++i)//{//R[i]=arr[begin2+i];//}//intindex=begin1;//for(i=0,j=0;index<end2&&i<one&&j<two;++index)//{//if(L[i]<=R[j])//{//arr[index]=L[i];//++i;//}//else//{//arr[index]=R[j];//++j;//}//}//if(i<one)//如果一个子序已排完，将剩另一个余的数据直接连接到后边//{//for(intk=i;k<one;++k)//arr[index++]=L[k];//}//else//{//for(intk=j;k<two;++k)//arr[index++]=R[k];//}//delete[]L;//delete[]R;}//void_merge_sort(int*arr,intbegin,intend)//{//assert(arr);//if(begin+1<end)//{//intmid=begin+((end-begin)>>1);//_merge_sort(arr,begin,mid);//_merge_sort(arr,mid,end);//Mergesort(arr,begin,mid,mid,end);////memcpy(src+begin,dst+begin,(end-begin)*sizeof(int));//}//else//return;//}//两个同样数组，将源数组按序放入目标数组中voidMergesort(int*src,int*dst,intbegin1,intend1,intbegin2,intend2){assert(src&&dst);size_tindex=begin1;//两个同样大小的数组while(begin1<end1&&begin2<end2){if(src[begin1]<src[begin2]){dst[index++]=src[begin1++];}else{dst[index++]=src[begin2++];}}if(begin1<end1){while(begin1<end1){dst[index++]=src[begin1++];}}else{while(begin2<end2){dst[index++]=src[begin2++];}}}void_merge_sort(int*src,int*dst,intbegin,intend){assert(src&&dst);if(begin+1<end){intmid=begin+((end-begin)>>1);_merge_sort(src,dst,begin,mid);_merge_sort(src,dst,mid,end);Mergesort(src,dst,begin,mid,mid,end);memcpy(src+begin,dst+begin,(end-begin)*sizeof(int));}elsereturn;}void_Merge_sort(int*src,size_tsize){int*dst=newint[size];_merge_sort(src,dst,0,size);delete[]dst;}//思想：采用分治法思想，选定一个基数，通过一趟排序将要排序的数组一分为二，其中基数前的数据都比它小，基数后的数据都比它大，然后在将这两部分数据分别进行快排intQSort(int*a,intleft,intright)//快速排序{assert(a);if(left>=right)returnleft;intkey=a[right];intbegin=left;intend=right-1;while(begin<end){while(begin<end&&a[begin]<=key)begin++;while(begin<end&&a[end]>key)end--;if(begin<end)swap(a[begin],a[end]);}if(a[end]>=a[right])swap(a[end],a[right]);returnend;}//voidQuiSort(int*a,intleft,intright)//挖坑法//{//assert(a);//if(right<=left)//return;//inttmp=a[left];//intbegin=left;//intend=right;//while(begin<end)//{//while(begin<end&&a[end]>=tmp)//end--;//if(begin<end)//{//a[begin++]=a[end];//}//while(begin<end&&a[begin]<=tmp)//begin++;//if(begin<end)//{//a[end--]=a[begin];//}//}//a[begin]=tmp;//QuiSort(a,left,begin-1);//QuiSort(a,begin+1,right);//}voidQuickSort(int*a,intleft,intright){assert(a);if(left<right){intmid=QSort(a,left,right);QuickSort(a,left,mid-1);QuickSort(a,mid+1,right);}}//思想：第一次查找最小元素所在位置的下标，与第一个元素交换，之后查找次小元素下标，与第二个元素交换，以此类推//voidSelectSort(int*a,size_tlen)//选择排序//{//assert(a);//size_tmin_index;//for(size_ti=0;i<len;++i)//{//min_index=i;//for(size_tj=i+1;j<len;++j)//{//if(a[min_index]>=a[j])//{//min_index=j;//找最小元素所在的下标//}//}//swap(a[min_index],a[i]);//让最小元素位于第i个位置//}//}//思想：将数组按某个增量gap分成若干组，每组中记录的下标相差gap，对每组中全部元素进行排序//，然后用一个较小增量再进行上述循环排序，当增量减到1时，整个要排序的数被分成单个组，排序完成voidShell_sort(int*a,size_tsize){assert(a);intgap=size/3+1;while(1){for(inti=0;i<size-gap;++i){intend=i;inttmp=a[end+gap];while((a[end]>tmp)&&end>=0){a[end+gap]=a[end];end-=gap;}a[end+gap]=tmp;}if(gap==1)break;gap=gap/3+1;//保证gap最后为1时能执行}}voidTestSelectSort(){inta[10]={9,1,3,4,8,6,0,2,5,0};intlen=sizeof(a)/sizeof(a[0]);cout<<"before:";for(inti=0;i<len;++i){cout<<a[i]<<"";}cout<<endl;Shell_sort(a,len);//QuickSort(a,0,9);//SelectSort(a,10);cout<<"after:";for(inti=0;i<len;++i){cout<<a[i]<<"";}cout<<endl;}voidTestMergeSort(){inta[10]={9,1,3,4,8,6,7,2,5,0};intlen=sizeof(a)/sizeof(a[0]);cout<<"before:";for(inti=0;i<len;++i){cout<<a[i]<<"";}cout<<endl;//_merge_sort(a,0,len);_Merge_sort(a,len);cout<<"after:";for(inti=0;i<len;++i){cout<<a[i]<<"";}cout<<endl;}//堆排序思想：先建成一个大堆或小堆，堆顶元素是最大（最小），让堆顶元素与最后一个元素交换，数组长度-1，然后向下调整一次，重复上述循环//template<classT>//classHeap//{//public://Heap(T*a,size_tsize)//{//for(size_ti=0;i<size;++i)//{//_array.push_back(a[i]);//}//for(inti=(_array.size()-2)/2;i>=0;--i)//{//AdjustDown(i,_array.size());//}//}////voidAdjustDown(introot,intsize)//{//size_tlchild=2*root+1;//while(lchild<size)//{//if((lchild+1<size)&&_array[lchild+1]<_array[lchild])//{//lchild++;//}//if(_array[lchild]<_array[root])//{//swap(_array[lchild],_array[root]);//root=lchild;//lchild=2*root+1;//}//else//break;//}//}////voidAdjustUp(size_tchild)//{//size_troot=(child-1)/2;//while(child>0)//若root和child为size_t型，永远都不会小于0，因此不能用它为循环条件//{//if(_array[child]<_array[root])//{//swap(_array[child],_array[root]);//child=root;//root=(child-1)/2;//}//else//break;//}//}////voidpush_elem(constT&x)//{//_array.push_back(x);//AdjustUp(_array.size()-1);//}////voidPop_elem()//{//swap(_array[0],_array[(_array.size()-1]));//_array.pop_back();//将堆顶元素与最后一个元素交换并删除，再进行向下调整//AdjustDown(0);//}////voidHeap_Sort()//{//intsize=_array.size();//while(size>0)//{//swap(_array[0],_array[size-1]);//cout<<_array[size-1]<<"";////_array.pop_back();//AdjustDown(0,size-1);//--size;//}//}//voidDisplay()//{//cout<<"heapis:";//for(inti=0;i<_array.size();++i)//{//cout<<_array[i]<<"";//}//cout<<endl;//}//protected://vector<T>_array;////};//

算法的适用场景及比较：

比较排序：（1）插入（直接插入、希尔排序）、（2）选择（选择排序、堆排序）、（3）交换（冒泡排序、快排）（4）外排序（归并）

1)时间复杂度：

平均性能为O(N^2):插入、选择、冒泡

数据规模小时:直接插入排序较好

数据规模大时：冒泡排序时间代价最高

平均性能为O(NlgN)：堆、快速、归并

数据规模大时：适用堆排序（例：在一千万个数中找最小的前100个数）

数据规模小时：快速排序较好，当小到一定区间使用插入排序

希尔排序平均时间复杂度为O(N^1.3)

稳定性指的是两个相同的数排序后位置是否变化，若无变化则稳定

2).稳定性分析：