8. 数据结构—交换排序

1）冒泡排序

#include<bits/stdc++.h>
using namespace std;
typedef int ElemType;

//冒泡排序
//最多排序n-1趟，每趟将确定一个最小的放在队头 
//第i趟比较n-i次(从后往前找最小)
//添加了一个flag标记位用来记录每趟是否存在交换，若不存在则说明排序结束 
void BubbleSort(ElemType A[],int n){
	for(int i=0;i<n-1;i++){  //n-1趟排序 
		bool flag=false;  //标记此趟是否存在交换
		for(int j=n-1;j>i;j--){  //每趟从后往前 
			if(A[j-1]>A[j]){
				ElemType t=A[j-1];
				A[j-1]=A[j];
				A[j]=t;
				flag=true;
			} 
		}
		if(!flag)   //如果没有发生交换，说明已经有序了 
 			return;
	} 
}
 
 
int main(void){
	int a[5]={34,-13,24,324,21};
	BubbleSort(a,5); 
	for(int i=0;i<5;i++)
		cout<<a[i]<<" ";
	return 0;
}
 

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

最好情况下：序列整体有序，第一趟比较n-1次之后即可完成排序，复杂度O(n)

最坏情况下:  序列整体逆序，需要比较n-1趟，第i趟排序比较n-i次关键字，复杂度O(n^2）

tips:无特别说明下，时间复杂度指的是最坏时间复杂度

• 空间复杂度：O(1) 

仅仅只是使用了常数个辅助空间(两数交换的时候)，故空间复杂度为O(1） 

• 稳定性：稳定 

从代码中，我们可以看到，当两数相等时，我们并不交换其位置，所以冒泡算法稳定。 

2）快速排序——递归实现

• 时间复杂度：O(n*递归层数)   

最好情况下：选取基准够好，刚好将其划分成了一个类似完全二叉树，时间复杂度O(nlogn) 

最坏情况下:  选取基准最差，直接划分成了一个单支树，时间复杂度O(n^2)

• 空间复杂度：O(递归层数) 

由于快速排序是递归的，所以需要借助一个递归工作栈来保存每层递归调用的必要信息，其容量与递归调用的最大层数一致。

最坏情况下：O(n）

最好情况下：O(logn)

平均情况下：O(logn) 

• 稳定性：不稳定 

例如表{1，2 ，2}，以1为基准的时候，经过一趟排序之后，相对位置发生了改变。