冒泡排序法

冒泡排序并不是课程中的内容，但liuyubo老师将他的代码写在了github中，顺便学习了一下，但是对于他的优化方法的测试结果，我还有些不太理解。

思路

冒泡排序依然是一个O(n²)的排序，思路是:

通过不断将自己与自己后一个元素比较并交换，将较大的元素交换到后面，这样过完一整趟，就可以让最大的元素归位到最后，此时我们可以保证至少数组中最后一个元素是排好序的，以此类推，下一趟排序我们将扫描的范围缩小1，重复这个过程，直到过完一整趟都没有发生交换，证明数组已经排好序。

实现

先贴代码

void bubbleSort(int arr[], int n){
    bool isSwap;
    do{
        isSwap = false;
        for (int i = 0; i<n-1; i ++) {
            if (arr[i] > arr[i + 1]){
                swap(arr[i], arr[i + 1]);
                isSwap = true;
            };
        }
        n --;
    }while(isSwap);
}

意思应该已经比较清楚了，这个版本的冒泡排序和插入排序一样是可以提前结束的，这意味着它在近乎有序的数组排序中将是一个O(n)级别的算法。

优化

在上述的分析中，我们是通过每一趟将扫描范围缩小1来优化整个排序的，但我们还可以将缩小范围的步伐迈得更大一些，事实上我们可以保证每次扫描的最后一次交换都确定了，最后交换的那个元素后面直至数组末尾的部分是有序的，因此我们可以做如下改动

void bubbleSort2(int arr[], int n){
    int end;
    do{
        end = 0;
        for (int i = 0; i<n-1; i ++) {
            if (arr[i] > arr[i + 1]){
                swap(arr[i], arr[i + 1]);
                end = i + 1;
            };
        }
        n = end;
    }while(n > 0);
}

这里用end来记录每趟扫描最后交换的位置，然后将范围的右边界缩小到这个位置，理论上可以使性能得到优化。

测试

这个部分就很诡异了，我们先来看看吧。

随机数组排序

insertion sort2 : 0.085354s
bubble sort : 0.311727s
bubble sort2 : 0.311345s

可以看到随机的情况下对10000个数排序，冒泡排序的水平在O(n²)的正常范围内，然而优化后的冒泡排序并没有体现出什么优势。

近乎有序的数组

insertion sort2 : 0.000269s
bubble sort : 0.114654s
bubble sort2 : 0.088130s

在近乎有序的情况下，优化后的冒泡排序有了一些优势，但依然比插入排序要慢很多。

完全有序的数组

insertion sort2 : 0.000042s
bubble sort : 0.000026s
bubble sort2 : 0.000025s

完全有序的情况下，冒泡排序整体快于插入排序，但优化效果并不是很明显。

结论

没有结论。。。很奇怪，这么看来优化似乎没有起到很明显的作用，后续再研究一下。