排序算法总结

比眉伴天荒 2022-05-18 09:36 203阅读 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); //后缀递归
    }