本文实例讲述了Java排序算法总结之选择排序。分享给大家供大家参考。具体分析如下:
选择排序的基本操作就是每一趟从待排序的数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。算法不稳定,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趟直接选择排序得到有序结果。
代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
|
public class Test {
public static int [] a = { 10 , 32 , 1 , 9 , 5 , 7 , 12 , 0 , 4 , 3 };
// 预设数据数组
public static void main(String args[]) {
int i; // 循环计数变量
int Index = a.length; // 数据索引变量
System.out.print( "排序前: " );
for (i = 0 ; i < Index - 1 ; i++)
System.out.printf( "%3s" , a);
System.out.println( "" );
SelectSort(Index - 1 ); // 选择排序
// 排序后结果
System.out.print( "排序后: " );
for (i = 0 ; i < Index - 1 ; i++)
System.out.printf( "%3s" , a);
System.out.println( "" );
}
public static void SelectSort( int Index) {
int i, j, k; // 循环计数变量
int MinValue; // 最小值变量
int IndexMin; // 最小值索引变量
int Temp; // 暂存变量
for (i = 0 ; i < Index - 1 ; i++) {
MinValue = 32767 ; // 目前最小数值
IndexMin = 0 ; // 储存最小数值的索引值
for (j = i; j < Index; j++) {
if (a[j] < MinValue) // 找到最小值
{
MinValue = a[j]; // 储存最小值
IndexMin = j;
}
Temp = a; // 交换两数值
a = a;
a = Temp;
}
System.out.print( "排序中: " );
for (k = 0 ; k < Index; k++)
System.out.printf( "%3s" , a[k]);
System.out.println( "" );
}
}
}
|
选择排序法与冒泡排序法一样,最外层循环仍然要执行n-1次,其效率仍然较差。
希望本文所述对大家的java程序设计有所帮助。