©2020-2024 ioDraw All rights reserved
Quick sort
public class sort { public static void main(String[] args){ int
arr[]={59,6,3,8,51,23}; QuickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr)); } public static void QuickSort(int[]
arr,int left,int right){ // Recursive exit if(left>=right){ return; } // Define the benchmark number of variables to save int base
= arr[left]; // Define variables i Point to the far left （ The goal is to win every round ） int i = left; // Define variables j Point to the far right （ The goal is to win every round ） int j =
right; // When i and j When we didn't meet , Execution cycle while(i<j){ //j Retrieve the number smaller than the benchmark from the far right , Stop when it's retrieved
while(arr[j]>=base&&i<j){ j--; } //i Retrieve from the leftmost side a number larger than the benchmark , Stop when it's retrieved
while(arr[i]<=base&&i<j){ i++; } // The two numbers retrieved are exchanged int temp = arr[j]; arr[j]=arr[i];
arr[i]=temp; } // Position where the pointer coincides i Exchange of numbers and reference numbers on arr[left]=arr[i]; arr[i]=base; // Left of row reference number
QuickSort(arr,left,i-1); // Row benchmark right QuickSort(arr,i+1,right); } }
Quick sort idea ：
Separate the records to be arranged into two separate parts through one-time sorting , The keywords of some records are smaller than those of others , You can sort these two parts of records separately , To achieve the order of the whole sequence
Quick sort uses divide and conquer to divide a string into two strings
1. A tree in the array will be used as the benchmark
2. Generally, the leftmost tree in the array is used as the benchmark , Then search from both sides . Retrieve the number smaller than the benchmark from the right , Then, the left side searches for the number larger than the benchmark . If retrieved , Just stop , Then swap the two elements , Then continue the search
1. First find a benchmark base=5
2. First move the pointer on the right j, Found first less than 5 Number of , that is 1
Then move the pointer on the left i, Find first greater than 5 Number of , that is 6
Then exchange
3.i and j Once meet , Stop searching and exchange the reference number with the number of encounter positions
4. The first sorting is completed , After sorting, we find that the number on the left of the sorting is smaller than the benchmark number , The right side is larger than the reference number
Treat the left and right data as a new array , Then the array and the original number will be sorted in the same way
Analyze recursive expressions and recursive exits
Technology