数据结构(8.3_1)——冒泡排序

交换排序：

冒泡排序和快速排序

冒泡排序：

示例：

 

从行往前将A[i-1]和A[i]比较若遇到A[i-1]>A[i]则将两个元素交换 

 

注意：

 

代码实现： 

//交换
void swap(int& a, int& b) {int temp = a;a = b;b = temp;
}
//冒泡排序
void BubbleSort(int A[], int n) {for (int i = 0; i < n - 1; i++) {bool flag = false;		//表示本趟冒泡是否发生交换的标志for (int j = n - 1; j > i; j--)		//一趟冒泡过程if (A[j - 1] > A[j]) { //若为逆序swap(A[j - 1], A[j]);//交换flag = true;}if (flag == false)return;			//本趟遍历后没有发生交换，说明表已经有序}
}

算法性能分析 

空间复杂度：O(1)

最好情况(有序)：

最坏情况(逆序)：

平均时间复杂度=O(n^2)

每次交换都需要移动元素3次

稳定性：稳定

冒泡排序适用于顺序存储和链式存储的线性表

总结：