选择排序

1、选择排序

表现最稳定的排序算法之一，因为无论什么数据进去都是O(n2)的时间复杂度，所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。理论上讲，选择排序可能也是平时排序一般人想到的最多的排序方法了吧。
选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2、时间复杂度

最佳情况：T(n) = O(n) 最差情况：T(n) = O(n^2) 平均情况：T(n) = O(n^2)

3、动态演示

Image text

4、算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
package sort;

public class SelectionSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [] a= {99,45,67,12,84,59,32};
		selectionSort(a);
		printArr(a);
	}
	
	public static void selectionSort(int [] arr) {
		//选择小的，从小排到大
		int min;//min记录最小值的下标
		
		for(int i=0;i<arr.length-1;i++) {//比arr.length-1趟
			min=i;
			for(int j=i;j<arr.length;j++) {
				if(arr[j]<arr[min]) {
					min=j;//记录下标
				}
			}
			
			//把最小的排到数组前
			int temp=arr[i];
			arr[i]=arr[min];
			arr[min]=temp;			
		}
	}
	
	public static void printArr(int [] a) {
		for(int i=0;i<a.length;i++) {
			System.out.print(a[i]+" ");
		}
	}
}