直接选择排序

直接选择排序

算法描述：

所谓直接选择排序,就是假设有一个长度为n的数组Array,第一次从Array[0]~Array[n-1]中选取最小值,与Array[0]交换,第二次从Array[1]~Array[n-1]中选取最小值,与Array[1]交换,...,第i次从Array[i-1]~Array[n-1]中选取最小值,与Array[i-1]交换,以此类推,总共通过n-1次,得到一个按排序码从小到大排列的有序序列.
例如:
初始状态 [ 8 3 2 1 7 4 6 5 ]   8 -- 1
第一次 [ 1 3 2 8 7 4 6 5 ]      3 -- 2
第二次  [ 1 2 3 8 7 4 6 5 ]     3 -- 3
第三次  [ 1 2 3 8 7 4 6 5 ]     8 -- 4
第四次  [ 1 2 3 4 7 8 6 5 ]     7 -- 5
第五次  [ 1 2 3 4 5 8 6 7 ]     8 -- 6
第六次  [ 1 2 3 4 5 6 8 7 ]     8 -- 7
第七次  [ 1 2 3 4 5 6 7 8 ]   
排序完成

时间复杂度：O(n*n)，

空间复杂度：O(1) 

java实现

public static void selectSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			int index = i;
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] < arr[index]) { //遍历查询最小值的index
					index = j;
				}
			}
			if (i != index) { //如果i与index不同，需要交换i与index的值
				swap(arr, i, index);
			}
		}
	}

	public static void swap(int[] arr, int i, int index) {
		int tmp = 0;
		tmp = arr[i];
		arr[i] = arr[index];
		arr[index] = tmp;
	}

github地址：https://github.com/xckNull/Algorithms-introduction.git