背景
接上面三篇文章
算法踩坑-快速排序
算法踩坑2-插入排序
算法踩坑3-堆排序
来继续聊聊最近我写的一些算法的小例程，这次要聊的是冒泡排序，是一个时间复杂度O(N²)的算法。冒泡排序是一个很简单的算法。
主要从以下几方面来说的：
- 冒泡排序思想
- 冒泡排序实现
- 冒泡排序优化
冒泡排序思想
冒泡排序就是简单的一句话：两两交换元素，在一次交换的过程中，把一个最大的元素冒泡到最右边，循环这个过程，直到序列有序为止。
冒泡排序实现
冒泡排序是O(N²)是最简单的，所以例程也很简单
void Bubblesort(ElementType arr[], int count) {
int i, j;
_Bool isChanged = 0;
for (i = 0; i<count; i++) {
isChanged = 0;
for (j = 1; j<count-i; j++) {
if (arr[j] < arr[j-1]) {
ElementType tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
isChanged = 1;
}
}
// 没有存在逆序，表示i之后的元素都是有序的序列，可以结束排序
if (0 == isChanged) {
break;
}
}
}
冒泡排序优化
冒泡排序有个优化的地方在于：当序列已经是有序的情况，添加一个标记为进行标记，这趟循环结束之后，如果标记为未被标记为已改变，那么不用再进行排序。
原因在于，这个序列中没有存在逆序，不会发生交换，元素都是有序的了，可以停止排序。
