This article describes the linear time selection operation implemented by Java based on the partitioning and conquer algorithm. Share it for your reference, as follows:
Linear time selection problem: Given n elements and an integer k, 1≤k≤n, it is necessary to find out the smallest element of these n elements (the given linear set here is disordered).
Randomly divided linear selection
The linear time selection random division method can imitate the design of the randomized quick sort algorithm. The basic idea is to recursively divide the input array. Unlike quick sorting, it only recursively processes one of the divided subarrays.
Program explanation: Use a random function to generate a division benchmark, divide the array a[p:r] into two subarrays a[p:i] and a[i+1:r], so that each element in a[p:i] is not greater than each element in a[i+1:r]. Then "j=i-p+1" calculates the number of elements j in a[p:i]. If k<=j, then the k-th smallest element in a[p:r] is in the sub-array a[p:i], and if k>j, the k-th smallest element is in the sub-array a[i+1:r]. Note: Since it is known that the elements in the sub-array a[p:i] are all smaller than the k-th small element to be found, the k-th small element in a[p:r] to be found is the k-th small element in a[i+1:r].
In the worst case, for example: when the smallest element is always found, it is always divided at the largest element, which is the time complexity of O(n^2) . However, the average time complexity is linearly related to n, which is O(n)
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]; //The first of the array is the center axis while (low < high) { while (low < high && list[high] > tmp) { high--; } list[low] = list[high]; //Records smaller than the center axis are moved to the low end while (low < high && list[low] < tmp) { low++; } list[high] = list[low]; //Records larger than the center axis are moved to the high end} list[low] = tmp; //Records larger than the center axis are returned low; //Return to the position of the center axis} 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,kj); } } public static void main(String args[]) { System.out.println("Wulin.com test result: "); 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("What smallest element are you want to query for in the array?"); @SuppressWarnings("resource") Scanner sc = new Scanner(System.in); int m = sc.nextInt(); int n = r.RandomizedSelect(a,0,8,m); System.out.println("The "th "in this array" + m + "The smallest element is: "+ n); }}Running results:
For more information about Java algorithms, readers who are interested in this site can view the topics: "Java Data Structure and Algorithm Tutorial", "Summary of Java Operation DOM Node Tips", "Summary of Java File and Directory Operation Tips" and "Summary of Java Cache Operation Tips"
I hope this article will be helpful to everyone's Java programming.