八大排序-上次看到这么好的排序博客还是在上次

文章目录

八大排序-上次看到这么好的排序博客还是在上次

本文将用说人话+动图的形式带你搞懂常见排序算法,简要分析复杂度、稳定性等指标,并给出参考代码。最后安利sort()函数的使用。

选择排序


每次选择后面最小的元素放在前面。
八大排序-上次看到这么好的排序博客还是在上次

  • 时间复杂度 O ( n 2 ) O(n^2) O(n2)
  • 稳定性:不稳定
    如2 2 1,第一趟选出最小的1后交换得到1 2 2,两个2相对位置改变。

稳定性:就是(关键字/元素值)相同的元素排序后的相对位置是否改变。

  • 排序趟数是否与原序列有关:无关
    无论升序乱序,选择排序每趟都要遍历到最后一个元素,才能确保选出的元素是最小的。
#include<bits/stdc++.h>
using namespace std;
void selection(int a[],int n){
	for(int i=0;i<n;i++){
		int min=i;  //记录最小元素
		for(int j=i+1;j<n;j++){  //找出后面最小元素
			if(a[j]<a[min])
				min=j;
		}
		swap(a[i],a[min]);  //交换
	}
}
int main(){
	int a[5]={3,5,1,4,2};
	selection(a,5);
	for(int i=0;i<5;i++)cout<<a[i]<<" "; 
	return 0;
}

冒泡排序


从前往后比较两两相邻的元素,如果前者>后者,则交换它们。元素就像气泡一样往后冒。
八大排序-上次看到这么好的排序博客还是在上次

  • 时间复杂度 O ( n 2 ) O(n^2) O(n2)

  • 稳定性:稳定
    遇到相同或更大元素时,不会交换。

  • 排序趟数是否与原序列有关:有关
    已经升序的极端条件下,可以记录是否发生交换,若无交换则序列有序,退出即可。

#include<bits/stdc++.h>
using namespace std;
void bubble(int a[],int n){
	for(int i=0;i<n;i++){
		bool tag=false;  //记录此趟是否发生交换
		for(int j=0;j<n-i-1;j++){
			if(a[j]>a[j+1]){  //和后一个元素比较
				swap(a[j],a[j+1]);
				tag=true;
				}
			}
		if(tag==false)break;  //没有发生交换,退出
	}
}
int main(){
	int a[5]={3,5,1,4,2};
	bubble(a,5);
	for(int i=0;i<5;i++)cout<<a[i]<<" "; 
	return 0;
}

插入排序


每次将待排序的元素正确插入到前面已经排好序的序列中,就像理扑克牌一样。
八大排序-上次看到这么好的排序博客还是在上次

  • 时间复杂度 O ( n 2 ) O(n^2) O(n2)

  • 稳定性:稳定
    从后向前先比较再移动,遇到相同不会交换。

  • 排序趟数是否与原序列有关:无关
    每趟插入1个元素,固定n-1趟。

#include<bits/stdc++.h>
using namespace std;
void insertion(int a[],int n){
	for(int i=0;i<n;i++){  //遍历i个待插元素
		for(int j=i;j>0;j--){  //插入前面
			if(a[j]<a[j-1])
				swap(a[j],a[j-1]);
		}
	}
}
int main(){
	int a[5]={3,5,1,4,2};
	insertion(a,5);
	for(int i=0;i<5;i++)cout<<a[i]<<" "; 
	return 0;
}

希尔排序


每次把相隔x(增量)的元素划分成一个子表,进行直接插入排序(先不管其他元素),然后不断缩小x。从基本有序到整体有序。
八大排序-上次看到这么好的排序博客还是在上次

  • 时间复杂度 O ( n 2 ) O(n^2) O(n2)
  • 稳定性:不稳定
    相同元素被划分到不同子表时,可能会改变它们的相对位置。
  • 排序趟数是否与原序列有关:无关
    无论原序列状态如何,都只与增量x(即数组大小n)有关。
#include<bits/stdc++.h>
using namespace std;
void shell(int a[],int n){
	for(int x=n/2;x>0;x/=2){  //增量x 
		for(int i=x;i<n;i++){  //划分子表 
			//子表内插入排序 
			for(int j=i;j>=x&&a[j]<a[j-x];j-=x) 
				swap(a[j],a[j-x]);
		}
	}
}
int main(){
	int a[5]={3,5,1,4,2};
	shell(a,5);
	for(int i=0;i<5;i++)cout<<a[i]<<" "; 
	return 0;
}

快速排序


每趟将比该元素大的放在它右边,比它小的放在它左边,那么该元素的位置就确定了,再递归的排序其他元素即可。
八大排序-上次看到这么好的排序博客还是在上次

  • 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
    需要确定 n n n个数的正确位置,每趟比较次左右两半区间,复杂度是 O ( l o g n ) O(logn) O(logn)。

  • 稳定性:不稳定
    在交换左右两边的数时会改变相对位置。

  • 排序趟数是否与原序列有关:有关

