什么是选择排序法？

选择排序，就是把要排序的含有N个元素的一组记录进行分趟比较，在每一趟的记录（无序序列）中选择最小（或最大）的值作为 有序序列 中第 I（I=1，2，…，N-1）个记录。通过比较交换后得到的有序序列即为选择排序的结果。

举个“栗子”，从小到大选择排序，有一组数A= ｛55，60，13，23，19，8｝
第 1 趟比较：
原数列就是一组无序序列，经过比较，最后一个元素“8”最小，故将其跟第1个元素“55”交换，作为有序序列 ｛8｝ 的第1个记录。
第 2 趟比较：
从无序序列 ｛60，13，23，19，55｝ 中比较得出元素“13”最小，交换后得到有序序列 ｛8，13｝ 。
如此类推，得出最后的有序序列 ｛8，13，19，23，55，60｝ 即为选择排序结果。

---

我们来看看代码（在 Java 环境运行）：

import javax.swing.JOptionPane;
public class SelectSort {      				//用选择排序法由小到大排序
	public static void main(String[] args) {
		int count = 0,count_swap=0, j,ins, index, temp, min;
		String s=JOptionPane.showInputDialog("请输入数组个数：");
		ins=Integer.valueOf(s);
		int []arr=new int[ins];
		for(int num=0;num<arr.length;num++) {
			arr[num]=Integer.valueOf(JOptionPane.showInputDialog("请输入第"+(num+1)+"个数："));
		}
		System.out.println("输入数组：");
		for (int a : arr) {
			System.out.print(a + " ");
		}
		System.out.println();
		System.out.println("执行过程：");
		for (int i = 0; i < arr.length - 1; i++) {
			min = arr[i];
			index = i;
			for (j = i + 1; j < arr.length; j++) {
				if (arr[j] < min) {
					min = arr[j];
					index = j;
				}
				count += 1;
			}
			if (index != i) {
				temp = arr[i];
				arr[i] = arr[index];
				arr[index] = temp;
				count_swap+=1;
				for (int a : arr) {
					System.out.print(a + " ");
				}
				System.out.print(" 第"+count_swap + "次交换");
				System.out.println();
			}
		}
		if(count_swap==0) {
			System.out.println("已是排序数组，无需执行");
		}
		System.out.println("排序结果:");
		for (int k : arr) {
			System.out.print(k + " ");
		}
		System.out.print(" " + "共交换" + count_swap + "次"+"，" + "共比较" + count + "次");
	}
}

运行结果：

输入数组： 55 60 13 23 19 8

执行过程： 8 60 13 23 19 55       第1次交换
                    8 13 60 23 19 55       第2次交换
                    8 13 19 23 60 55       第3次交换

排序结果:    8 13 19 23 55 60       共交换4次，共比较15次

---

算法分析：

首先将整个数组分别划分为以第1个、第2个…第n-1个数开头到最后一个数的比较区域，共有n-1个。接着在每个比较区域里找出最小值，若最小值的位置不在比较区域之首，则将其第1个数和最小值交换；若无，则不交换。在含有x个数的比较区域中，必定涉及x-1次比较，次数与最小值出现的位置无关。

接下来，记录分别为5-10个元素的数组，做进一步分析：

---

由统计数据可知：

1. 对n个不同随即序列的数进行选择排序，比较次数是恒定的，与原数组排列顺序无关。n越大，比较次数越多，规模越大。通过记录不难发现，存在这种关系：比较次数 c=n(n–1)/2, (n>0) 。

2. 交换次数由原数组的有序程度决定。有序程度越高，交换次数越少。

3. 多次测试总结得出，运行结果是否与分析结果一致。

如有不对的地方，欢迎指正，谢谢！