排序算法

冒泡排序

冒泡排序重复访问要排序的序列，每次比较两个元素，如果顺序错误就交换这两个元素。直到全部遍历和比较所有元素之后结束排序。

冒泡排序对n个项目需要O(n²)的比较次数，对于大量元素的排序效率很低。

冒泡排序与插入排序拥有相等的执行时间，但是两种算法交换次数有很大的不同。在最坏情况下，冒泡需要O(n²)次交换，而插入排序只要最多O(n)次交换。冒泡排序会对已经排好序的数列执行O(n²)次比较，而插入排序再这里只需要O(N²)次运算。冒泡排序如果在内部的第一次循环运行时，使用一个旗标来表示有无需要交换的可能，也可以把最优情况下的复杂度降低到O(n)。在这种情况下，已经排序好的序列就无交换的需要。

冒泡排序算法的步骤

• 比较相邻的元素。如果第一个比第二个大，就交换他们两个
• 对每一个相邻的元素作同样的操作，从开始第一对到结尾最后一对。这步做完后，最后的元素会是最大的元素。
• 针对所有的元素重复以上的步骤，出了最后一个。
• 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对元素需要比较

具体实现：

• 原数组：6 5 4 3 2 1
• 第一次循环：5 4 3 2 1 6
• 第二次循环：4 3 2 1 5 6
• 第三次循环：3 2 1 4 5 6
• 第四次循环：2 1 3 4 5 6
• 第五次循环：1 2 3 4 5 6

int bubbleSort(int a[], int count)
{
    int i, j, tmp;
    for (i = 0;i < count - 1;++i)
    {
        for (j = 0;j < count - 1 - i;++j)
        { 
            if (a[j] > a[j+1])
            {
                tmp = a[j];
                a[j] = a[j + 1];
                a[j+1] = tmp;
            }
        }
    }
}

优化1（优化外层循环）

原数组本来就是有序的：1，2，3，4如果我们还是按照上述方法执行，那么还是要执行n-1次，于是我们就需要在没跑完一趟就判断一次原数组现在是否有序，如果有序，直接return掉；

• 原数组：1 2 3 4
• 第一次循环：1 2 3 4

因为原本的序列就是有序的，所以并不会进入内层循环

int bubbleSort1(int a[], int count) 
{
    int i = 0;
    int j = 0;

    for (i = 0; i < count - 1; ++i)
    {
        int flag = 1; // 假定每次进入都是有序的flag设为1
        for (j = 0; j < count - i - 1; ++j)
        {
            int tmp = 0;
            if (a[j] > a[j + 1])
            {
                tmp = a[j];
                a[j] = a[j + 1];
                a[j+1] = tmp;
                flag = 0; // 如果发生交换，则flag置为0
            }
        }
        if (flag == 1) // 如果这趟走完，没有发生交换，则原数组有序
            break;
    }

}

优化2(减少内部循环比较的次数)

void bubbleSort2(int a[], int count) 
{
    int i = 0;
    int j = 0;
    int k = count - 1; // 控制内部比较循环
    int n = 0;

    for (i = 0; i < count - 1; ++i)
    {
        int flag = 1;
        n = 0;
        // 假定每次进入都是有序的flag为1
        for (j = 0; j < k; ++j)
        {
            int tmp = 0;
            if (a[j] > a[j+1])
            {
                tmp = a[j];
                a[j] = a[j+1];
                a[j+1] = tmp;
                flag = 0; // 如果发生交换，则flag置位0
                n = j; // 保存最后一次交换的下标
            }
        }

        if (flag == 1) // 如果这趟走完，没有发生交换，则原数组有序；
            break;
        k = n; // 最后一次交换的位置给k，减少比较的次数；
    }
}