#include<bits/stdc++.h>
using namespace std;
int partition(int a[],int low,int high){  //一趟划分
	int cur=a[low];  //当前元素的值  
	while(low<high){
		while(low<high&&a[high]>=cur)high--;  //从后往前找比当前值小的元素
		a[low]=a[high];  //把小的换到前面去
		while(low<high&&a[low]<=cur)low++;  //从前往后找比当前值大的元素
		a[high]=a[low];  //把大的换到后面去
	}
	//当low=high,跳出循环,这个位置就是当前元素的正确位置了
	a[low]=cur;  
	return low;
}
void qsort(int a[],int low,int high){
	if(low<high){
		int idx=partition(a,low,high);  //确定该元素的正确位置
		qsort(a,low,idx-1);  //递归左右两个区间
		qsort(a,idx+1,high);
	}
}
int main(){
	int a[5]={3,5,1,4,2};
	qsort(a,0,4);
	for(int i=0;i<5;i++)cout<<a[i]<<" "; 
	return 0;
}

插播反爬信息 )博主CSDN地址:https://wzlodq.blog.csdn.net/

堆排序


以大根堆为例,即根元素是最大的。初始时无序,从下往上(叶节点往根)的方向,将两个叶子节点中值更大的元素和它的父节点交换,父节点换下来后如果还有子节点(即除了最后一层),则还要比较是否比现在的两个叶子节点更大,不然选更大的叶节点换上来,依次递归。
八大排序-上次看到这么好的排序博客还是在上次

  • 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
    n − 1 n-1 n−1次向下调整操作,每次调整复杂度是 O ( h ) O(h) O(h)即 O ( l o g n ) O(logn) O(logn)。
  • 稳定性:不稳定
    可能把后面相同的关键字调整到前面。
  • 排序趟数是否与原序列有关:有关
    如果有序,每次向下调整的复杂度是 O ( 1 ) O(1) O(1)。
#include<bits/stdc++.h>
using namespace std;
void adjustheap(int a[], int i, int n){
    for(int j=i*2+1;j<n;){
        if(j+1<n&&a[j]<a[j+1])  //取左右孩子中较大的那个 
    		j++;
        if(a[i]>a[j])break;
        swap(a[i], a[j]);
        //交换后递归比较与子节点大小 
        i=j;
        j=2*i+1;
    }
}
void makeheap(int a[], int n){  //建堆 
    for(int i=n/2-1; i>=0; i--)//递归从最后一个父节点开始调整堆
        adjustheap(a,i,n);
}
void heapsort(int a[], int n){
    makeheap(a, n);
    for(int i=n-1; i>=0; i--){
        swap(a[i], a[0]);
        adjustheap(a, 0, i);
    }
}
int main(){
	int a[5]={3,5,1,4,2};
	heapsort(a,5);
	for(int i=0;i<5;i++)cout<<a[i]<<" "; 
	return 0;
}

归并排序


递归的划分子区间直到一个元素,然后依次合并子区间,此时每个子区间内部有序。合并过程就是比较两个子区间的最前面元素,取最小的那个,直到一个子区间取完了,那么再直接加上另一个子区间剩下元素即可。
八大排序-上次看到这么好的排序博客还是在上次

  • 时间复杂度 O ( n l o g n ) O(nlogn) O(nlogn)
    每趟归并 O ( n ) O(n) O(n),共需要 O ( l o g n ) O(logn) O(logn)趟归并。
  • 稳定性:稳定
    归并操作从前往后合并两个子区间,不会改变相对位置。
  • 排序趟数是否与原序列有关:无关
    无论原序列状态如何,都要划分到一个元素然后开始归并。
#include<bits/stdc++.h>
using namespace std;
int b[5];  //辅助数组 
void merge(int a[],int low,int mid,int high){
	for(int k=low;k<=high;k++)b[k]=a[k];
	int i=low,j=mid+1,k=low;
	//i,j分别表示左右子区间最前面元素下标
	//k表示合并后数组下标 
	while(i<=mid&&j<=high){
		if(b[i]<=b[j])
			a[k++]=b[i++];
		else a[k++]=b[j++];
	}
	while(i<=mid)a[k++]=b[i++];
	while(j<=high)a[k++]=b[j++]; 
}
void mergeSort(int a[],int low,int high){
	if(low<high){
		int mid=(low+high)/2;  //从中间划分区间
		mergeSort(a,low,mid);  //分别归并左右区间 
		mergeSort(a,mid+1,high); 
		merge(a,low,mid,high);  //归并 
	}
}
int main(){
	int a[5]={3,5,1,4,2};
	mergeSort(a,0,4);
	for(int i=0;i<5;i++)cout<<a[i]<<" "; 
	return 0;
}

基数排序


