冒泡排序算法小优化

冒泡排序算法是个入门的排序算法，可能是很多人接触过的第一个排序算法，算法本身很简单，主要步骤如下：

1、从前到后遍历数组，依次比较当前元素和
下一个元素。如果当前元素大于下一个元素，
则对调当前元素和下一个元素；如果当前元素
不大于下一个元素，什么也不用做，继续遍历
下一个元素。这样经过一轮遍历后，最大的元
素就排到了数组的尾部，找到了最大的元素。
2、重复第一步，依次找到第二大、第三大等
元素等等，并放到适当的位置。

算法的动图（网上找的）演示如下：

冒泡排序动图演示

常规排序代码如下：

    int arr[] = {2, 4, 0, 5, 7, 1, 3, 8, 9};
    int len = sizeof(arr) / sizeof(arr[0]);
    int max = len;

    while (max > 0) {
        for (int i = 0; i < max - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
            }
        }

        max--;
    }

接下来说下可以优化的点，如果这个数组的前部分本身就是有序的，只是后面一部分元素是乱序的，其实本必要做完所有轮次的排序，可以提早结束遍历，提高程序性能。提高结束遍历的条件是：

如果某轮排序结束后，在本轮排序中，没有需要
发生元素顺序的调换，那么就可以认为当前的数
组中，所有元素都是有序的了，可以退出遍历。

优化后的代码为：

    int arr[] = {2, 4, 0, 5, 7, 1, 3, 8, 9};
    int len = sizeof(arr) / sizeof(arr[0]);
    int max = len;

    while (max > 0) {
        int replace = 0;

        for (int i = 0; i < max - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                replace++;
            }
        }

        if (replace == 0) {
            break;
        }

        max--;
    }

以程序的测试数据为例，优化前，循环次数为36次，优化后，循环次数减少到30次，减少6次，减少16.67%的循环次数。如果数组乱序程度不是很大的情况下，减少的幅度应该是比较可观的。

优化前冒泡排序过程

优化后冒泡排序过程