本文实例讲述了Java基于分治算法实现的线性时间选择操作。分享给大家供大家参考,具体如下:
线性时间选择问题:给定线性序集中n个元素和一个整数k,1≤k≤n,要求找出这n个元素中第k小的元素,(这里给定的线性集是无序的)。
随机划分线性选择
线性时间选择随机划分法可以模仿随机化快速排序算法设计。基本思想是对输入数组进行递归划分,与快速排序不同的是,它只对划分出的子数组之一进行递归处理。
程序解释:利用随机函数产生划分基准,将数组a[p:r]划分成两个子数组a[p:i]和a[i+1:r],使a[p:i]中的每个元素都不大于a[i+1:r]中的每个元素。接着"j=i-p+1"计算a[p:i]中元素个数j.如果k<=j,则a[p:r]中第k小元素在子数组a[p:i]中,如果k>j,则第k小元素在子数组a[i+1:r]中。注意:由于已知道子数组a[p:i]中的元素均小于要找的第k小元素,因此,要找的a[p:r]中第k小元素是a[i+1:r]中第k-j小元素。
在最坏的情况下,例如:总是找到最小元素时,总是在最大元素处划分,这是时间复杂度为O(n^2)。但平均时间复杂度与n呈线性关系,为O(n)
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
|
package math;
import java.util.Scanner;
import java.util.Random;
public class RandomSelect {
public static void swap( int x, int y) {
int temp = x;
x = y;
y = temp;
}
public int Random ( int x, int y) {
Random random = new Random();
int num = random.nextInt(y)%(y - x + 1 ) + x;
return num;
}
public int partition( int [] list, int low, int high) {
int tmp = list[low]; //数组的第一个作为中轴
while (low < high) {
while (low < high && list[high] > tmp) {
high--;
}
list[low] = list[high]; //比中轴小的记录移到低端
while (low < high && list[low] < tmp) {
low++;
}
list[high] = list[low]; //比中轴大的记录移到高端
}
list[low] = tmp; //中轴记录到尾
return low; //返回中轴的位置
}
public int RandomizedPartition ( int [] arrays, int left, int right) {
int i = Random(left, right);
swap(arrays[i], arrays[left]);
return partition(arrays, left, right);
}
public int RandomizedSelect( int [] arrays, int left, int right, int k) {
if (left == right ) {
return arrays[left];
}
int i = RandomizedPartition(arrays, left, right);
int j = i - left + 1 ;
if (k <= j) {
return RandomizedSelect(arrays,left, i,k) ;
}
else {
return RandomizedSelect(arrays,i+ 1 ,right,k-j);
}
}
public static void main(String args[]) {
System.out.println( "服务器之家测试结果:" );
int [] a = { 7 , 5 , 3 , 4 , 8 , 6 , 9 , 1 , 2 };
for ( int i = 0 ; i < 9 ; i ++) {
System.out.print(a[i]+ " " );
}
System.out.println();
RandomSelect r = new RandomSelect();
System.out.println( "你要查询的元素是数组中第几小的?" );
@SuppressWarnings ( "resource" )
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();
int n = r.RandomizedSelect(a, 0 , 8 ,m);
System.out.println( "这个数组中第" + m + "小的元素是:" + n);
}
}
|
运行结果:
希望本文所述对大家java程序设计有所帮助。
原文链接:http://blog.csdn.net/u014755255/article/details/50531632