选择排序

 

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

 

        算法描述

        比如在一个长度为N的无序数组中，在第一趟遍历N个数据，找出其中最小的数值和第一个元素交换，第二趟遍历剩下的N-1个数据，找出其中最小的数值和第二个元素交换......第N-1趟遍历剩下的2个数据，找出其中最小的数值与第N-1个元素交换，至此选择排序完成。

 

        常见的选择排序细分为简单选择排序，树形选择排序（锦标赛排序）、堆排序。本文仅介绍简单选择排序。

 

        以下为简单选择排序的存储状态，其中大括号内为无序区，大括号外为有序序列：

        初始序列：{ 49 27 65 97 76 12 38 }

        第1趟：   12 { 27 65 97 76 49 38 } //找出最小元素12与第一元素49交换：

        第2趟：   12 27 { 65 97 76 49 38 } //27不动

        第3趟：   12 27 38 { 97 76 49 65 } //65与38交换

        第4趟：   12 27 38 49 { 76 97 65 } //97与49交换

        第5趟：   12 27 38 49 65 { 97 76 } //65与76交换

        第6趟：   12 27 38 49 65 76 97     //97与76交换,排序完成

 

        Java代码实现如下

	private static void selectSort(int[] a) {
		
		for(int i = 0; i<a.length-1;i++){
			int min = i;
			for(int j = i+1;j<a.length;j++){ //找到最小的
				if(a[j]<a[min])
					min = j;
			}
			//将最小的放到i的位置上；
			swap(i,min,a);
			System.out.print("第"+(i+1)+"趟选择排序：");
			print(a);
			System.out.println();
		}
		//排完序后；
		print(a);
	}
	
	private static void swap(int i,int j,int[] arr){
		int temp = arr[i];
		arr[i] = arr[j];
		arr[j] = temp;
	}
	private static void print(int[] a) {
		for(int i:a)
			System.out.print(i+" ");
		
	}

      

       选择排序的另一种排序变种如下：

        

public class SelectSort {
	
	public static void main(String[] args) {
		int a[] = {1,2,6,9,3,8,5,4,0,7};
		selectSort(a);
	}

	/**
	 * 选择排序
	 *   基本思想：1.从i~a.length中选择一个最小的放在i的位置
	 *          2.以此迭代
	 *          3.i从0开始；          
	 * @param a
	 */
	private static void selectSort(int[] a) {
		for(int i=0;i<a.length;i++){
			//找到最小
			for(int j=i+1;j<a.length;j++){
				if(a[i]>a[j]){
					int temp = a[i];					
					a[i] = a[j];
					a[j] = temp;
				}
			}
			
			System.out.print("  第"+i+"趟选择排序：");
			print(a);
		}
	}
	
	private static void print(int[] a) {
		for(int i:a)
			System.out.print(i+" ");
		System.out.println();
	}
}

        上述选择排序就是：

 

              第 一次选择排序的过程如下（排行第0个元素，去上面排序中的i=0）：

                该选择排序就是每一次排序的每次比较都要交换元素；

 

       算法分析

       通过以上代码我们知道简单选择排序的算法复杂度为：平均时间复杂度：O(n2)

 

       空间复杂度：O(1)  (用于交换和记录索引)

 

       稳定性

       举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。