模板网站配置文件,网页设计就业工资,品牌高端网站制作官网,嘉兴做网站建设的公司选择排序
算法思路 每一次从待排序的数据元素中选出最小#xff08;或最大#xff09;的一个元素#xff0c;存放在序列的起始位置#xff0c;直到全部待排序的数据元素排完 。 选择排序的步骤#xff1a; 1首先在未排序序列中找到最小#xff08;大#xff09;元素…选择排序
算法思路 每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。 选择排序的步骤 1首先在未排序序列中找到最小大元素存放到排序序列的起始位置。 2再从剩余未排序元素中继续寻找最小大元素然后放到未排序序列的起始位置。 3重复第二步直到所有元素均排序完毕。 动画演示 算法代码
public static void selectSort1(int[] a){for (int i 0; i a.length; i) {int minIndex i;for (int j i1 ; 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(leftright) {int minIndex left;int maxIndex right;for(int i left1;iright;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 i1 ; 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));}
}
创作不易如果本篇博客对您有一定的帮助大家记得留言点赞哦。
