Introduction to the principles of quick sorting
Quick sorting is an upgrade of bubble sorting that we learned before. They all belong to swap sorting, and they all use constant comparison and movement to achieve sorting. Quick sorting is a very efficient sorting algorithm. Its implementation increases the distance between the comparison and movement of records, and moves records with larger keywords directly from the front to the back, and records with smaller keywords directly from the back to the front, thereby reducing the total number of comparisons and movements. At the same time, the idea of "dividing and conquering" is adopted to split the big into small, and the small into smaller ones. The principle is as follows: For a given set of records, select a benchmark element, usually the first element or the last element is selected, and through a scan, the sequence to be sorted is divided into two parts, part smaller than the benchmark element, and part greater than or equal to the benchmark element. At this time, the benchmark element is in the correct position after it is sorted, and then the two parts are recursively sorted in the same way until all records in the sequence are ordered.
1. The smallest number of k
Enter n numbers to find the smallest k numbers, for example, enter 4,5,1,6,2,7,3,8, and the smallest number is 1,2,3,4
Based on O(n), this problem can be solved by using the Partion function. If the kth number of the array is adjusted based on the kth number, so that all numbers smaller than the kth number are located on the left of the array, and all numbers larger than the kth array are located on the right of the array. After adjustment, the k numbers on the left of the array are the smallest k numbers, which are not necessarily ordered.
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 is on the right side of k-1 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;}//partition partition function returns the index value of the quick row of the first element of array a 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. Numbers with more than half of the occurrences in the array
There is a number in the array that appears more than half of the length of the array. Please find this number. For example, 1, 2, 3, 2, 2, 5, 4, 2, the number 2 appears 5 times in the array, exceeding half of the length of the array, output 2
Inspired by quick sort, in quick sort, now select a number in the array, and then adjust the order of the numbers in the array so that numbers smaller than the selected number are ranked on its left and numbers larger than the selected number are ranked on its right.
If the subscript of the selected number happens to be n/2, then this number is the median number in 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;//Half of length int start=0;int end=uiInputNum-1;int index=partition(pInputArray,start,end); while(index!=middle){//If it is not equal to half of length, it means that the median is not found 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 kth smallest number in the array
For example, given array 1, 5, 2, 6, 8, 0, 6, the 4th 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 is not the position of k-1 if(index>uiK-1){end=index-1;index=partition(pInputArray,start,end);} else{start=index+1;index=partition(pInputArray,start,end);}} return pInputArray[index];//The value of this position returned}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;}}Summarize
The above is the entire content of this article about the example code of three algorithm questions based on quick sorting of Java programming. I hope it will be helpful to everyone. Interested friends can continue to refer to other related topics on this site. If there are any shortcomings, please leave a message to point it out. Thank you friends for your support for this site!