排序算法（二）选择排序

0. 简介

• 选择排序 与 冒泡排序本质是一样的，都是每次从未排序的数组片段中选取一个相对最大（或最小）值，并连续执行有限次（具体次数取决于数组长度）。
• 对于长度为 n 的数组，需要执行 n - 1 次选择（一次选取一个相对最大或最小值）。例如对长度为 n 的数组进行递增排序，（一般）从该数组的第一个元素位置（即数组头部）开始，
  第一次选择操作，为数组中下标为 0 的位置，在下标为 0 到 n - 1 的范围中选取一个相对最小值，即将 array[0] 与其后面的所有元素依次比较，当所有比较操作完成，会确认一个最小元素的下标，然后可能将 array[0] 和 该下标对应的元素值进行互换，第一次选择操作完毕。
  第二次选择操作，为数组中下标为 1 的位置，在下标为 1 到 n - 1 的范围中选取一个相对最小值，即将 array[1] 与其后面的所有元素依次比较，当所有比较操作完成，会确认一个最小元素的下标，然后可能将 array[1] 和 该下标对应的元素值进行互换，第二次选择操作完毕。
  最后一次选择操作，为数组中下标为 n - 2 的位置（倒数第二个位置），在下标为 n - 2 到 n - 1 的范围中选取一个相对最小值，即将 array[n - 2] 与其后面的元素 array[n - 1] 进行比较，确认最小元素的下标，然后可能将 array[n -2] 和 array[n - 1] 的元素值进行互换。排序完毕。
  （注意：每次选择操作中，在完成和数组最后一个元素的比较后，所有的比较操作才宣告结束）

数组的结构相对简单，但是在操作数组的过程中，有时却很容易出错且不易察觉

1. 长度为 n 的数组 ‘int[] array = new int[n];’ 中，<第 i 个元素> 与 <下标为 i 的元素> 的区别，我们来理清其中的概念，一个个来：
   1. 首先，长度为 n 的数组，其中 n 表示可以将数组中的每一个元素从 1 开始编号，而最大的编号为 n，即数组中元素的个数。通常从数组的第一个元素即 array[0] 开始依次编号，所以下标为 0 的元素 array[0] 其编号为 1，可以发现： ‘元素编号’ = ‘元素下标’ + 1，所以，下标为 i 的元素其编号为 ‘i + 1’，而编号为 m 的元素其下标则为 ‘m - 1’。
   2. 所以，‘第 i 个元素’ 等价于 ‘下标为 i - 1 的元素’。而 ‘下标为 i 的元素’ 则等价于 ‘编号为 i + 1 的元素’，当然以上这些都很显然。下面是我想强调的重点：
   3. 让我们来分别计算 ‘第 i 个元素’ 和 ‘下标为 i 的元素’ 它们后面还有多少个元素。
      1. 先计算 ‘第 i 个元素’ 后面还有多少个元素。显然，其后面还有 n - i 个元素，因为我们知道数组中的元素从 array[0] 开始依次被编号，且编号范围为 ‘1 到 n’，而上面的结果 ‘n - i’ 就是基于这个范围 ‘1 到 n’ 计算出来的，这个范围从 1 开始取值。
      2. 再来计算 ‘下标为 i 的元素’ 后面还有多少个元素。这个好像一时没有头绪啊。方法一：我们知道，数组的下标从 0 开始，直到 n - 1 为止（这是一个等差数列），所以将最后一个元素的下标 减去 下标 i 即得结果为：（n - 1）- i 则等于（n - 1 - i），注意，该结果是基于这个范围： ‘0 到 （n - 1）’计算出来的，这个范围从 0 开始取值。方法二：可以将 ‘下标为 i 的元素’ 转换为 ‘编号为 i + 1 的元素’，则结果为：n - （i + 1）则等于（n - i - 1）。可以发现两个方法计算的结果一致（当然这并不复杂）。综上，范围 ‘0 到 n - 1’对应于数组下标，可直接用于索引，而范围 ‘1 到 n’ 对应于数组元素的序号，将其减一运算则可用于索引，这是编号与下标的对应关系。我想强调的是如果将这两种范围应用于多层 for 循环时，就可能会轻易出现问题：下面是一个 for 循环（这个 for 循环执行 n - 1 次，i 取值从 0 开始，范围为：0 到 n - 2）：

