数据结构及算法学习----02----选择排序

前沿：

如果您还没有了解基础的冒泡排序，可以点击这里 阅读。

 

介绍：
在介绍选择排序之前，回顾下冒泡排序。如果有N的数据项，冒泡排序需要比较的次数是N(N-1)/2的次数，而交换的次数也和N的平方成正比。因此大O表示法来表示亦即O(N*N)。选择排序改进了冒泡排序，将不必要的交换次数从O(N*N) 减少到O(N)。不幸的是比较次数依然是O(N*N)。 因此，选择排序相对于冒泡排序其实只是减少了交换的次数。

思路：
为了减少冒泡排序总俩俩比较并交换的缺点，选择排序偏向于较少的交换次数。其做法是：从数组最左端(下标为0位置)开始依次比较，找出数组中最小值并将此数据项记下，然后将找到的最小值与数组最左端(下标为0位置)的数据项进行交换。第一次比较完成之后，得到的结果便是数组中最小的数据项已经被移动到了数组最左端(下标为0)。以此类推，第二次找到数组中第二小的结果并与数组下标为1的位置的数据项进行交换。

核心代码：

	public void selectSort() {
		int innerLoop, outterLoop, min;
		double temp;
		for(outterLoop=0;outterLoop<elementCount-1;outterLoop++) {
			min = outterLoop;
			for(innerLoop=outterLoop+1;innerLoop<elementCount;innerLoop++) {
				if(array[innerLoop] < array[min]) {
					min = innerLoop;
				}//end of if
			}//end of for
			//swap them
			temp = array[min];
			array[min] = array[outterLoop];
			array[outterLoop] = temp;			
		}//end of for
	}//end of method

 

 

核心代码说明：
内层for循环，实际上是找最值的过程。假设数组中下标为0位置的数据项是最小值，从下表为1位置开始于这个最小值相比较，如果找到比min更小的值，就将min更新，下次循环比较的过程将用新的最小值比较。内层for循环比较过之后，数组中最小值已经找到，此时，只需要讲这个找到的最小值与数组下标为0的位置交换即可。
外层for循环，实际控制着等待交换的位置，从0开始直到数组的最后一个位置结束。

 

完整代码：

package barry.sort.selectsort;

public class SelectSorter {

	private double[] array;
	private int elementCount;
	
	public SelectSorter(int size) {
		array = new double[size];
		elementCount = 0;
	}//end of constructor
	
	public void insert(double value) {
		array[elementCount] = value;
		elementCount++;
	}//end of method insert()
	
	public void display() {
		for(int i=0;i<elementCount;i++) {
			System.out.print(array[i]+"\t");
		}//end of for
	}//end of method display()
	
	public void selectSort() {
		int innerLoop, outterLoop, min;
		double temp;
		for(outterLoop=0;outterLoop<elementCount-1;outterLoop++) {
			min = outterLoop;
			for(innerLoop=outterLoop+1;innerLoop<elementCount;innerLoop++) {
				if(array[innerLoop] < array[min]) {
					min = innerLoop;
				}//end of if
			}//end of for
			//swap them
			temp = array[min];
			array[min] = array[outterLoop];
			array[outterLoop] = temp;			
		}//end of for
	}//end of method
	
}

 

package barry.sort.selectsort;

public class SelectSorterApp {

	public static void main(String[] args) {
		
		SelectSorter sorter = new SelectSorter(91);
		sorter.insert(-10);	sorter.insert(89);
		sorter.insert(-980);	sorter.insert(45);
		sorter.insert(343);	sorter.insert(32);
		sorter.insert(5563);	sorter.insert(9);
		
		
		System.out.println("\nBefore Sort:");
		sorter.display();
		
		sorter.selectSort();
		
		System.out.println("\nAfter Sort:");
		sorter.display();		
		
	}

}

   

运行结果：

Before Sort:
-10.0	89.0	-980.0	45.0	343.0	32.0	5563.0	9.0	
After Sort:
-980.0	-10.0	9.0	32.0	45.0	89.0	343.0	5563.0	

 

 

总结：
不难发现，选择排序和冒泡排序的区别在于：冒泡排序每两个数据项比较之后就有可能需要交换，然而选择排序时从数组中“选出最小值”然后和特性位置的数据项交换。虽然其时间复杂度依旧和冒泡排序一样，但是交换的次数却明显减少。 因此，当交换数据项所需的时间比比较所需的时间大很多时，选择排序时相当快的。