首页 > 代码库 > 冒泡排序的基础知识部分(不含源码)

冒泡排序的基础知识部分(不含源码)

|   版权声明:本文为博主原创文章,未经博主允许不得转载。

 

冒泡排序:

  原理:冒泡排序是重复的比较前后两个数据,将错误的顺序交换过来,每次交换后,就往后挪动一个数据,在比较。直到待排序列重复地进行到没有再需要交换,也就是说待排序列已经排序完成。

  时间复杂度:

  (1).如果待排序列是正序的话,那么待排序列只需要一次扫描,如果该序列的元素数量为n,那么时间复杂度为O(n)。O(n)为最好的时间复杂度。

  (2).如果待排序列不是正序的话,那么待排序列要进行n-1趟扫描,每趟扫描进行n-1次比较。因此时间复杂度为O(n2)。

  示例:(以Q,H,C,Y,P,A,M为例,进行字母的升序排列),见下图

技术分享

  技术分享

  技术分享

技术分享

 技术分享

 技术分享

 技术分享

  当然,上面的排序知识第一趟的排序过程(第一趟的结果为:H,C,Q,P,A,M.Y),要完好的将序列排列好,要经过n-1趟排序, 后面的排序过程就和第一趟的排序一样。

 

  冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较,交换也发生在这两个元素之间。所以,如果两个元素相等,就不需要;如果两个相等的元素没有相邻,那么即使通过前面的两两交换把两个相邻起来,这时候也不会交换,所以相同元素的前后顺序并没有改变,所以冒泡排序是一种稳定排序算法。

 

冒泡排序的基础知识部分(不含源码)