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

2023-12-17 18:09:45

文章目录

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

本文将用说人话+动图的形式带你搞懂常见排序算法，简要分析复杂度、稳定性等指标，并给出参考代码。最后安利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


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