C++冒泡排序（优化）

C++冒泡排序（优化）

优化+bool类型变量，如果某次冒泡排序没有发生元素的交换，就说明元素已经排好序了，就不用再进行无效的排序了

依次比较两个相邻的元素，若前一个数比后一个数大，交换两个数，即将最大的数放在最后，是一种从小到大的排序

 

---

void buffuerSort(vector& arr) {//需要传引用类型，不传引用类型，无法修改主函数中的数组
	for(int j = arr.size();j>0;j--){//每次需要排的数的个数
		bool judge = true;//状态变量，检验是否发生了交换
		for (int i = 0; i  arr[i + 1]) {
				swap(arr[i], arr[i + 1]);
				judge = false;
			}
		}
		if (judge == true) {//此种情况说明已经排好序了，没有必要再进行排序了
			return;
		}
	}
}
//输出函数
void printArr(vector arr) {
	for (int i = 0; i < arr.size(); i++) {
		cout << arr[i] << "  ";
	}
}
//主函数
int main() {
	vector arr = { 2,4,1,5,3 };
	buffuerSort(arr);
	printArr(arr);
	return 0;
}

---

时间复杂度：

最差的情况下，元素是从大到小的，而目标是从小到大，所以需要O(n^2)复杂度。

最优的情况下，元素本身就是有序的，但是我们仍需冒一次泡判断出这个序列本身是有序的，时间复杂度O(n)。

具体 *** 作：加一个标记变量表示是否产生了交换 *** 作，若产生交换 *** 作，则说明此时序列未达到有序，则需继续执行冒泡，若无交 换 *** 作说明有序，提前结束。我们在执行每一轮冒泡时，都检查下这个标记变量，即可提前退出。 若元素初始有序，则一次冒泡就可判断出这个序列有序，直接退出，时间复杂度O(n).

平均复杂度；O(n^2)。

空间复杂度：

冒泡排序的空间复杂度就是在交换元素时那个临时变量所占的内存空间，只需交换两个元素，所以为O(1)。

稳定性：

交换 *** 作执行时并不会交换相邻的相等元素，所以是稳定的。