排序算法之冒泡排序

青旅半醒 2022-09-25 15:23 196阅读 0赞

同样的先上这张图

![Center][]

下面分析交换排序之冒泡排序：

冒泡排序和选择排序很相似，都是遍历一趟把最大的元素放到最后面，但选择排序属于选择排序，而冒泡排序属于交换排序，原因在于冒泡排序在找最大元素的时间，两两比较之后会作交换，这样使得一趟排序下来不仅把最大元素放到了后面，同时让前面的元素也更加有序。

原版的冒泡排序较之选择排序效率上不仅没有提高，反而会更差。因为冒泡排序同样也需要nxn的时间，而且冒泡排序还多了很多交换的时间开销。但是，改进版的冒泡排序会比选择排序效率高些，正是前面那些不断的交换，使得冒泡排序有可能提前退出，而不用做n趟排序。

冒泡排序最差及平均时间复杂度为O(n2)，最好情况只需要一趟排序，时间复杂度为O(n)。

冒泡排序空间复杂度为O(1)。

冒泡排序在交换过程中只有前面元素大于后面元素才会作交换，所以相同元素的相对位置不会被破坏，因此它是稳定的。

AS代码：

/**
    		 * 冒泡排序
    		 * 外层循环标记已经排好序的个数
    		 * 内层循环遍历前面未排序的元素，两两比较做交换，把最大元素换到最后
    		 */
    		private function BubbleSort(arr:Array):void{
    			var finish:Boolean=true;
    			var temp:Number;
    			for(var i:int=0;i<arr.length-1;i++){
    				for(var j:int=1;j<arr.length-i;j++){
    					if(arr[j-1]>arr[j]){
    						temp=arr[j-1];
    						arr[j-1]=arr[j];
    						arr[j]=temp;
    						finish=false;
    					}
    				}
    				if(finish){
    					break;
    				}
    			}
    		}

C++代码

/*
    * 冒泡排序
    * 最好O(n),最坏及平均O(n2)
    * O(1)
    * 稳定
    */
    template <typename T>
    void SortHelp<T>::bubbleSort(T l[], int length) {
    	bool bSwap ;
    	for (int i = 0; i < length; i++)
    	{
    		bSwap = false;
    		for (int j = 0; j < length - i - 1; j++)
    		{
    			if (l[j] > l[j + 1])
    			{
    				l[j] += l[j + 1];
    				l[j + 1] = l[j] - l[j + 1];
    				l[j] = l[j] - l[j + 1];
    				bSwap = true;
    			}
    		}
    		if (!bSwap)
    		{
    			break;
    		}
    	}
    }

总结，冒泡排序平均及最坏时间复杂度为O(n2)，最好时间复杂度为O(n)，空间复杂度为O(1)，稳定。

[Center]: /images/20220717/92563e7be06d41d4b48640bf30571bf2.png