冒泡排序

冒泡排序是一种交换排序。

交换排序：两两比较待排序的关键字，并交换不满足次序要求的那对数，直到整个表都满足次序要求为止。

算法思想

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。 这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端，故名。

算法原理

冒泡排序算法的运作如下：（从后往前） 比较相邻的元素。如果第一个比第二个大，就交换他们两个。 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。 针对所有的元素重复以上的步骤，除了最后一个。 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较

临近的数字两两进行比较,按照从小到大或者从大到小的顺序进行交换,这样一趟过去后,最大或最小的数字被交换到了最后一位,然后再从头开始进行两两比较交换,直到倒数第二位时结束。

时间复杂度

若文件的初始状态是正序的，一趟扫描即可完成排序。所需的关键字比较次数 和记录移动次数 均达到最小值： ， 。 所以，冒泡排序最好的 时间复杂度为 。 　　若初始文件是反序的，需要进行 趟排序。每趟排序要进行 次关键字的比较(1≤i≤n-1)，且每次比较都必须移动记录三次来达到交换记录位置。在这种情况下，比较和移动次数均达到最大值： 冒泡排序的最坏时间复杂度为 。 综上，因此冒泡排序总的平均时间复杂度为 。

算法稳定性

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

冒泡排序算法的性能

排序类别排序方法时间复杂度空间复杂度稳定性复杂性平均情况最坏情况最好情况交换排序冒泡排序 O(N ²) O(N²)O(N)O(1)稳定简单

 

  代码实现   冒泡算法C# namespace  数组排序 {      class  Program      {          static  void  Main( string [] args)          {              int  temp = 0;              int [] arr = {23, 44, 66, 76, 98, 11, 3, 9, 7};              #region该段与排序无关              Console.WriteLine( "排序前的数组：" );              foreach  (intiteminarr)              {                  Console.Write(item +  "" );              }              Console.WriteLine();              #endregion              for  ( int  i = 0; i < arr.Length - 1; i++)              {                  #region将大的数字移到数组的arr.Length-1-i                  for  ( int  j = 0; j < arr.Length - 1 - i; j++)                  {                      if  (arr[j] > arr[j + 1])                      {                          temp = arr[j + 1];                          arr[j + 1] = arr[j];                          arr[j] = temp;                      }                  }              #endregion              }              Console.WriteLine( "排序后的数组：" );              foreach  ( int  item  in  arr)              {                  Console.Write(item+ "" );              }              Console.WriteLine();              Console.ReadKey();          }      } }

举例说明

例子为从小到大排序,

原始待排序数组| 6 | 2 | 4 | 1 | 5 | 9 |

 

第一趟排序(外循环)

第一次两两比较6 > 2交换(内循环)

交换前状态| 6 | 2 | 4 | 1 | 5 | 9 |

交换后状态| 2 | 6 | 4 | 1 | 5 | 9 |

 

第二次两两比较,6 > 4交换

交换前状态| 2 | 6 | 4 | 1 | 5 | 9 |

交换后状态| 2 | 4 | 6 | 1 | 5 | 9 |

 

第三次两两比较,6 > 1交换

交换前状态| 2 | 4 | 6 | 1 | 5 | 9 |

交换后状态| 2 | 4 | 1 | 6 | 5 | 9 |

 

第四次两两比较,6 > 5交换

交换前状态| 2 | 4 | 1 | 6 | 5 | 9 |

交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

 

第五次两两比较,6 < 9不交换

交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |

交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

 

第二趟排序(外循环)

第一次两两比较2 < 4不交换

交换前状态| 2 | 4 | 1 | 5 | 6 | 9 |

交换后状态| 2 | 4 | 1 | 5 | 6 | 9 |

 

第二次两两比较,4 > 1交换

交换前状态| 2 | 4 | 1 | 5 | 6 | 9 | 交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

 

第三次两两比较,4 < 5不交换

交换前状态| 2 | 1 | 4 | 5 | 6 | 9 | 交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

 

第四次两两比较,5 < 6不交换

交换前状态| 2 | 1 | 4 | 5 | 6 | 9 |

交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

 

第三趟排序(外循环)

第一次两两比较2 > 1交换

交换后状态| 2 | 1 | 4 | 5 | 6 | 9 |

交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

 

第二次两两比较,2 < 4不交换

交换后状态| 1 | 2 | 4 | 5 | 6 | 9 | 交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

 

第三次两两比较,4 < 5不交换

交换后状态| 1 | 2 | 4 | 5 | 6 | 9 | 交换后状态| 1 | 2 | 4 | 5 | 6 | 9 |

 

第四趟排序(外循环)无交换

第五趟排序(外循环)无交换

 

排序完毕,输出最终结果1 2 4 5 6 9

 

转载于:https://www.cnblogs.com/nxxshxf/p/5150339.html

相关资源：数据结构—成绩单生成器