- 2022-04-05 20:30
*views 7*- algorithm

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

- Java244 blogs
- Python241 blogs
- Vue112 blogs
- algorithm96 blogs
- c language94 blogs
- Flow Chart81 blogs
- MySQL71 blogs
- C++64 blogs
- more...

Daily Recommendation

© ioDraw All rights reserved

js of indexOf method computer network - Agreement and hierarchy Computer function key name , Do you know the basic knowledge of computer keyboard function Deep understanding of processes and threads Computer keyboard letter memory , keyboard 26 What is a letter formula ? stay uniapp Used in element-ui assembly PTA— Read numbers （C language ） Two methods QFontJAVA realization QQ Sign in , Registration and other functions number IC Hand tear code （ seven ）