简单（直接）选择排序

要点

• 时间复杂度-平均情况：O(n²)；最好情况：O(n²)；最坏情况：O(n²)。
• 辅助空间O(1)。
• 简单选择排序是一种稳定的排序方式。
• 基本思想：每一趟在n-i+1(i=1,2,…,n)个记录中选取关键字最小的记录作为有序序列的第i个记录。

基本思路（一趟）

• 定义一个哨兵，记录当前待排序列的最小关键字的坐标，默认为待排序列的首位；
• 遍历待排序列，发现小于哨兵指向的关键字的值，则哨兵变为新发现的关键字的坐标；
• 遍历完成后，哨兵与默认坐标（即待排序列的首位）比较，若不同，则交换默认坐标的关键字和哨兵指向的关键字。此时实现当前待排序列的最小值置于待排序列的首位，在下一趟排序时成为有序序列的末位。

	public void selectSort(int[] nums) {
		int min; // 哨兵
		int len = nums.length; // 数组长度
		for (int i = 0; i < len; i++) {
			min = i; // 默认哨兵为待排序列首位
			for (int j = i + 1; j < len; j++) {
				if (nums[min] > nums[j]) { // 出现更小的关键字，修改哨兵的值
					min = j;
				}
			}
			if (i != min) { // 哨兵发生变动，则交换新位置与默认位置的关键字
				swap(nums, i, min);
			}
		}
	}

	public void swap(int[] nums, int i, int min) {
		int temp;
		temp = nums[i];
		nums[i] = nums[min];
		nums[min] = temp;
	}