一, 动图演示
二, 思路分析
1. 第一个跟后面的所有数相比, 如果小于 (或小于) 第一个数的时候, 暂存较小数的下标, 第一趟结束后, 将第一个数, 与暂存的那个最小数进行交换, 第一个数就是最小(或最大的数)
2. 下标移到第二位, 第二个数跟后面的所有数相比, 一趟下来, 确定第二小 (或第二大) 的数
重复以上步骤
直到指针移到倒数第二位, 确定倒数第二小 (或倒数第二大) 的数, 那么最后一位也就确定了, 排序完成.
三, 负杂度分析
1. 不管原始数组是否有序, 时间复杂度都是 O(n2),
因为没一个数都要与其他数比较一次,(n-1)2 次, 分解: n2+2n-1, 去掉低次幂和常数, 剩下 n2, 所以最后的时间复杂度是 n2
2. 空间复杂度是 O(1), 因为只定义了两个辅助变量, 与 n 的大小无关, 所以空间复杂度为 O(1)
四, Java 代码如下:
import java.util.Arrays;
public class 选择 {
- public static void main(String[] args) {
- int[] n = new int[]{1,6,3,8,33,27,66,9,7,88};
- int temp,index = -1;
- for (int i = 0; i <n.length-1; i++) {
- index=-1;
- for (int j = i+1; j <n.length; j++) {
- // 如果大于, 暂存较小的数的下标
- if(n[i]>n[j]){
- index = j;
- }
- }
- // 将一趟下来求出的最小数, 与这个数交换
- if(index>0 && index!=i){
- temp = n[i];
- n[i] = n[index];
- n[index] = temp;
- }
- }
- System.out.println(Arrays.toString(n));
- }
- }
来源: https://www.cnblogs.com/l199616j/p/10591955.html