算法之冒泡排序

• 一：基本概念

  冒泡排序(Bubble Sort)，又被称为气泡排序或泡沫排序；它是一种比较简单的排序算法，按待排序序列的先后顺序，依次比较相邻的两个数，将小数放在前面，大数放在后面。（若二者是升序，则不做任何操作，否则交换两数即可）

• 二：图文说明

我们先分析第一趟排序：
1. 依次从前往后走，a[0]>a[1],则进行交换，交换之后的结果为a[0]=1,a[1]=5；
2. 接着继续进行比较，a[1]<a[2],则不进行交换；
3. 接着继续进行比较，a[2]>a[3],则进行交换，交换之后的结果为a[2]=-2,a[3]=12；
4. 接着继续进行比较，a[3]>a[4],则进行交换，交换之后的结果为a[3]=-1,a[4]=12；

于是，第一趟排序完成之后，数列{5,1,12,-2,-1}变成了{1,5,-2,-1,12},此时，数列末尾的数最大。

根据这种方法，对数列依次进行排序，即得排序完之后的升序结果！

• 三：代码实现

  1. C语言实现

  #include <stdio.h>
  /*
      冒泡排序 
  */
  void show(int arr[],int len);//打印出数组 
  void swap(int arr[],int i,int j); //交换数组中的两个位置 
  void bubbleSort(int arr[],int len);//冒泡排序算法 
  
  int main(void)
  {
      int arr[] = {5, 1, 12, -2, -1};
      int len = sizeof(arr)/sizeof(*arr);
      printf("待排序数组为:\n");
      show(arr,len);
      bubbleSort(arr,len);
      printf("排序之后的数组为:\n");
      show(arr,len);
      return 0;
  }
  
  void show(int arr[],int len)
  {
      int i;
      for(i=0;i<len;i++)
      {
          printf("%d ",arr[i]);
      }
      printf("\n");
  }
  
  void swap(int arr[],int i,int j)
  {
      int temp;
      temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
  }
  
  void bubbleSort(int arr[],int len)
  {
      int i = 0;
      int j = 0;
      int change = 1;
      for(i=0; (i<len) && change; i++)
      {
          change = 0;
          for(j=len-1; j>i; j--)
          {
              if( arr[j] < arr[j-1] )
              {
                  swap(arr, j, j-1);
                  change = 1;
              }
          }
      }
  }
  

  2.JAVA实现

  package com.data;
  import java.util.Arrays;
  
  /**
   * @author mxf
   * 冒泡排序
   */
  public class BubbleSort {
      public static void main(String[] args) {
          int[] arr = {5, 1, 12, -2, -1};
          //输出排序前的数组
          System.out.println("排序前的数组为:"+Arrays.toString(arr));
          int swapped = 1;
          //排序
          for(int i=0;i<arr.length-1 &&swapped!=0;i++){//外层循环控制排序趟数
              for(int j=0;j<arr.length-1-i;j++){//内层循环控制每一趟中的排序次数
                  swapped = 0;
                  if(arr[j]>arr[j+1]){//如果前面的数大于后面的数则进行交换
                      int temp = arr[j];
                      arr[j] = arr[j+1];
                      arr[j+1] = temp;
                      swapped = 1;
                  }
              }
          }
          //输出排序后的数组
          System.out.println("排序后的数组为:"+Arrays.toString(arr));
      }
  }
  
  

• 四：冒泡排序的时间复杂度和稳定性

  1. 冒泡排序的时间复杂度
  • 冒泡排序的时间复杂度是O(NN)。
    假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？N-1次！因此，冒泡排序的时间复杂度是O(NN)。
  2. 冒泡排序稳定性
  • 冒泡排序是稳定的算法，它满足稳定算法的定义。冒泡排序就是把小的元素往前调（或者把大的元素往后调）。注意是相邻的两个元素进行比较，而且是否需要交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把它们俩再交换一下。如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个元素相邻起来，最终也不会交换它俩的位置，所以相同元素经过排序后顺序并没有改变。