思路:就是把所有数据项扫描一遍,挑出最小的那个和最左边的交换位置,即放到0位置。现在最左边的就是有序得了,不需要在交换位置,再次扫描数据时就是从1开始,还是寻找最小的和1交换位置,直到所有数据都是有序的。选择排序的比较次数与冒泡排序相同,都是N-1次(https://www.cnblogs.com/zouwangblog/p/10984663.html),但是交换次数少于冒泡排序,每趟排序只有最后一次交换,前面的比较都是下标赋值

下面举例说明:

int[] arg = {6,3,8,2,9,1}

int min = 0

  • 第一趟排序:
    • 第一次3和6比较,3小于6,min = 1
    • 第二次从min=1开始比较:8和3比较,8大于3,继续不赋值
    • 第三次2和3比较,2小于3,min = 3
    • 第四次从min = 3开始比较,9大于2,继续不赋值

    • 第五次1和2比较,1小于2,min = 5

    • 将下标0和下标5进行交换
    • 第一趟总共进行了 5次比较 1次交换, 排序结果: 1,3,8,2,9,6

  • 第二趟排序(从3开始向后比较):

    • 第一次3和8比较,8大于3,继续不赋值

    • 第二次2和3比较,2小于3,min = 3

    • 第三次从min = 3开始比较,9 大于2,继续不赋值

    • 第四次从min = 3开始比较,6大于2,不赋值,循环结束

    • 将下标1和下标3进行交换
    • 第二趟总共进行了4次比较 1次交换, 排序结果: 1,2,8,3,9,6

  • 第三趟排序(从8开始向后比较):

    • 第一次3和8比较,3小于8,min = 3

    • 第二次从min = 3开始比较,9大于3,继续不赋值

    • 第三次从min = 3开始比较,6大于4,继续不赋值结束循环

    • 将下标2和下标3进行交换,

    • 第二趟总共进行了3次比较 1次交换, 排序结果: 1,2,3,8,9,6

  • 第四趟排序(从8开始向后比较):

    • 第一次8和9比较,9大于8,继续不赋值

    • 第二次8和6比较,6小于8,min = 5结束循环

    • 将下标3和下标5进行交换

    • 第二趟总共进行了2次比较 1次交换, 排序结果: 1,2,3,6,8,9


  • 第五趟排序(从8开始向后比较):
    • 第一次8和9比较,9大于8,不赋值结束循环
    • 第二趟总共进行了1次比较 0次交换, 排序结果: 1,2,3,6,8,9

代码实现:

外层循环用变量out,从数组开头开始(数组下标为0)向高位增长。内层循环用循环变量in,从out所指位置开始,同样是向右移位,在每一个in的新位置数据项array[in]和array[min]进行比较,如果a[in]更小,则min被赋值为in的值,在内层循环的最后,min被指向最小的值,然后交换out和min指向的数组数据项

public static void selectSort(int[] array) {
        int out,in,min = 0;
        for (out = 0; out<array.length-1; out++) {
            min = out;
            for (in = out; in<array.length; in++) {
                if (array[in] < array[min]) {
                    min = in;
                }
            }
            swap(out, min);
        }
    }

public static void swap(int one, int two) {
        int temp = ii[one];
        ii[one] = ii[two];
        ii[two] = temp;
    }

不变性:下标小于或等于out位置的数据总是有序的