经典排序算法：冒泡排序（Bubble Sort）详解编程语言

冒泡排序（Bubble Sort）

冒泡排序作为排序中的经典算法，其思想是非常具有意义的，同时也是面试官很经常提问面试者的考题。
它的基本思想是：两两比较相邻的记录的关键字，如果反序则交换，知道没有反序的记录为止。

案例分析

假设我要对这么一个数组进行排序：
9,1,5,8,3,7,4,6,2

冒泡图：

冒泡顾名思义就是从下往上冒，因此我们的循环从底开始，即从2开始。

1. 第一轮，2先与6比较，2小于6，因此2与6交换位置。2小于4，2与4交换位置，以此类推，第一轮冒泡后的结果是：1,9,2,5,8,3,7,4,6
2. 第二轮，6与 4比较，6大于4，不交换位置。4与7比较，7大于4,7和4交换位置，以此类推，第二轮冒泡结果：1,2,9,3,5,8,4,7,6
3. 第三轮，6与7比较，7大于6，交换位置。4与6比较，不交换位置。8与4比较，交换位置，以此类推，第三轮冒泡结果为：1,2,3,9,4,5,8,6,7
4. 第四轮，7与6比较，不交换位置。6与8比较，交换位置。5与6比较，不交换位置。知道9与4比较，交换位置，第四轮冒泡结果为:1,2,3,4,9,5,6,8,7
5. 第五轮，基本完成排序，只需要循环把9交换至最后一个即可。

最终的冒泡结果为：
1,2,3,4,5,6,7,8,9

代码实现

#include <stdio.h> 
#include <stdlib.h> 
 
#define MAXSIZE 10 
 
typedef struct 
{ 
    int r[MAXSIZE]; 
    int length; 
}SqList; 
 
//交换函数 
void swap(SqList *L, int i, int j){ 
    int temp = L->r[i]; 
    L->r[i] = L->r[j]; 
    L->r[j] = temp; 
} 
//冒泡算法，重点 
void bubbleSort(SqList *L){ 
    int i, j; 
    for(i = 1;i < L->length; i++){ 
        for(j = L->length - 1; j >= i; j--){ 
            if(L->r[j] > L->r[j+1]){ 
                swap(L, j, j+1); 
            } 
        } 
    } 
}  
//初始数组 
void initSort(SqList *L){ 
    L->length = MAXSIZE; 
    L->r[0] = 0; 
    int a[9] = {9,1,5,8,3,7,4,6,2} ; 
    for(int i = 1; i<MAXSIZE; i++){ 
        L->r[i] = a[i-1]; 
    } 
} 
//查询数组 
void searchSort(SqList *L){ 
    for(int i = 1; i < MAXSIZE; i++){ 
        printf("%d", L->r[i]); 
    } 
} 
 
int main(){ 
    SqList *L = new SqList; 
    initSort(L); 
    searchSort(L); 
    printf("/n"); 
    bubbleSort(L); 
    searchSort(L); 
    return 0; 
}

结果为：

冒泡成功！

冒泡排序优化

假如有这个一个序列：[2,1,3,4,5,6,7,8,9]，按照常规的冒泡，会从往上逐渐比较冒泡，但是发现，其实只要交换了1和2的位置，这个序列就有序了，而3,4,5,6,7,8,9的比较都是多余的，因此可以采用这样的思想：
如果该趟冒泡发现没有交换发生（即已经有序了），那么这个序列已经有序了。

public class MaoPaoSort { 
 
    public static void sort(int[] array){ 
        //增加了一个flag 
        boolean flag = true; 
        for(int i = 0; i < array.length && flag; i++){ 
            //每一趟开始前置为false，如果没有交换发生，说明有序 
            flag = false; 
            for(int j = array.length - 1; j > i; j--){ 
                if(array[j] < array[j-1]){ 
                    swap(array, j, j-1); 
                    //有交换，则置为true 
                    flag = true; 
                } 
            } 
        } 
    } 
 
    public static void swap(int[] array, int i, int j){ 
        int temp = array[i]; 
        array[i] = array[j]; 
        array[j] = temp; 
    } 
 
    public static void main(String[] args){ 
        int[] array = new int[]{9,1,5,8,3,7,4,6,2}; 
        sort(array); 
        for(int i = 0; i < array.length; i++){ 
            System.out.println(array[i]); 
        } 
    } 
} 

更多经典算法介绍