十大排序算法及C++实现-白红宇的个人博客

十大排序算法及C++实现

发布日期：2021-09-14 15:32:55 浏览次数：14 分类：技术文章

本文共 2434 字，大约阅读时间需要 8 分钟。

算法	平均时间复杂度	最好	最坏	空间复杂度	稳定性
冒泡排序	o(n²)	o(n)	o(n²)	o(1)	稳定
选择排序	o(n²)	o(n²)	o(n²)	o(1)	不稳定
插入排序	o(n²)	o(n)	o(n²)	o(1)	稳定
希尔排序	o(nlogn)	o(nlog²n)	o(nlogn)	o(1)	不稳定
归并排序	o(nlogn)	o(nlogn)	o(nlogn)	o(n)	稳定
快速排序	o(nlogn)	o(nlogn)	o(n²)	o(logn)	不稳定
堆排序	o(nlogn)	o(nlogn)	o(nlogn)	o(1)	不稳定
计数排序	o(n+k)	o(n+k)	o(n+k)	o(k)	稳定
桶排序	o(n+k)	o(n+k)	o(n²)	o(k)	稳定
基数排序	o(n*k)	o(n*k)	o(n*k)	o(n+k)	稳定

什么是排序算法的稳定性？
若排序前数组元素中有相同元素，如两个10，其中10*在10`之前。若排序后相同元素的相对位置保持不变，则称排序算法是稳定的。

排序算法的稳定性有什么用?

冒泡排序：

for(int i=0;i
   
    arr[j+1]) {
   			swap(arr[j],arr[j+1]);			isSort=false;		}	}	if(isSort) break;}

归并排序：

核心思想是分治法，将数组一分为二，排序后再合并。

//合并两个有序数组void merge(vector
   
    arr,vector
    
     tempArr,int start,int mid,int end){
   	//复制要合并的数组	for(int i=start;i<=end;i++) tempArr[i]=arr[i]	//左半部分从left开始，右半部分从right开始	int left=start,right=mid+1;	for(int i=start;i<=end;i++){
   		if(left>mid) arr[i]=tempArr[right++];		else if(right>end) arr[i]=tempArr[left++];		else if(tempArr[right]

arr,vector

tempArr,int start,int end){

if(end<=start) return; int mid=start+(end-start)/2; sort(arr,tempArr,start,mid); sort(arr,tempArr,mid+1,end); merge(arr,tempArr,start,mid,end);}

代码注释

left>mid||tempArr[right]<tempArr[left]第一种情况是左半边数据已经排完了，第二种情况左半边的数据更大；这两种情况下将右半边数据排入。

right>end||tempArr[left]<tempArr[right]第一种情况是右半边数据已经排完了，第二种情况右半边的数据更大；这两种情况下将左半边数据排入。

时间复杂度，merge()是o(n)，分割是o(logn)。相乘。

快速排序：

核心思想也是分治法。

int partition(vector
   
    arr,int start,int end){
   	int pivot=arr[start];	int mark=start;	for(int i=start+1;i<=end;i++){
   		if(arr[i]

arr,int start,int end){

if(end<=start) return; int pivotIdx=partition(arr,start,end); sort(arr,start,pivotIdx-1); //每趟排序之后，基准值pivot都到了它的排序位置。 sort(arr,pivotIdx+1,end);}

最好情况：每次的基准值都平均将数组划分为等长的两部分。o(nlogn)

最坏情况：每次都将数组划分时，只划分出一边。不均衡。o(n²)

堆排序：是一种优先队列。有两种实现方法，最大堆和最小堆。升序用最大堆。

void sink(vector
   
    arr,int index,int n){
   	int leftchild=2*index+1；//左子节点下标	int rightchild=2*index+2;//右子节点下标	int cur=index;	if(leftchild
    
     arr[cur]) cur=leftchild;	if(rightchild
     
      arr[cur]) cur=rightchild;	if(cur!=index){
   		swap(arr[cur],arr[index]);		sink(arr,cur,n);	}}void buildHeap(vector
      
       arr,int n){
   	for(int i=n/2;i>=0;i--)		sink(arr,i,n);}void sort(vector
       
        arr){
   	buildHeap(arr,arr.size());	int n=arr.size();	for(int i=arr.size()-1;i>0;i--){
   		swap(arr[0],arr[i]);//堆顶元素移动到末尾并交换		n--;		sink(arr,0,n);//重新构建堆	}}

转载地址：https://blog.csdn.net/weixin_42490152/article/details/100939013 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！

上一篇：lower_bound()函数与upper_bound()函数

下一篇：网易互娱游戏研发面经及答案：算法编程题

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

发表评论

最新留言

关于作者

推荐文章