选择排序的基本操作就是每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。算法不稳定,O(1)的额外的空间,比较的时间复杂度为O(n^2),交换的时间复杂度为O(n),并不是自适应的。在大多数情况下都不推荐使用。只有在希望减少交换次数的情况下可以用。
基本思想
n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果:
①初始状态:无序区为R[1..n],有序区为空。
②第1趟排序
在无序区R[1..n]中选出关键字最小的记录R[k],将它与无序区的第1个记录R[1]交换,使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
……
③第i趟排序
第i趟排序开始时,当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n-1)。该趟排序从当前无序区中选出关键字最小的记录
R[k],将它与无序区的第1个记录R交换,使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。
这样,n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。
代码实现
public class chooseSort {
public static void main(String[] args) {
<wbr>int[] a = {25,89,42,16,12,36};</wbr>
<wbr>int min = 0;</wbr>
<wbr>int tmp = 0;</wbr>
<wbr>for(int
i=0;i<a.length;i++){</wbr>
<wbr> min = i;//</wbr>
<wbr><wbr><wbr><wbr>System.out.println("第一组设定下标min为:"+min);</wbr></wbr></wbr></wbr>
<wbr></wbr>
<wbr> for(int
j=i+1;j<a.length;j++){</wbr>
<wbr><wbr>if(a[min]>a[j]) {</wbr></wbr>
<wbr><wbr>
System.out.print(a[min]+"比"+a[j]+"要大 <wbr><wbr> ");</wbr></wbr></wbr></wbr>
<wbr><wbr> min =
j;//记下较大数位置,再次比较,直到最大</wbr></wbr>
<wbr><wbr>}</wbr></wbr>
<wbr><wbr><wbr><wbr>System.out.println("现在较小数为"+a[min]+",下标为min:"+min+"
<wbr><wbr> ");</wbr></wbr></wbr></wbr></wbr></wbr>
<wbr> }</wbr>
<wbr></wbr>
<wbr> if(i!=min){</wbr>
<wbr><wbr>tmp = a[i];</wbr></wbr>
<wbr><wbr>a[i] = a[min];</wbr></wbr>
<wbr><wbr>a[min] = tmp;</wbr></wbr>
<wbr><wbr>System.out.print(a[i]+"与"+a[min]+"进行了交换,现在较大值为:a[min]:"+a[min]+"
要换的值的下标为:"+min+" <wbr><wbr> ");</wbr></wbr></wbr></wbr>
<wbr> }</wbr>
<wbr> System.out.println(Arrays.toString(a));</wbr>
<wbr>}</wbr>
<wbr>for(int i=0;i<a.length;i++)</wbr>
<wbr> System.out.print(a[i]+" ");</wbr>
}
}
代码二:按顺序排序
public static void main(String args[]) {
<wbr>int[] array = { 14, 5, 86, 4, 12, 3, 51, 13,
11, 2, 32, 6 }; <wbr>// 创建一个初始化的一维数组array</wbr></wbr>
<wbr>int keyValue; <wbr><wbr><wbr>// 表示最小的元素值</wbr></wbr></wbr></wbr>
<wbr>int index; <wbr><wbr><wbr> // 表示最小的元素值的下标</wbr></wbr></wbr></wbr>
<wbr>int temp; <wbr><wbr><wbr> // 中间变量</wbr></wbr></wbr></wbr>
<wbr>System.out.println("未排序的数组:");</wbr>
<wbr>for (int i = 0; i <
array.length; i++) { <wbr>// 遍历array数组中的元素</wbr></wbr>
<wbr> System.out.print(" " + array[i]);
<wbr>// 输出数组元素</wbr></wbr>
<wbr> if ((i + 1) % 5 == 0) <wbr><wbr>// 每5个元素一行</wbr></wbr></wbr>
<wbr><wbr>System.out.println();</wbr></wbr>
<wbr>}</wbr>
<wbr>for (int i = 0; i <
array.length; i++) { <wbr>// 使用选择排序法的核心</wbr></wbr>
<wbr> index = i;</wbr>
<wbr> keyValue = array[i];</wbr>
<wbr> for (int j = i; j <
array.length; j++)</wbr>
<wbr><wbr>if (array[j]
< keyValue) {</wbr></wbr>
<wbr><wbr> index = j;</wbr></wbr>
<wbr><wbr> keyValue =
array[j];</wbr></wbr>
<wbr><wbr>}</wbr></wbr>
<wbr> temp = array[i];</wbr>
<wbr> array[i] = array[index];</wbr>
<wbr> array[index] = temp;</wbr>
<wbr>}</wbr>
<wbr>System.out.println("\n使用选择排序法后的数组:");</wbr>
<wbr>for (int i = 0; i <
array.length; i++) { <wbr> // 遍历排好序的array数组中的元素</wbr></wbr>
<wbr> System.out.print(" " + array[i]);
<wbr> // 输出数组元素</wbr></wbr>
<wbr> if ((i + 1) % 5 == 0)</wbr>
<wbr><wbr>System.out.println();
<wbr><wbr>// 每5个元素一行</wbr></wbr></wbr></wbr>
<wbr>}</wbr>
}
}
选择排序法与冒泡排序法一样,最外层循环仍然要执行n-1次,其效率仍然较差
相关推荐
Java常用的排序算法,常用算法集代码。
用线程来实现比较查找、排序算法的运行时间,第一部分是将顺序查找、折半查找算法设计成线程并同时运行来比较两种查找算法,第二部分是将冒泡排序、快速排序及选择排序设计成线程并同时运行来比较三种排序算法。...
Java 排序 随机数 算法收录了几种java常见的排序算法!
java排序算法java排序算法插入选择冒泡java排序算法插入选择冒泡
java排序算法使用及场景说明 文档后面有一些别人的链接,多在google上搜索Java排序算法,及维基百科上面也有很全的算法介绍。
经常使用查找和排序算法_Java_下载.zip
java实现的常用的几种基本排序算法,插入、交换、选择、归并
常用各种排序算法Java的实现_差不多了__.rar常用各种排序算法Java的实现_差不多了__.rar
Java排序算法实现 Java排序算法实现 Java排序算法实现
JAVA语言 排序算法 选择 冒泡 插入 希尔 归并
Java排序算法代码.
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
Java排序算法 Java排序算法.rar
尚硅谷Java排序算法PPT
Java所有排序算法大全 Java所有排序算法大全 Java所有排序算法大全 Java所有排序算法大全
Java排序算法实现资源 这个资源是关于Java中排序算法实现的简单示例。排序算法是计算机科学中的基础概念,用于按升序或降序排列数据集。这里提供了两种常见的排序算法实现:冒泡排序和选择排序。 冒泡排序(Bubble ...
Java语言实现的选择排序算法,代码里头有详细注释,注释皆为简单英文,因为这个算法比较简单,欢迎新手下载学习使用,欢迎后期的学习交流!
Java数组排序总结(冒泡_选择_插入_希尔)__递归算法的复杂度,实用
7大排序算法Java实现,简单易懂,包括2路快排,3路快排