算法踩坑4-冒泡排序

背景

接上面三篇文章
算法踩坑-快速排序
算法踩坑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;
        }
    }
}

冒泡排序优化

冒泡排序有个优化的地方在于：当序列已经是有序的情况，添加一个标记为进行标记，这趟循环结束之后，如果标记为未被标记为已改变，那么不用再进行排序。
原因在于，这个序列中没有存在逆序，不会发生交换，元素都是有序的了，可以停止排序。

One More Thing

噢！我是算法，点我