选择排序

算法思路

 选择排序的步骤：

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个数据进行测试。

                           结果证明耗时上还是有所下降的。                                   

完整代码

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));}
}

创作不易，如果本篇博客对您有一定的帮助，大家记得留言+点赞哦。