写好冒泡排序

冒泡

冒泡排序是我们最容易写出来的排序算法,就算没有学过算法,也能自己轻松写出来如下排序代码:

void bubbleSort0 (int arr[], int len) 
{
    int i, j, temp;
    for (i = 0; i < len; i++) {
        for (j = i + 1; j < len; j++) {
            if (arr[i] > arr[j]) { 
                // 用当前待排序索引和剩余所有未排序位进行比较 如果大于当前字符,就交互。
                temp = arr[j];
                arr[j] = arr[i];
                arr[i] = temp;
            }
        }
    }
}

上边的代码,基本思想是,从数组第一个元素开始,拿出该元素和剩余所有元素比较,只要当前元素大于剩余元素中的任何一个,就互换位置;这样一轮排序下来,就能找出当前所有待排序元素的最小元素,直到最后一个元素。

上述代码虽然实现了排序,但严格来讲,不算是标准的冒泡排序算法,因为它不满足“两两比较相邻记录”。冒泡排序的基本思想是:两两比较相邻记录关键字,如果反序则交互,直到没有反序记录为止。 下面来看看比较正宗的冒泡排序算法:

void bubbleSort1 (int arr[], int len) 
{

    int i, j, temp;

    for (i = 0; i < len; i++) {
        for (j = len - 1; j > i; j--) { // 从后往前循环
            if (arr[j - 1] > arr[j]) { 
                // 这里比较是 j - 1 和 j 相邻的两个元素,和上边代码中比较 i 和 j 是有区别的。
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
        }
    }
}

这次的代码依然是两两比较,但是是从后往前两两进行比较。每一轮比较结束后,除了将最小元素找出,还能将较小的数字提升到比较靠前的位置,显然这种写法是有进步的。较小的数字如同气泡般慢慢浮到上面,因此就将此算法命名为冒泡算法。

冒泡排序优化

假设有一待排序的序列是 {2, 1, 3, 4, 5, 6},那么用上述冒泡排序算法,只需要一轮交换,就得到了正常的序列。但是算法依然会不依不饶的从 i = 2 循环到 6,但每次都是无效循环。代码改进的关键是增加一个 flag ,来记录每轮排序后,是否已经得到了正常的序列:

void bubbleSort1 (int arr[], int len) 
{
    int i, j, temp;
    _Bool flag = TRUE;

    for (i = 0; i < len && flag; i++) { // 循环条件改为 i < len && flag 
        flag = FALSE; // 假设已经排好序
        for (j = len - 1; j > i; j--) {
            if (arr[j - 1] > arr[j]) {
                temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
                flag = FALSE; // 还需要交互,无法判断是否已经排好序,进行下一轮排序
            }
        }
    }
}

上述代码增加一个 bool 型的 flag,就可以避免因已经排好序的情况下的无意义的循环判断。

复杂度分析

我们用改进后的代码来分析算法的时间复杂度;当情况是最好的,也就是序列本身已经有序了,那么代码只需要执行 n – 1 次比较操作,不需要进行数据交换,时间复杂度为 O(n)。

最坏的情况,待排序的序列是逆序,那么依次需要比较 (n – 1) + (n -2) + …+ 3 + 2 + 1 = \frac{n(n-1)}{2} 次,并做等量的数据交换,总的时间复杂度为 O(n^2 )。

(完)

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注