阿西河

所有教程

公众号
🌙
阿西河前端的公众号

我的收藏

    最近访问  (文章)

      教程列表

      抓包专区
      测试专区

      冒泡排序

      基本概念

      冒泡排序(Bubble Sort)也是一种简单直观的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端。

      作为最简单的排序算法之一,冒泡排序给我的感觉就像 Abandon 在单词书里出现的感觉一样,每次都在第一页第一位,所以最熟悉。冒泡排序还有一种优化算法,就是立一个 flag,当在一趟序列遍历中元素没有发生交换,则证明该序列已经有序。但这种改进对于提升性能来

      说并没有什么太大作用。

      1. 算法步骤

      比较相邻的元素。如果第一个比第二个大,就交换他们两个。

      对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。

      针对所有的元素重复以上的步骤,除了最后一个。

      持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

      2. 动图演示

      3. 什么时候最快

      当输入的数据已经是正序时(都已经是正序了,我还要你冒泡排序有何用啊)。

      4. 什么时候最慢

      当输入的数据是反序时(写一个 for 循环反序输出数据不就行了,干嘛要用你冒泡排序呢,我是闲的吗)。

      5. JavaScript 代码实现

      function bubbleSort(arr) {
          var len = arr.length;
          for (var i = 0; i < len - 1; i++) {
              for (var j = 0; j < len - 1 - i; j++) {
                  if (arr[j] > arr[j+1]) {        // 相邻元素两两对比
                      var temp = arr[j+1];        // 元素交换
                      arr[j+1] = arr[j];
                      arr[j] = temp;
                  }
              }
          }
          return arr;
      }
      

      6. Python 代码实现

      def bubbleSort(arr):
          for i in range(1, len(arr)):
              for j in range(0, len(arr)-i):
                  if arr[j] > arr[j+1]:
                      arr[j], arr[j + 1] = arr[j + 1], arr[j]
          return arr
      

      7. Go 代码实现

      func bubbleSort(arr []int) []int {
              length := len(arr)
              for i := 0; i < length; i++ {
                      for j := 0; j < length-1-i; j++ {
                              if arr[j] > arr[j+1] {
                                      arr[j], arr[j+1] = arr[j+1], arr[j]
                              }
                      }
              }
              return arr
      }
      

      8. Java 代码实现

      public class BubbleSort implements IArraySort {
      
          @Override
          public int[] sort(int[] sourceArray) throws Exception {
              // 对 arr 进行拷贝,不改变参数内容
              int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);
      
              for (int i = 1; i < arr.length; i++) {
                  // 设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已经完成。
                  boolean flag = true;
      
                  for (int j = 0; j < arr.length - i; j++) {
                      if (arr[j] > arr[j + 1]) {
                          int tmp = arr[j];
                          arr[j] = arr[j + 1];
                          arr[j + 1] = tmp;
      
                          flag = false;
                      }
                  }
      
                  if (flag) {
                      break;
                  }
              }
              return arr;
          }
      }
      

      9. PHP 代码实现

      function bubbleSort($arr)
      {
          $len = count($arr);
          for ($i = 0; $i < $len - 1; $i++) {
              for ($j = 0; $j < $len - 1 - $i; $j++) {
                  if ($arr[$j] > $arr[$j+1]) {
                      $tmp = $arr[$j];
                      $arr[$j] = $arr[$j+1];
                      $arr[$j+1] = $tmp;
                  }
              }
          }
          return $arr;
      }
      

      10. C 语言

      #include <stdio.h>
      void bubble_sort(int arr[], int len) {
              int i, j, temp;
              for (i = 0; i < len - 1; i++)
                      for (j = 0; j < len - 1 - i; j++)
                              if (arr[j] > arr[j + 1]) {
                                      temp = arr[j];
                                      arr[j] = arr[j + 1];
                                      arr[j + 1] = temp;
                              }
      }
      int main() {
              int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
              int len = (int) sizeof(arr) / sizeof(*arr);
              bubble_sort(arr, len);
              int i;
              for (i = 0; i < len; i++)
                      printf("%d ", arr[i]);
              return 0;
      }
      

      11. C++ 语言

      #include <iostream>
      using namespace std;
      template<typename T> //整数或浮点数皆可使用,若要使用类(class)或结构体(struct)时必须重载大于(>)运算符
      void bubble_sort(T arr[], int len) {
              int i, j;
              for (i = 0; i < len - 1; i++)
                      for (j = 0; j < len - 1 - i; j++)
                              if (arr[j] > arr[j + 1])
                                      swap(arr[j], arr[j + 1]);
      }
      int main() {
              int arr[] = { 61, 17, 29, 22, 34, 60, 72, 21, 50, 1, 62 };
              int len = (int) sizeof(arr) / sizeof(*arr);
              bubble_sort(arr, len);
              for (int i = 0; i < len; i++)
                      cout << arr[i] << ' ';
              cout << endl;
              float arrf[] = { 17.5, 19.1, 0.6, 1.9, 10.5, 12.4, 3.8, 19.7, 1.5, 25.4, 28.6, 4.4, 23.8, 5.4 };
              len = (float) sizeof(arrf) / sizeof(*arrf);
              bubble_sort(arrf, len);
              for (int i = 0; i < len; i++)
                      cout << arrf[i] << ' '<<endl;
              return 0;
      }
      

      12. C#

      static void BubbleSort(int[] intArray) {
          int temp = 0;
          bool swapped;
          for (int i = 0; i < intArray.Length; i++)
          {
              swapped = false;
              for (int j = 0; j < intArray.Length - 1 - i; j++)
                  if (intArray[j] > intArray[j + 1])
                  {
                      temp = intArray[j];
                      intArray[j] = intArray[j + 1];
                      intArray[j + 1] = temp;
                      if (!swapped)
                          swapped = true;
                  }
              if (!swapped)
                  return;
          }
      }
      

      13. Ruby

      class Array
        def bubble_sort!
          for i in 0...(size - 1)
            for j in 0...(size - i - 1)
              self[j], self[j + 1] = self[j + 1], self[j] if self[j] > self[j + 1]
            end
          end
          self
        end
      end
      
      puts [22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70].bubble_sort!
      

      14. Swift

      import Foundation
      
      func bubbleSort (arr: inout [Int]) {
          for i in 0..<arr.count - 1 {
              for j in 0..<arr.count - 1 - i {
                  if arr[j] > arr[j+1] {
                      arr.swapAt(j, j+1)
                  }
              }
          }
      }
      
      // 测试调用
      
      func testSort () {
          // 生成随机数数组进行排序操作
          var list:[Int] = []
          for _ in 0...99 {
              list.append(Int(arc4random_uniform(100)))
          }
          print("\(list)")
          bubbleSort(arr:&list)
          print("\(list)")
      }
      

      参考

      目录
      目录