Java programming based on the quick sort of three algorithm example code

A brief introduction to quicksort

Quicksort is an update to bubble sort that we learned about before, and they're all sort by exchange class, and they're all sort by constant comparison and movement. Rapid sorting is a very efficient sorting algorithm. Its implementation increases the distance between the comparison and movement of records, and directly moves the records with large keywords from the front to the back, and the records with small keywords from the back to the front, thus reducing the total number of comparison and movement. By adopting the idea of "divide and conquer" at the same time, the big broken down into small, small split into smaller, its principle is as follows: 1, for a given set of records, choose a base element, usually choose the first or the last one element, through 1 scan, will stay sequence is divided into two parts, one part is smaller than benchmark elements, part 1 is greater than or equal to base element, the base element in its correct position after the sorted, and then use the same method recursively sort divided into two parts, until all of the records in sequence are orderly.

1, the minimum number of k

Enter the number of n and find out the smallest number of k, for example, enter 4,5,1,6,2,7,3,8, then the smallest number is 1,2,3,4

Based on O (n) algorithm, based on Partion function can be used to solve this problem, if the first k based on array Numbers to adjust, make all smaller than the first k a digital Numbers are located in the left of the array, is bigger than the first k an array of all the Numbers are in the right side of the array, this adjustment array on the left side of the k Numbers is the smallest k Numbers, not 1 order

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int n=in.nextint();
		int k=in.nextint();
		int[] num=new int[n];
		int[] out=new int[k];
		for (int i=0;i<n;i++){
			num[i]=in.nextint();
		}
		Boolean b=GetMinK(n,num,k,out);
		if(b){
			for (int i=0;i<k;i++){
				System.out.print(out[i]+" ");
			}
		}
	}
	public static Boolean GetMinK(int uiInputNum, int[] pInputArray, int uiK, int[] pOutputArray){
		if(pInputArray==null||pOutputArray==null||uiK>uiInputNum||uiInputNum<=0||uiK<=0){
			return false;
		}
		int start=0;
		int end=uiInputNum-1;
		int index=partition(pInputArray,start,end);
		while(index!=uiK-1){
			if(index>uiK-1){
				//index in k-1 On the right side of the  
				end=index-1;
				index=partition(pInputArray,start,end);
			} else{
				start=index+1;
				index=partition(pInputArray,start,end);
			}
		}
		for (int i=0;i<uiK;i++){
			pOutputArray[i]=pInputArray[i];
		}
		return true;
	}
	//partion Partition function, which returns an array a The index value of the first element of quicksort index 
	public static int partition(int[] a,int start,int end){
		int privot=a[start];
		int i=start;
		int j=end;
		while(i<j){
			while(i<j&&privot<=a[j]){
				j--;
			}
			swap(a,i,j);
			while(i<j&&privot>=a[i]){
				i++;
			}
			swap(a,i,j);
		}
		return i;
	}
	public static void swap(int[] a,int i,int j){
		int t=a[i];
		a[i]=a[j];
		a[j]=t;
	}
}

2, the number that occurs more than 1 half times in the array

There is a number in the array that occurs more than one and a half times the length of the array. Find this number. For example, 1,2, 3,2,2,2,5,4,2, the number 2 appears in the array five times, exceeding 1/2 of the array length, and outputs 2

Inspired by quicksort, in quicksort, you now select a number in the array, and then adjust the order of the numbers in the array so that any number smaller than the selected number is placed to its left and any number larger than the selected number is placed to its right.

If the subscript of the selected number happens to be n/2, that number is the median of the array

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int n=in.nextint();
		int[] num=new int[n];
		for (int i=0;i<n;i++){
			num[i]=in.nextint();
		}
		int b=GetHalfNum(n,num);
		if(b!=-1){
			System.out.println(b);
		}
	}
	public static int GetHalfNum(int uiInputNum, int[] pInputArray){
		if(pInputArray==null||uiInputNum<=0){
			return -1;
		}
		int middle=uiInputNum>>1;
		// The length of the 1 And a half  
		int start=0;
		int end=uiInputNum-1;
		int index=partition(pInputArray,start,end);
		while(index!=middle){
			// If it's not equal to the length 1 Half of that means you don't find the median  
			if(index>middle){
				end=index-1;
				index=partition(pInputArray,start,end);
			} else{
				start=index+1;
				index=partition(pInputArray,start,end);
			}
		}
		return pInputArray[index];
		//index=middle
	}
	public static int partition(int[] a,int start,int end){
		int privot=a[start];
		int i=start;
		int j=end;
		while(i<j){
			while(i<j&&privot<=a[j]){
				j--;
			}
			swap(a,i,j);
			while(i<j&&privot>=a[i]){
				i++;
			}
			swap(a,i,j);
		}
		return i;
	}
	public static void swap(int[] a,int i,int j){
		int t=a[i];
		a[i]=a[j];
		a[j]=t;
	}
}

3. Find the k smallest number in the array

For example, given array 1,5,2,6,8,0,6, the fourth smallest number is 5

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in=new Scanner(System.in);
		int n=in.nextint();
		int k=in.nextint();
		int[] num=new int[n];
		//int[] out=new int[k]; 
		for (int i=0;i<n;i++){
			num[i]=in.nextint();
		}
		int b=GetMinK(n,num,k);
		if(b!=-1){
			System.out.println(b);
		}
	}
	public static int GetMinK(int uiInputNum, int[] pInputArray, int uiK){
		if(pInputArray==null||uiK>uiInputNum||uiInputNum<=0||uiK<=0){
			return -1;
		}
		int start=0;
		int end=uiInputNum-1;
		int index=partition(pInputArray,start,end);
		while(index!=uiK-1){
			// if index not k-1 The location of the  
			if(index>uiK-1){
				end=index-1;
				index=partition(pInputArray,start,end);
			} else{
				start=index+1;
				index=partition(pInputArray,start,end);
			}
		}
		return pInputArray[index];
		// Returns the value of this position 
	}
	public static int partition(int[] a,int start,int end){
		int privot=a[start];
		int i=start;
		int j=end;
		while(i<j){
			while(i<j&&privot<=a[j]){
				j--;
			}
			swap(a,i,j);
			while(i<j&&privot>=a[i]){
				i++;
			}
			swap(a,i,j);
		}
		return i;
	}
	public static void swap(int[] a,int i,int j){
		int t=a[i];
		a[i]=a[j];
		a[j]=t;
	}
}

conclusion

The above is the Java programming based on the quick sort of three algorithm sample code, I hope to help you. Interested friends can continue to refer to other related topics in this site, if there is any deficiency, welcome to comment out. Thank you for your support!