选择排序 (Selection Sort) 算法也是比较简单的排序算法, 其思路比较直观. 选择排序算法在每一步中选取最小值来重新排序, 从而达到排序的目的.
选择排序算法通过选择和交换来实现排序, 其排序流程如下:
1首先从原始数组中选择最小的 1 个数据, 将其和位于第 1 个位置的数据交换.
2接下来从剩下的 n-1 个数据中选择次小的 1 个数据, 将其和第 2 个位置的数据交换.
3然后不断重复上诉过程, 直到最后两个数据完成交换. 至此, 便完成了对原始数组的从小到大的排序.
为了更好地理解选择排序算法的执行过程, 下面举一个实际数据的例子来一步一步地执行选择排序算法. 5 个整型数据 118,101,105,127,112 是一组无序的数据. 对其执行选择排序过程, 如图 1 所示.
选择排序算法的执行步骤如下:
1第一次排序, 从原始数组中选择最小的数据, 这个数据便是 101, 将其与第 1 个数据 118 进行交换. 此时排序后的数据为 101,118,105,127,112.
2第二次排序, 从剩余的数组中选择最小的数据, 这个数据便是 105, 将其与第 2 个数据 118 进行交换. 此时排序后的数据为 101,105,118,127,112.
3第三次排序, 从剩余的数组中选择最小的数据, 这个数据便是 112, 将其与第 3 个数据 118 进行交换. 此时排序后的数据为 101,105,112,127,118.
4第四次排序, 从剩余的数组中选择最小的数据, 这个数据便是 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 所示. 图中显示了每一步排序的中间结果.
来源: http://www.jianshu.com/p/3bbdea82839f