选择排序（Selection Sort）算法也是比较简单的排序算法，其思路比较直观。选择排序算法在每一步中选取最小值来重新排序，从而达到排序的目的。
选择排序算法
选择排序算法通过选择和交换来实现排序，其排序流程如下：
⑴首先从原始数组中选择最小的1个数据，将其和位于第1个位置的数据交换。
⑵接下来从剩下的n-1个数据中选择次小的1个数据，将其和第2个位置的数据交换。
⑶然后不断重复上诉过程，直到最后两个数据完成交换。至此，便完成了对原始数组的从小到大的排序。
为了更好地理解选择排序算法的执行过程，下面举一个实际数据的例子来一步一步地执行选择排序算法。5个整型数据118、101、105、127、112是一组无序的数据。对其执行选择排序过程，如图1所示。
选择排序算法的执行步骤如下：
⑴第一次排序，从原始数组中选择最小的数据，这个数据便是101，将其与第1个数据118进行交换。此时排序后的数据为101，118，105，127，112。
⑵第二次排序，从剩余的数组中选择最小的数据，这个数据便是105，将其与第2个数据118进行交换。此时排序后的数据为101、105、118、127、112。
⑶第三次排序，从剩余的数组中选择最小的数据，这个数据便是112，将其与第3个数据118进行交换。此时排序后的数据为101、105、112、127、118。
⑷第四次排序，从剩余的数组中选择最小的数据，这个数据便是118，将其与第4个数据127进行交换。此时排序后的数据为101、105、112、127、118。
从上面的例子可以非常直观的了解到选择排序算法的执行过程。选择排序算法在对n个数据进行排序时，无论袁术就有无顺序，都需要进行n-1步的中间排序。这种排序方法思路很简单直观，但是缺点是执行的步骤稍长，效率不高。
选择排序算法的示例代码如下：
void selectSort(int[] a) {
int index;
int temp;
for (int i = 0; i < a.length - 1; i++) {
index = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[index]) {
index = j;
}
}
if (index != i) {
temp = a[i];
a[i] = a[index];
a[index] = temp;
}
System.out.print("第" + (i + 1) + "步排序结果:"); // 输出每步排序的结果
for (int h = 0; h < a.length; h++) {
System.out.print(" " + a[h]);
}
System.out.println("\n");
}
}
在上述代码中，输入参数a一般为一个数组的首地址。待排序的原数据便保存在数组a中，程序中通过两层循环来对数据进行排序。可以结合前面的选择排序算法来加深理解。为了更清楚排序算法的执行过程，在排序的每一步都输出了当前的排序结果。
选择排序算法实例
学习了前面的选择排序算法的基本思想和算法之后，下面通过一个完整的例子来说明选择排序法在整型数组排序中的应用，程序示例如下：
【程序】
public class SelectionSort {
static final int SIZE = 10;
public static void selectSort(int[] a) {
int index, temp;
for (int i = 0; i < a.length - 1; i++) {
index = i;
for (int j = i + 1; j < a.length; j++) {
if (a[j] < a[index]) {
index = j;
}
}
if (index != i) {
temp = a[i];
a[i] = a[index];
a[index] = temp;
}
System.out.print("第" + (i + 1) + "步排序结果:"); // 输出每步排序的结果
for (int h = 0; h < a.length; h++) {
System.out.print(" " + a[h]);
}
System.out.println("\n");
}
}
public static void main(String[] args) {
int[] shuzu = new int[SIZE];
int i;
for (i = 0; i < SIZE; i++) {
shuzu[i] = (int) (100 + Math.random() * (100 + 1));
}
System.out.print("排序前的数组为: \n");
for (i = 0; i < SIZE; i++) {
System.out.print(shuzu[i] + " ");
}
System.out.print("\n");
selectSort(shuzu);
System.out.print("排序后的数组为: \n");
for (i = 0; i < SIZE; i++) {
System.out.print(shuzu[i] + " ");
}
System.out.print("\n");
}
}
在上诉代码中，程序定义了符号常量SIZE，用于表征需要排序整型数组的大小。在主方法中，首先声明一个整型数组，然后对数组进行随机初始化，并输出排序前的数组内用。接着，调用选择排序算法方法来对数组进行排序。最后，输出排序后的数组。
该程序的执行结果，如图2所示。图中显示了每一步排序的中间结果。
网友评论