冒泡排序(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]); 
        } 
    } 
} 

更多经典算法介绍

发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

散列(Hash)建立和查找(面试常考)详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。