算法回顾之六：选择排序

算法回顾系列第六篇：选择排序

-----------------------------------------

选择排序

 

基本原理：

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最前（或最后），直到全部待排序的数据元素排完。

 

程序实现：

public void sort(int[] data) {
		//i代表已经排序的元素个数.
	    for(int i=0; i<data.length; i++){
	    	//lowIndex代表最小元素的位置.
	    	int lowIndex=i;
	        for(int j=data.length-1; j>i; j--){
	          //j从后向前将每个元素的值与最小元素进行比较,如果比最小元素还小,则设置该位置为最小元素
	        	if (data[j] < data[lowIndex]){
	                 lowIndex=j;
	            }
	        }
	        //交换最小元素位置
	        swap(data,i,lowIndex);
	        System.out.println(Arrays.toString(data));
	    }
	}
	
	public void swap(int[] data,int first,int second){
		int temp;
		temp=data[first];
		data[first]=data[second];
		data[second]=temp;
	}

上面程序中：

遍历所有元素，并将已排序元素放在了最前。

每趟排序时，最小元素坐标默认为已排序元素的下一个元素(即待排序元素，初始为0)。

然后从后向前遍历每个元素并与最小元素进行比较，如果小于最小元素，则修改最小元素坐标位置。

每趟排序结束时，将最小元素与当前待排序元素交换位置，完成一趟排序。

重复以上步骤直到全部元素都排完序。

 

性能分析：

时间复杂度O(n^2)

 

空间复杂度：1。

稳定性：不稳定