交换排序：冒泡排序（Bubble Sort）

基本思想：

将n个记录看作按纵向排列，在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换，整个排序过程共进行n-1趟。如下所示：

初态 第1趟 第2趟 第3趟 第4趟 第5趟 第6趟 第7趟
 49   38   38   38    38   13   13   13
 38   49   49   49    13   27   27   27 
 65   65   65   13    27   38   38
 97   76   13   27    49   49
 76   13   27   49    49
 13   27   49   65
 27   49   76 
 49   97    

算法的实现：

// 输出数组内容
void print(int array[], int length, int i) {
    printf("i=%d:",i);
    for (int j = 0; j < length; j++) {
        printf(" %d ", array[j]);
    }
    printf("\n");
}

// 冒泡排序（Bubble Sort）
void bubbleSort(int array[], int length) {
    if(NULL == array || 0 == length) {
        return;
    }
    
    for (int i = 0; i < length - 1; i++) {
        for (int j = 0; j < length - i - 1; j++) {
            if (array[j] > array[j+1]) {
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
        print(array, length, i); // 打印每趟排序的结果
    }
    
    return;
}

int main(int argc, const char * argv[]) {
    int arrayBubbleSort[8] = { 49, 38, 65, 97, 76, 13, 27, 49 };
    bubbleSort(arrayBubbleSort, 8);
    printf("\n");
    
    return 0;
}

冒泡排序算法的改进

对冒泡排序常见的改进方法是加入一标志性变量exchange，用于标志某一趟排序过程中是否有数据交换，如果进行某一趟排序时并没有进行数据交换，则说明数据已经按要求排列好，可立即结束排序，避免不必要的比较过程。本文再提供以下两种改进算法：

1、设置一标志性变量pos,用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

改进后算法如下:

// 冒泡排序改进1（Bubble Sort）
void bubbleSort1(int array[], int length) {
    int i = length - 1; // 初始时，最后位置保持不变
    while (i > 0) {
        int pos = 0; // 每趟开始时，无记录交换
        for (int j = 0; j < i; j ++) {
            if (array[j] > array[j+1]) {
                pos = j; // 记录交换的位置
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
        print(array, length, i); // 打印每趟排序的结果
        i = pos; // 为下一趟排序作准备
    }
}

2、传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

改进后算法如下:

// 冒泡排序改进2（Bubble Sort）
void bubbleSort2(int array[], int length) {
    int low = 0;
    int high = length - 1; // 设置变量的初始值
    int temp,j;
    while (low < high) {
        for (j = low; j < high; j ++) { // 正向冒泡，找到最大值
            if (array[j] > array[j+1]) {
                temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
        --high; // 修改high值，前移一位
    
        for (j = high; j > low; j --) { // 反射冒泡，找到最小值
            if (array[j] < array[j-1]) {
                temp = array[j];
                array[j] = array[j-1];
                array[j-1] = temp;
            }
        }
        ++low; // 修改low值，后移一位
    }
}

总结

冒泡排序毕竟是一种效率低下的排序方法，在数据规模很小时，可以采用。数据规模比较大时，最好用其它排序方法。