排序算法--冒泡排序_冒泡排序比较次数

首先我们创建一个列表类，将要排序的元素放在一个数组中，便于后期插入和转化

function ArrayList(){
	//属性
	this.array = []
	//方法
	//将数据可以插入到数组中的方法
	ArrayList.prototype.insert = function(item){
		this.array.push(item)
	}
	//toString方法
	ArrayList.prototype.toString = function(){
		return this.array.join('-')
	}
	//交换两个位置的数据(便于在排序中直接使用)
	ArrayList.prototype.swap = function(m,n){
		var temp = this.array[m]
		this.array[m] = this.array[n]
		this.array[n] = temp
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

一.冒泡排序

冒泡排序相对于其他排序运行效率较低，但在排序算法中是最简单的

冒泡排序的思路：

• 对未排序的各元素从头到尾，依次进行两两比较
• 如果左边较大，则两元素交换位置，并依次向右移
• 当第一轮移动到最右端时，最大的数一定被放在最右侧
• 按照这个思路，从最左端重新开始，移动到倒数第二个位置即可
• 依此类推
  

ArrayList.prototype.bubblesort = function(){
	var length = this.array.length
	for(var j = length - 1; j >= 0; j--){
		//第一次：j=length-1,比较到倒数第一的位置
		//第二次：j=length-2,比较到倒数第二的位置
		//...
		for(var i = 0; i < j; i++){
		//第一次进来，i=0,比较第0位和第1位的两个数据
		//最后一次进来，i=length-2,比较length-2和length-1两个数据
			if(this.array[i] > this.array[i+1]){
				this.swap(i,i+1)
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

冒泡排序的效率：

1. 冒泡排序的比较次数：
   假设现有5个数据项，则总共的比较次数为：4+3+2+1
   那么对于N个数据项呢？总共比较次数为：(N-1)+(N-2)+(N-3)+…+1 = N*(N-1) / 2
   那么通过大O表示法可以表示为O(N^2)
2. 冒泡排序的交换次数：
   真实的次数为：N*(N-1) / 2 / 2，因为冒泡排序平均下来可以默认为进行2次比较，交换一次数据，那么通过大O表示法也可以表示为O(N^2)