for(int i = 0;i < n - 1;i++){
}

其等价于（同样执行 n - 1 次，但是 i 的取值从 1 开始，范围为：1 到 n - 1）：

for(int i = 1;i <= n - 1;i++){
}

其等价于（同样执行 n - 1 次，但是 i 的取值从 1 开始，范围为：1 到 n - 1）：

for(int i = 1;i < n;i++){
}

上面的 3 个 for 循环都互不相同，但都是执行 n - 1 次循环。
当在多层 for 循环中，下层的 for 循环通常需要引用上层 for 循环中的自增计数变量，当同一个自增计数变量处于不同的 for 循环，而多个 for 循环又使用不同的计数范围时，就可能轻易造成 ‘数组下标越界异常’ 或 ‘逻辑错误’，而这种错误又较难排除，因为这个场景具有迷惑性。
这里提出几点参考：

1. for 循环中自增变量的 ‘起始值’，和该 for 循环的 ‘终止条件’ 要特别留意，以及 ‘终止条件’ 语句中可能使用到的 ‘小于号‘ < ’’ 与 ‘小于或等于号 ‘ <= ’’ 的区别，例如

for(int i = 0;i < n;i++){ // 执行 n 次
}
// 区别于
for(int i = 0;i <= n - 1;i++){ // 执行 n 次
}
// 区别于
for(int i = 0;i <= n;i++){ // 执行 n + 1 次
}

2. 一定要理清每个 for 循环的范围，即起始值与最后一个有效值，以及该循环体执行的次数

1. 选择排序程序示例（有两种内层 for 循环方式）

/**
	 * 选择排序
	 * @param array 等待被排序的数组
	 * @param type 指定排序方式，小于 0：表示递减排序，否则为递增排序
	 */
	public static void doSorting2(int[] array, int type) {
		type = type < 0 ? -1 : 1;
		int len = 0;
		int index = -1;
		if (array != null && (len = array.length) > 1) {
			int temp = 0;
			// 每一次选择操作，都是为数组下标为 i 的位置选择一个相对最大（或最小）值，
			// 当确定了 n - 1 个位置的值时，数组便排序完成
			for(int i = 0;i < len - 1;i++) {
				index = i;
				// 1，第一种 for 循环写法
				// 与 i 后面的所有其它元素依次进行比较，直到数组的末端（j 的最大取值为 下标 len - 1）
//				for(int j = i + 1;j < len;j++) {
//					if (type < 0) {
//						// 递减排序
//						if (array[index] < array[j]) {
//							index = j;
//						}
//					} else {
//						// 递增排序
//						if (array[index] > array[j]) {
//							index = j;
//						}
//					}
//				}
				// 2，第二种 for 循环写法
				// 外层 for 循环中，自增计数变量 i 从 0 开始取值，且其用于数组下标，
				// 所以下标为 i 的元素后面还有 （len - 1）- i 个元素（其中 len - 1 为数组的最大下标）。
				// 与 i 后面的（len - 1 - i）个元素进行比较（j 的最大取值为：循环执行的最大次数即 len - 1 - i）
				for (int j = 1; j <= len - 1 - i; j++) {
					if (type < 0) {
						// 递减排序
						if (array[index] < array[i + j]) {
							index = i + j;
						}
					} else {
						// 递增排序
						if (array[index] > array[i + j]) {
							index = i + j;
						}
					}
				}
				// 交换位置
				if (index != i) {
					temp = array[i];
					array[i] = array[index];
					array[index] = temp;
				}
			}
		}
	}