选择排序面试题

001什么是选择排序？

选择排序是在遍历一个待排序的数组过程中，

第一次从 arr[0] 到 arr[n-1] 中选取最小值，与 arr[0] 交换；

第二次从arr[1] 到 arr[n-1]中选取最小值， 与arr[1]交换；

第三次从arr[2] 到 arr[n-1]中选取最小值，与arr[2]交换；

……

第 i 次从 arr[i-1] 到 arr [n-1] 中选取最小值，与arr[i-1]交换；

第n-1次从 arr[n-2] 到 arr [n-1] 中选取最小值，与 arr[n-2] 交换，总共通过n-1次，得到一个按排序码从小到大排列的有序序列。

002选择排序的代码实现？

具体实现参考如下源代码：

public static void choice(int arr[]) {
    for (int i = 0; i < arr.length - 1; i++) {
        int minIndex = i;
        int min = arr[i];
        for (int j = i + 1; j < arr.length; j++) {
            if (min > arr[j]) {
                min = arr[j];
                minIndex = j;
            }
        }
        if (minIndex != i) {
            arr[minIndex] = arr[i];
            arr[i] = min;
        }
    }
}

003有一组数据“12,15,1,18,2,35,30,11”，用选择法由小到大排序，第2趟交换数据后数据的顺序是( )。

A. 11，1，2，12，35，18，30，15
B. 1，2，12，18，15，35，30，11
C. 1，2，11，12，15，18，30，35
D. 1，2，11，12，15，18，35，30
答案：B
解析：第一趟选择1，将1和12交换位置，序列变为1,15,12,18,2,35,30,11，第二趟选择2，将2和15交换位置，序列变为1,2,12,18,15,35,30,11；故B正确

004在选择排序中，以下什么情况下选择排序会更快执行？

A. 数据已按升序排列
B. 数据已按升降序排列
C. 俩者花费时间一样
答案：C
解析：不管升序还是降序 其比较次数都是整条路径。