冒泡排序与归并排序

归并排序

归并排序总体的时间复杂度为O(nlogn)，合并有序子序列merge过程为O(n)。接下来我们重点来关注下合并过程。

合并过程示例图


合并的主体过程为：分别从两区间的头部选择较小的一个插入到原数组中

for ( Rank i = 0, j = 0, k = 0; ( j < lb ) || ( k < lc ); ) {
      if ( ( j < lb ) && ( ! ( k < lc ) || ( B[j] <= C[k] ) ) ) A[i++] = B[j++];//j位于区间内，k超出了C的右边界时，哨兵值为无穷大，将数组B的值放入A中
      if ( ( k < lc ) && ( ! ( j < lb ) || ( C[k] <  B[j] ) ) ) A[i++] = C[k++];//k位于区间内，j超出了B的右边界时，哨兵值为无穷大，将数组C的值放入A中
      }

( j < lb ) || ( k < lc)两区间同时越界才退出循环。B[j] <= C[k]保证了归并过程的稳定性
for语句内的if判断条件采用短路求值策略，保证后面的数组访问不会越界

for (int i = 0, j = 0, k = 0; j < lb || k < lc; ) { //for语句的写法值得学习}

int i = 0, j = 0, k = 0;这里只需一个int，否则报错。

完整代码

#include <iostream>
using namespace std;

void merge(int *a, int lo, int mi, int hi)
{
    int *A =  &a[lo];  //声明一个指针
    int lb = mi - lo;
    int *B = new int[lb]; //分配一个一维数组
    cout << A[0] << endl;
    for (int i = 0; i < lb; i++)
    {
        B[i] = A[i];//for语句内进行赋值
    }
    int *C = &a[mi];
    int lc = hi - mi;
    for (int i = 0, j = 0, k = 0; j < lb || k < lc; )
    { //for语句的写法值得学习
        if (j < lb && (lc <= k || B[j] <= C[k]) ) { A[i++] = B[j++]; };
        if (k < lc && (lb <= j || C[k] < B[j]) )  { A[i++] = C[k++]; };
    }
    delete [] B; //释放内存
}

void mergesort(int *a, int lo, int hi)
{
    //递归退出条件
    if ( hi - lo < 2 ) return; //单元素区间自然有序，否则...
    int mi = (hi + lo) >> 1;   //中点的下标hi+lo
    mergesort(a, lo, mi);
    mergesort(a, mi, hi);
    merge(a, lo, mi, hi);
}

int main(int argc, const char * argv[])
{
    int a[] = {5, 4, 3, 2, 1};
    mergesort(a, 0, 5);
    return 0;
}

只需要开辟[lo，mi)大小的空间用来存放前一区间的数值，避免发生元素覆盖

int lb = mi - lo;
int *B = new int[lb]; //分配一个一维数组

B[j] <= C[k] A[i++] = B[j++]，保证了归并排序的稳定性

二路归并的精简实现：删除冗余逻辑

冒泡排序

冒泡排序属于交换排序，它的排序过程为倒三角模型。
优化后的冒泡1：sorted变量记录当前序列是否有序，若已有序，则直接返回

bool bubble(int *a, int lo, int hi)
{
    int sorted = true; //last初始化为lo

    cout << "趟数：" << ++cnt << endl;

    while (++lo < hi) //自左向右，依次检测逆序
    {
        if (a[lo] < a[lo - 1])
        {
            sorted = false;
            swap(a[lo], a[lo - 1]);
        }
    }
    return sorted;
}

void bubblesort(int *a, int lo, int hi)
{
    //hi = bubble(a, lo, hi)无需再定义其他变量
    while (!bubble(a, lo, hi--));
}

优化后的冒泡2：跳过已排序区间，每趟直接对逆序进行调整

int bubble(int *a, int lo, int hi)
{
    int last = lo; //last初始化为lo

    cout << "趟数：" << ++cnt << endl;

    while (++lo < hi) //自左向右，依次检测逆序
    {
        if (a[lo] < a[lo - 1])
        {
            last = lo; //更新最右侧逆序对的位置
            swap(a[lo], a[lo - 1]);
        }
    }
    return last;
}

void bubblesort(int *a, int lo, int hi)
{
    //hi = bubble(a, lo, hi)无需再定义其他变量
    while (lo < (hi = bubble(a, lo, hi)));
}

总结

稳定性：冒泡->稳定，归并->稳定
初始序列相关性：冒泡->相关，归并->不相关
时间复杂度：冒泡（最好O(n)，最差O(n^2)，平均O(n^2)），归并（O(nlogn)）

C++小知识

短路求值，之前的条件只要满足，直接跳入执行语句

int main(int argc, const char * argv[])
{
    int j = 0, k = 3;
    if (j < 1 || ++k > 2)
    {
        cout << j << endl;
        cout << k << endl;
    }
    return 0;
}