排序算法

假设存在一组棒球队员， 现在需要对这组队员排序。


冒泡排序(Bubble sort)

• 遵循的规则：

1.比较两个队员
2.如果左边的队员高， 则两队员交换位置
3.向右移动一个位置， 比较下面2个队员

• 冒泡排序的Java代码：

public void bubbleSort() {
	int out, in;
	for(out = nElems -1; out > 1; out --) {  // outer loop(backward)
		for (in = 0; in < out; in ++) {		 // inner loop(forward)
			if(a[in] > a[in + 1] {			 // out of order?
				swap(in, in+1);				 // swap them
			}
		}
	}
} // end bubbleSort()

附:

private void swap(int one, int two) {
	long temp = a[one];
	a[two] = a[one];
	a[one] = temp;
}

• 不变性：

在bubble.java程序中，不变性是指out右边的所有数据项为有序。 在算法的整个运行过程中
这个条件始终未真。

• 冒泡排序的效率：

算法做了约　Ｎ平方／２　次比较　（忽略减1，　不会有很大的差别，特别是当Ｎ很大时）
如果数据是随机的，那么大约有一半数据需要交换，　则交换的次数为Ｎ平方／４。
交换和比较次数都和　Ｎ平方　成正比，因为常数不算在大Ｏ表示法中，　可以忽略２和４，　
并且认为冒泡排序需要Ｏ（Ｎ平方）时间级别。无论何时，　只要看到一个循环里还有另一个循环，　例如在冒泡排序和后面说的其它排序算法中，都可以怀疑为时间复杂度为（Ｎ平方）级。


选择排序(Ｓｅｌｅｃｔ sort)

• 遵循的规则：

    进行选择排序就是把所有的队员扫描一遍，从中找出（或者说选择，这正是这个排序名字的由来）
最矮的队员， 这个队员与最左端的队员交换位置，即0号位置。现在最左端的队员已经是有序的了，不需要交换位置了。 注意， 在这个算法中有序的队员都排列在队列的左边（较小的下标值）， 而在冒泡排序中是排在队列右边的。
    再次扫描队员队列时， 就是从1号位置开始，还是寻找最矮的， 然后和1号队员的位置交换。 这个过程一直持续到所有的队员都排定。

• 选择排序的Java代码：

public void selectionSort() {
	int out, in, min;
	for(out = 0; out < nElems -1; out ++) {     // outer loop
		min = out;								// minimum
		for(in = out + 1; in < nElems; in++)	// inner loop
			if(a[in] < a[min])					// if min greater
				min = in;						// we have a new min
		swap(out, min);							// swap them
	}
}

附：

private void swap(int one, int two) {
	long temp = a[one];
	a[two] = a[one];
	a[one] = temp;
}

• 不变性：

下标小于或等于out的位置项的数据项总是有序的。

• 选择排序的效率：

选择排序和冒泡排序执行了相同次数的比较， 但只执行了N次交换。 N值很大时， 比较次数是主要的，
所以结论是选择排序和冒泡排序一样运行了O（N平方）时间。
当N值较小时， 特别是当交换的时间级比比较的时间级大的多时， 选择排序是相当快的。


插入排序（Insert Sort）

• 遵循的规则：

局部有序:
此时， 在队员的中间有一个作为标记的队员。 在这个作为标记的队员左边的队员都是有序的 。这意味着这一部分人是按顺序排列的了；每个人都比他/她左边的人高。 然而这些队员在队列中的最终位置还没有确定， 因为当没有排序的队员插入到他们中间时， 他们的位置还要变化。
注意： 局部有序在冒泡排序和选择排序中是不会出现的。 在这两个算法中， 一组数据项在某个位置是完全有序的； 在插入排序中， 一组数据仅仅是局部有序的。

作为标记的队员， 称为“被标记”的队员，他和他右边的所有队员都是未排序的。下面要做的就是在(局部)有序组中插入被标记的队员。 然而要做到这一点，需要把部分已标记的队员右移以腾出空间。 为了提供移动所需的空间，就先让被标记的队员出列。 （在程序中，这个数据项被存储在一个临时变量中。）

现在移动已经排过序的队员来腾出空间。 将局部有序中的最高的队员移动到被标记为局部有序队员的位置，次高的队员移动到原先最高的队员的位置，依此类推。

这个移动过程什么时候结束呢？假设你和被标记的队员一起向队列的左端移动。 在每个位置上，队员都向右移动一个单位，同时， 被标记的队员和下一个要移动的队员比较身高。 当把最后一个比被标记的队员身高还高的队员移位之后，这个移动过程就结束了。 最后一次移出空位的位置，就是被标记队员应该插入的位置。

现在局部有序的部分里多了一个队员，而未排序的部分里少了一个队员。重复这个操作，直到所有未排序的队员都插入(插入排序由此得名)到局部有序队列中的合适位置。

• 插入排序的Java代码：

public void insertionSort() {
	int out, in;
	for (out = 1; out < nElems; out ++) { 			// out is dividing line 
		long temp = a[out];							// remove marked item
		int = out; 									// start shifts at out
		while(in > 0 && a[in - 1] > = temp) {		// until one is smaller
			a[in] = a[in - 1];						// shift item right
			-- in;									// go left one postion
		}											// end for
		a[in] = temp;								// end insertionSort
	}
}

• 不变性：

在每趟结束时， 在将item位置的项插入后，比out变量下标号小的数据项都是局部有序的 。

• 插入排序的效率：

复制的次数大致等于比较的次数。 然而一次复制和一次交换的时间耗费不同， 所以相对于随机数据这个算法比冒泡排序快一倍，比选择排序略快。