# 排序

# 0、前言

我们常用的排序算法有十种。
通常分为以下两类：
- 比较类排序： 通过比较来决定元素间的次序，时间复杂度为 O (nlogn)~O ( $n^2$ )。
- 非比较类排序： 不通过比较来决定元素间的相对次序，时间复杂度可以突破 O (nlogn)，以线性时间运行。
排序算法的稳定性:
排序算法的稳定性是指在排序过程中，如果两个元素相等，它们在排序前后的相对位置是否保持不变。稳定的排序算法可以保证相等元素的相对顺序不变，而不稳定的排序算法则可能会改变相等元素的相对顺序。

说明
以下讲解排序时，目的都是为了从左往右越来越大。

# 1. 冒泡排序

# 1.1 描述

从左到右依次比较相邻元素大小，更大的元素交换到右边。
从最左边走到最右边的过程中，是一定能找到一个最大数的。
多轮重复从左到右，而前一轮所排出来的数不参与比较，所以需要记录经过了几轮。
根据上述规则，每一轮结束都会减少一个元素参与比较（即已排好序），直到未排序的元素个数为 $0$ 。

# 1.2 动图演示

# 1.3 代码实现

	void init(){
	for(int i=1;i<=n;i++){
	flag=false;
	for(int j=1;j<=n-i+1;j++){
	if(a[j]>a[j+1]){
	swap(a[j],a[j+1]);
	}
	}
	if(flag==1){
	return;
	}
	}
	}

# 1.4 算法分析

冒泡排序属于交换排序，稳定性取决于代码怎么写，复杂度为 $O(n^2)$ , 空间复杂度为 $O(1)$ 。
复杂度最差为 $O(n^2)$ ，最好为 $O(n)$
最好的时需要记录