• 冒泡排序
    • 基本思想
    • 步骤
    • By C++
    • By Golang
    • 排序过程

    冒泡排序

    基本思想

    • 比较相邻两个元素，如果第一个比第二个大，就交换两者的顺序
    • 对每一对相邻的元素做同样的操作，从最后一对到第一对，每一趟结束最小的元素会排在第一个（即冒泡）
    • 从未排序的元素开始循环做以上操作，直到排序完成

    步骤

    1. 第一层循环: i=0; i<(len-1); i++
    2. 第二层循环: j=len-1; j>i; j—
    3. 比较相邻两个元素: list[j-1]和list[j]
    4. 如果前者比后者大，就交换顺序: list[j-1], list[j] = list[j], list[j-1]

    By C++

    1. #include <stdio.h>
    2. #define MaxSize 100
    4. typedef int KeyType;        /*关键字类型*/
    6. typedef char ElemType[10];    /*其他数据项类型*/
    8. typedef struct 
    9. {    
    10.     KeyType key;               /*关键字域*/
    11.     ElemType data;             /*其他数据域*/
    12. } LineList;                    /*线性表元素类型*/
    14. void BubbleSort(LineList R[],int n)
    15. {
    16.     int i,j,exchange;
    17.     LineList tmp;
    18.     for (i=0;i<n-1;i++) 
    19.     {    exchange=0;
    20.         for (j=n-1;j>i;j--)    /*比较,找出最小关键字的记录*/
    21.             if (R[j].key<R[j-1].key)       
    22.             {    tmp=R[j];  /*R[j]与R[j-1]进行交换,将最小关键字记录前移*/
    23.                 R[j]=R[j-1];
    24.                 R[j-1]=tmp;
    25.                 exchange=1;
    26.             }
    27.         if (exchange==0)     /*本趟未发生交换时结束算法*/
    28.             return;
    29.     }
    30. }
    32. void main()
    33. {
    34.     LineList R[MaxSize];
    35.     KeyType a[]={75,87,68,92,88,61,77,96,80,72};
    36.     int n=10,i;
    37.     for (i=0;i<n;i++)
    38.         R[i].key=a[i];
    39.     printf("排序前:");
    40.     for (i=0;i<n;i++)
    41.         printf("%3d",R[i].key);
    42.     printf("\n");
    43.     BubbleSort(R,n);
    44.     printf("排序后:");
    45.     for (i=0;i<n;i++)
    46.         printf("%3d",R[i].key);
    47.     printf("\n");
    48. }

    By Golang

    1. package main
    3. import (
    4.     "fmt"
    5. )
    7. // 冒泡排序，从小到大
    8. func bubbleSort(list []int) []int {
    9.     for i := 0; i < len(list)-1; i++ {  
    10.         for j := len(list) - 1; j > i; j-- {  // 从最后两个元素开始比较
    11.             if list[j-1] > list[j] { // 相邻元素对比
    12.                 list[j-1], list[j] = list[j], list[j-1] // 如果后者比前者小，就交互位置
    13.             }
    14.         }
    15.         fmt.Println("第", i+1, "趟：", list)
    16.     }
    17.     return list
    18. }
    20. func main() {
    21.     list := []int{75, 87, 68, 92, 88, 61, 77, 96, 80, 72}
    22.     fmt.Println("初始序列:", list)
    23.     result := bubbleSort(list)
    24.     fmt.Println("最终结果:", result)
    25. }

    排序过程

    1. 初始序列: [75 87 68 92 88 61 77 96 80 72]
    3. 第 1 趟： [61 75 87 68 92 88 72 77 96 80]
    4. 第 2 趟： [61 68 75 87 72 92 88 77 80 96]
    5. 第 3 趟： [61 68 72 75 87 77 92 88 80 96]
    6. 第 4 趟： [61 68 72 75 77 87 80 92 88 96]
    7. 第 5 趟： [61 68 72 75 77 80 87 88 92 96]
    8. 第 6 趟： [61 68 72 75 77 80 87 88 92 96]
    9. 第 7 趟： [61 68 72 75 77 80 87 88 92 96]
    10. 第 8 趟： [61 68 72 75 77 80 87 88 92 96]
    11. 第 9 趟： [61 68 72 75 77 80 87 88 92 96]
    13. 最终结果: [61 68 72 75 77 80 87 88 92 96]