冒泡排序

简单版的冒泡排序

冒泡排序的基本思想是：两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。冒泡细分下来可以分为3种，先来看最简单的一段。

void BubbleSort_simple(SqList *L){
    int i, j;
    for (i = 1; i <= L->length; i++)
        for (j = i + 1; j < L->length; j++)
            if (L->r[i] > L->r[j]){
                swap(L, i, j); //交换L->r[i]与L->r[j]的值
            }                
}

严格来说，不算是标准的冒泡排序，因为它不满足“两两比较相邻记录”的思想，应该算是交换排序。思路就是和让每一个关键字和后面的比较，如果大就交换。这个应该算是最容易写出来的排序代码了，但是它却有较大的缺陷。例如：{ 9，1，5，8，3，7，4，6，2 } 在排序好1，2的位置后，对其余的关键字的排序没什么帮助，3反而还被换到了最后，也就是说，这个算法的效率是非常低的。

普通版的冒泡排序

void BubbleSort1(SqList *L){
    int i, j;
    //注意数组下标是1~9存储了数据，0没有存储数据，前面一节以已经约定好了的，而L->length=10
    for (i = 1; i < L->length; i++)
        for (j = L->length-1; j >= i; j--)    //注意 j 是从后往前循环
            if (L->r[j] > L->r[j+1]){   //若前者大于后者 
                swap(L, j, j + 1); //交换L->r[j]和L->r[j+1]的值
            }
}

从上图可以看到，普通版本的冒泡排序是从后往前两两比较并交换，所以，当 i = 0时，1就到了最上面，2也到了第三个位置。往后的话，数据交换更简单，在越多的数据排序中，这种优势就更能体现出来，较小的数字如同气泡一样慢慢浮到上面，因此就将该算法命名为冒泡算法。此处，只提供第一次排序的示意图，全部过程就自己和上面一样，用输出函数自己打印观察了。

优化版的冒泡排序

当然这样的冒泡排序是还可以优化的。如果我们的待排序序列式 {2，1，3，4，5，6，7，8，9} ，也就是说，除了1和2意外的，都已经是正常的顺序了，那么，当 i = 1时，交换了2和1，此时序列已有序，但是算法依旧会将从 i = 2到9所有的都执行了一遍，尽管没有交换，但是大量的比较还是多于的。为了改变这个现状，我们使用一个标志 flag 来改进：

void BubbleSort_optimization(SqList *L){
    int i, j;
    bool flag = true;     //flag作为标记
    for (i = 1; i < L->length && flag; i++){  //若flag为true则退出循环
        flag = false;                         //初始化为flase
        for (j = L->length-1; j >= i; j--){    
            if (L->arr[j] > L->arr[j+1]){        
                swap(L, j, j + 1);
                flag = true;      //如果有交换，则flag为true
            }
        }
    }
}

代码改动的关键就在于 i 变量的循环中增加了flag，可以避免一些无意义的循环，在性能上就有一些提升。

冒泡排序分析

时间复杂度

当最好的情况下，如果本来就是有序的，那么根据改进后的代码，就只需要 n-1 次的比较并且没有交换，时间复杂度为 O(n)；
当最坏的情况，即待排序的表是逆序的情况，此时需要比较1+2+…+(n-1)= n(n-1)/2 次，并作等数量级的记录移动，因此总的时间复杂度是O(n^2)；
因此，冒泡排序的平均时间复杂度为O(n^2)。
空间复杂度
空间复杂度是运行完一个程序所需要的内存的大小。这里包括了存储算法本身所需要的空间，输入与输出数据所占空间，以及一些临时变量（比如上面的h）所占用的空间。一般而言，我们只比较额外空间，来比较算法的空间优越性。上面的冒泡排序的临时变量所占空间不随处理数据 n 的大小改变而改变，则空间复杂度为O(1)。
稳定性
因为当r[j]==r[j+1]的时候，我们可以不移动r[j]和r[j+1]，排序前后r[j]和r[j+1]序列都是一样的，所以冒泡排序是稳定的。

参考文章： https://www.cnblogs.com/chengxiao/p/6103002.html

快速排序

https://www.cnblogs.com/chengxiao/p/6262208.html

交换排序