选择排序
算法思路
选择排序的步骤:
1>首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
2>再从剩余未排序元素中继续寻找最小(大)元素,然后放到未排序序列的起始位置。
3>重复第二步,直到所有元素均排序完毕。
动画演示
算法代码
public static void selectSort1(int[] a){
for (int i = 0; i < a.length; i++) {
int minIndex = i;
for (int j = i+1 ; j <a.length ; j++) {
if(a[j] <= a[minIndex]){
minIndex = j;
}
}
if(minIndex == i) continue; //说明没找到更小的
int tmp = a[minIndex];
a[minIndex] = a[i];
a[i] = tmp;
}
}
复杂度分析
时间复杂度 O(n^2) 等差数列
空间复杂度 O(1)
稳定性 不稳定
选择排序优化
选择排序的优化思路一般是在一趟遍历中,同时找出最大值与最小值,放到数组两端,这样就能将遍历的趟数减少一半。第一次选择最大值与最小值,过程如下:
算法代码
public static void selectSort2(int[] a){
int left = 0;
int right = a.length-1;
while(left<right) {
int minIndex = left;
int maxIndex = right;
for(int i = left+1;i<=right;i++) {
if(a[i] < a[minIndex]) {
minIndex = i;
}
if(a[i] > maxIndex) {
maxIndex = i;
}
}
//交换左边
int tmp1 = a[minIndex];
a[minIndex] = a[left];
a[left] = tmp1;
if(maxIndex == left) { //很重要的一点细节
maxIndex = minIndex;
}
//交换右边
int tmp2 = a[maxIndex];
a[maxIndex] = a[right];
a[right] = tmp2;
left++;
right--;
}
}
时间复杂度测试
接下来我们试着用大量数据测试一下。
int[] a = new int[10_0000]; //10万个数据测试
1.orderArray函数实现生成一个基本有序数列,即从小到大排列。
public static void orderArray(int[] a) {
for (int i = 0; i < a.length; i++) {
a[i] = i;
}
}
2.notOrderArray函数生成一个倒序数列,即从大到小排列。
public static void notOrderArray(int[] a) {
for (int i = 0; i < a.length; i++) {
a[i] = a.length-i;
}
}
3.randomArray函数生成一个随机无序数列。
public static void randomArray(int[] a) {
Random random = new Random();
for (int i = 0; i < a.length; i++) {
a[i] = random.nextInt(10_0000);
}
}
4.testInsertSort函数测试 System.currentTimeMillis() 返回值单位是毫秒。
public static void testInsertSort(int[] a){
int[] tmpArray = Arrays.copyOf(a,a.length);
long startTime = System.currentTimeMillis(); //注意用long接收
shellSort(tmpArray);
long endTime = System.currentTimeMillis(); //返回单位是毫秒
System.out.println("选择排序耗时:"+(endTime-startTime));
}
5.main函数调用执行
public static void main(String[] args) {
int[] a = new int[10_0000];
//有序
System.out.println("基本有序数列");
orderArray(a);
testInsertSort(a);
//倒序
System.out.println("逆序数列");
notOrderArray(a);
testInsertSort(a);
//随机乱序
System.out.println("无序数列");
randomArray(a);
testInsertSort(a);
}
测试结果
从结果来看,对于大量的数据,优化后的反而更慢了,应该是这种排序算法更适合少量数据。
我们放250个数据进行测试。文章来源:https://www.toymoban.com/news/detail-622207.html
结果证明耗时上还是有所下降的。 文章来源地址https://www.toymoban.com/news/detail-622207.html
完整代码
import java.util.Random;
public class sort {
public static void main(String[] args) {
int[] a = new int[10_0000];
//有序
System.out.println("基本有序数列");
orderArray(a);
testInsertSort(a);
//无序
System.out.println("逆序数列");
notOrderArray(a);
testInsertSort(a);
//乱序
System.out.println("无序数列");
randomArray(a);
testInsertSort(a);
}
public static void selectSort(int[] a){
for (int i = 0; i < a.length; i++) {
int minIndex = i;
for (int j = i+1 ; j <a.length ; j++) {
if(a[j] <= a[minIndex]){
minIndex = j;
}
}
if(minIndex == i) continue; //说明没找到更小的
int tmp = a[minIndex];
a[minIndex] = a[i];
a[i] = tmp;
}
}
//生成有序数组 从小到大排列
public static void orderArray(int[] a) {
for (int i = 0; i < a.length; i++) {
a[i] = i;
}
}
//n无序 其实就是从大到小排列
public static void notOrderArray(int[] a) {
for (int i = 0; i < a.length; i++) {
a[i] = a.length-i;
}
}
//乱序 随机生成序列
public static void randomArray(int[] a) {
Random random = new Random();
for (int i = 0; i < a.length; i++) {
a[i] = random.nextInt(10_0000);
}
}
//大量数据测试
public static void testInsertSort(int[] a){
int[] tmpArray = Arrays.copyOf(a,a.length);
long startTime = System.currentTimeMillis(); //注意用long接收
selectSort(tmpArray);
long endTime = System.currentTimeMillis();
System.out.println("选择排序耗时:"+(endTime-startTime));
}
}
创作不易,如果本篇博客对您有一定的帮助,大家记得留言+点赞哦。
到了这里,关于八大排序算法--选择排序(动图理解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!