Algorithm

排序算法之选择排序

排序算法之选择排序

在未排序序列中找到最小元素，并与待排序列的首位进行交换。
选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。

选择排序的时间复杂度为O(n^2) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class SelectSort {
	public static void selectSort(int [] arr) {
		if(arr.length == 0 || arr == null)
			return ;
		int minIndex = 0;
		for(int i = 0; i < arr.length-1; i++) {
			minIndex = i;
			for (int j = i+1; j < arr.length-i-1; j++) {
				if (arr[minIndex] > arr[j])
					minIndex = j;
			}
			if(minIndex != i)
				swap(arr, i, minIndex);
		}
	}

	public void swap(int[] arr, int a, int b) {
		int tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
	}
}