经典选择排序的分析、实现、测试
1.选择排序过程分析
int arr
[] = {3,9,-1,-10,-2};
假设对arr这个数组进行排序： 第一轮： 用3和3后面的所有元素挨个比较，如果有比3小的，下一次比较就用这个较小的比较，例如：3与-1比较时-1比3小，那么下一次与-10的比较就用-1而不是3，最后找出最小的即-10，3和-10交换位置。
{-10,9,-1,3,-2}
结论： 每一轮比较，会找到数组中最小的元素。 … 结论： 排序思路比较好理解，代码写起来就不那么容易了，需要设置临时变量，对数据进行保存，有两个临时变量即找到的较小的元素temp与这个元素的下标index；
2.代码实现
package test1
;
import java
.util
.Arrays
;
import java
.util
.Random
;
public class SelectionSort {
public static void main(String
[] args
) {
int arr
[] = new int[80000];
for (int i
= 0; i
< 80000; i
++) {
arr
[i
]= new Random().nextInt(80000);
}
long before
= System
.currentTimeMillis();
sort(arr
);
long after
= System
.currentTimeMillis();
System
.out
.println((after
- before
) / 1000);
}
public static int[] sort(int[] arr
) {
boolean flag
= false;
for (int i
= 0; i
< arr
.length
-1; i
++) {
int temp
= arr
[i
];
int index
= 0;
for (int j
= 1; j
< arr
.length
- i
; j
++) {
if (arr
[i
+ j
] < temp
) {
temp
= arr
[i
+ j
];
index
= i
+ j
;
flag
= true;
}
}
if (flag
) {
arr
[index
] = arr
[i
];
arr
[i
] = temp
;
flag
=false;
}
}
return arr
;
}
}
3.选择排序测试
我的电脑测试了大约需要3秒的时间，比上一篇冒泡的时间快了5秒，顺嘴提一句选择排序的时间复杂度是O（n^2）
