冒泡排序

冒泡排序将序列 L 分成两个部分，前面为未排序的序列L1，后面为已经排序的序列L2，每次都将 L1 最大的元素排到后面L2 前面去，是一种稳定的排序算法。其排序方案是：

从数组第一位开始，比较相邻两个元素，通过交换将大的元素排到后边去。这样操作，每执行一轮，都会将未排序的列表中的最大的元素排到后面。

复杂度分析：

最好的情况是执行了一轮，所有元素都是有序的，没有交换过元素，时间复杂度为 $O (1)$

最坏的情况是倒序序列，执行了 n-1 轮， $n (n - 1) / 2$ 次，时间复杂度为 $O ()$

时间复杂度： $O ()$
空间复杂度： $O (1)$

注意下面的代码，添加了一个标志位 flag, 若是某一轮执行后 flag = false, 表示该轮没有交换过元素，则说明剩下的数据已经是有序的，不用往下执行了，退出循环。

Array.prototype.bubbleSort = function () {
	var arr = this.slice(0);

	function swap(i, j) {
		var temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}

	function sort() {
		var len = arr.length;
		for (var i = 0; i < len - 1; i++) {
      flag = false;
			for (var j = 0; j < len - 1 - i; j++) {
				if (arr[j] > arr[j + 1]) {
          swap(j, j + 1);
          flag = true;
        }
			}

      if (!flag) {
        break;
      }
		}
	}

	sort();

	return arr;
};

var arr = [2, 1, 2, 3, 5, 1, 6];

console.log(arr.bubbleSort());

冒泡排序 ​

冒泡排序