从每个数的低位向高位遍历,第二重循环遍历每个数,按照该位的数值入队到对应的位(0~9)里,最后从9到0按加入的顺序取出这些数,则完成了一趟数据对第i位的排序。
八大排序-上次看到这么好的排序博客还是在上次

  • 时间复杂度 O ( d ( n + r ) ) O(d(n+r)) O(d(n+r))
    r r r表示基数, d d d是长度, n n n表示个数。

  • 稳定性:稳定
    用队列保证稳定性。

  • 排序趟数是否与原序列有关:无关
    按数位和元素个数操作,与序列初试状态无关。

  • 小结

算法 时间复杂度 稳定性 排序趟数是否与原序列有关
选择排序 O ( n 2 ) O(n^2) O(n2) 不稳定 无关
冒泡排序 O ( n 2 ) O(n^2) O(n2) 稳定 有关
插入排序 O ( n 2 ) O(n^2) O(n2) 稳定 无关
希尔排序 O ( n 2 ) O(n^2) O(n2) 不稳定 无关
快速排序 O ( n l o g n ) O(nlogn) O(nlogn) 不稳定 有关
堆排序 O ( n l o g n ) O(nlogn) O(nlogn) 不稳定 有关
归并排序 O ( n l o g n ) O(nlogn) O(nlogn) 稳定 无关
基数排序 O ( d ( n + r ) ) O(d(n+r)) O(d(n+r)) 稳定 无关

sort()


就实际编程而言,没有sort()解决不了的排序问题(如果有那就有吧),它的底层主要是快速排序,源码这就不再深究了,下面主要介绍下sort()的用法。
头文件是<algorithm>

#include<bits/stdc++.h>
using namespace std;
int main(){
	int a[5]={3,5,1,4,2};
	sort(a,a+5);  //两个参数分别是起始位置和结束位置 
	for(int i=0;i<5;i++)cout<<a[i]<<" "; 
	return 0;
}

嗯对,就是这么简单粗暴。
下面再介绍下自定义结构体的复杂排序情况。

#include<bits/stdc++.h>
using namespace std;
struct node{
	string name;
	int grade;
	node(){}
	node(string a,int b){
		name=a;
		grade=b;
	}
	bool operator<(const node&a)const{  //可以自定义小于操作符 
		if(grade==a.grade)  //成绩相同,名字升序 
			return name<a.name;
		return a.grade<grade;  //否则按成绩降序 
	}
}a[5]; 
bool cmp(node a,node b){  //也可以定义比较函数 
	if(a.name==b.name)  //名字相同,成绩降序 
		return a.grade>b.grade;
	return a.name<b.name;  //否则名字升序 
} 
int main(){
	a[0]=node("c",90);
	a[1]=node("b",90);
	a[2]=node("b",95);
	a[3]=node("a",80);
	a[4]=node("da",100);
	sort(a,a+5);  //使用结构体内定义<
	for(int i=0;i<5;i++)
		cout<<a[i].name<<":"<<a[i].grade<<"\n"; 
	cout<<"---------------\n"; 
	sort(a,a+5,cmp);  //使用自定义比较函数
	for(int i=0;i<5;i++)
		cout<<a[i].name<<":"<<a[i].grade<<"\n"; 
	return 0;
}

八大排序-上次看到这么好的排序博客还是在上次
同样的也可以对vector<>排序:

#include<bits/stdc++.h>
using namespace std;
struct node{
	string name;
	int grade;
	node(){}
	node(string a,int b){
		name=a;
		grade=b;
	}
	bool operator<(const node&a)const{  //可以自定义小于操作符 
		if(grade==a.grade)  //成绩相同,名字升序 
			return name<a.name;
		return a.grade<grade;  //否则按成绩降序 
	}
}a[5]; 
bool cmp(node a,node b){  //也可以定义比较函数 
	if(a.name==b.name)  //名字相同,成绩降序 
		return a.grade>b.grade;
	return a.name<b.name;  //否则名字升序 
} 
int main(){
	a[0]=node("c",90);
	a[1]=node("b",90);
	a[2]=node("b",95);
	a[3]=node("a",80);
	a[4]=node("da",100);
	vector<node>v;
	for(int i=0;i<5;i++)v.push_back(a[i]);
	sort(v.begin(),v.end());  //起始位置,结束位置,[比较函数] 
	for(int i=0;i<5;i++)
		cout<<v[i].name<<":"<<v[i].grade<<"\n"; 
	cout<<"---------------\n"; 
	sort(v.begin(),v.end(),cmp);  //换汤不换药 
	for(int i=0;i<5;i++)
		cout<<v[i].name<<":"<<v[i].grade<<"\n"; 
	return 0;
}

附:算法可视化网站
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

原创不易,请勿转载本不富裕的访问量雪上加霜
博主首页:https://wzlodq.blog.csdn.net/
来都来了,不评论两句吗

上一篇:字符串算法题(2)反转字符串II


下一篇:[学习笔记] 无向图和有向图的连通分量