排序算法-冒泡排序-编程思维

原理

  1. 默认按照升序的规则排序。
  2. 相邻元素依次比较,相邻之间的元素,如果前一个元素比后一个元素大就交换两个元素的位置。
  3. 每循环比较一次,就可以确定数组里面最大的一个元素,把该元素放至末尾。
  4. 重复2,3操作,每次末尾就会得到一个最大的元素,直至只剩下一个元素为止。

图示

代码演示

public static void Sort(int[] array)
{
    for(int i = 0; i < array.Length - 1; i++)
    {
        for(int j = 0; j < array.Length - i - 1; j++)
        {
            if(array[j] > array[j + 1])
            {
                var temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    }
}   

优化

其实冒泡排序是可以优化的,这种情况就是当在一次循环比较中,没有产生一次数据的换位,说明当前数组的数据已经是从小到大排好序了,就不需要再次循环比较了。
具体代码实现如下:

public static void Sort(int[] array)
{
  for(int i = 0; i < array.Length - 1; i++)
  {
      bool flag = false;
      for(int j = 0; j < array.Length - i - 1; j++)
      {
          if(array[j] > array[j + 1])
          {
              var temp = array[j];
              array[j] = array[j + 1];
              array[j + 1] = temp;
              flag = true;
          }
      }
      if (!flag) break;
  }
}

分析

  1. 最好的时间复杂度是O(n),遍历一次就得到结果。
  2. 最坏的时间复杂度是O(n²),需要走n遍并进行n次的换位。

源码地址:https://github.com/woniuSnail/BaseAlgorithm.git

版权声明:本文版权归作者所有,遵循 CC 4.0 BY-SA 许可协议, 转载请注明原文链接
https://www.cnblogs.com/snailZz/p/13690149.html