JavaScript 实现 -- 冒泡排序

冒泡排序

冒泡排序（Bubble Sort）也叫气泡排序、泡沫排序，是一种比较简单的排序算法。

它通过遍历数组，比较相邻的两个元素，如果前一个元素比后一个元素大，则交换它们的位置，这样第一次遍历后数组的最大元素就排在了数组的末尾。采用相同的方法再次遍历，直至整个数组都有序为止。

代码实现

理解完冒泡排序的原理，我们再来看看实现代码：

		Array.prototype.bubbleSort = function(){
		    for(let i = 0; i < this.length - 1; i++){
		    	//j < length - 1 - i 内层循环只循环未排序的数组元素
		        for(let j = 0; j < this.length - 1 - i;j++){
		            if(this[j] > this[j+1]){
		            	//交换数组元素
		                [this[j], this[j+1]] = [this[j+1], this[j]];
		            }
		        }
		    }
		} 
        const arr = [6,5,4,3,2,1];
        arr.bubbleSort(); 
        console.log(arr);   

控制台输出：

冒泡排序过程

时间复杂度

冒泡排序有两层循环，所以其时间复杂度为O(n^2)；

算法稳定性

冒泡排序是稳定的算法；

即在数组中存在a[i]=a[j]，若在排序之前，a[i]在a[j]前面；并且排序之后，a[i]仍然在a[j]前面。