笔试时，冒泡排序也要写得优雅出众

导语

排序算法是笔试面试当中经常遇到的内容，之前参加的两个笔试都遇到了手写排序算法，可能大家都能写出来，但是要出众就要把代码优化一下，让人一看到就觉得你想的不简单。首先从最简单的冒泡排序开始，相信大家都能默出来，由于大部分人写的都一样，所以你要更出众的代码。

冒泡排序算法的步骤：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

首先给出严格按照定义写的代码：

void bubbleSort(int array[], int length)
{
    for (int i = 0; i < length; i++) {
        for (int j = 1; j < length - i; j++) {
            if (array[j-1] > array[j]) {
                swap(array[j-1], array[j]);
            }
        }
    }
}

这里先给出交换函数，交换函数有很多种写法，最基本的写法是：

void swap(int &a, int &b) {
    int temp = a;
    a = b;
    b = temp;
}

据说会在笔试中考不用中间变量交换两个数，网上有种写法：(其实这类方法还可已通过加减乘等代换方式实现，但都有一定弊端，虽然我们在平时的编程中不会这么写，不装X的话还是写第一种)

void swap(int &a, int &b) {
    a = a ^ b;
    b = b ^ a;
    a = a ^ b;
}

但这种写法有个问题，当交换同一元素时，该元素会被置零，在选择排序中会有bug所以还是建议第一种写法，当然你也可以在里面加个判断：

void swap(int &a, int &b) {
    if (a != b) {
        a = a ^ b;
        b = b ^ a;
        a = a ^ b;
    }
}

很明显上面的经典算法有些不足，当我们需要排序的数组基本有序时，上面的代码还会做出很多不必要的查找判断，降低了代码的执行效率。下面我们进行第一步优化，我们先定义一个标志flag，用来判断本次排序中是否发生交换，如果没有发生交换，说明排序已经完成，我们不需要再做不必要的循环判断，代码为：

void bubbleSort(int array[], int length) {
    bool flag = true;//判断是否发生交换
    while (flag) {
        flag = false;
        for (int j = 1; j < length; j++) {
            if (array[j-1] > array[j]) {
                swap(array[j-1], array[j]);
                flag = true;
            }
        }
        length --;
    }
}

对比下两种方法的比较大小次数：

由上图对比可见，第二种方法大大减少了对比的次数。

再做进一步优化，如果有数组前面几个是无序的，而后面的元素都已经是有序的，那我们就可以记录下无序的位置，下次排序判断时，只需要从数组头部遍历到该位置就可以了，这样可以省去遍历后面的元素，提高了代码的执行效率。代码为：

void bubbleSort(int array[], int length)
{
    int flag = length;
    while (flag > 0) {
        int k = flag;
        flag = 0;
        for (int j = 1; j < k; j++) {
            if (array[j - 1] > array[j]) {
                swap(array[j - 1], array[j]);
                flag = j;
            }
        }
    }
}

该方法和第二种的区别就是：先判断有没有交换，若有交换我也只遍历无序的区域。比较次数：

很明显比上面的少了很多次。
最后要说一句，冒泡排序写起来简单，相对于其他的排序算法效率比较低下，数据规模不大时，可以使用。