冒泡排序

基本思想

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

步骤

  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]