Sorting method (3) = > quick sort and merge sort

4. Quick sort
Quick sort is called quick sort for short , It mainly uses the main idea of recursion
recursive
Recursion is a method that calls its own method

Recursion mainly includes Recursive relation and recursive exit
example ：
① Array {1,2,3,4,5,…,n}
Recursive export ： When n=1 when , The return value is n;
Recursion ： At other times , The return value is （n-1）+1;
Code ：

public static int run(int n) {
		if(n==1)
			return 1;// Recursive export 
		return run(n-1)+1;// Recursion 
	}

② Fibonacci sequence
{1,1,2,3,5,8,13,…}
The third term is equal to the sum of the first two terms
Recursive export ： When n=1,n=2 when , The return values are 1;
Recursion ： In other cases , Returns the sum of the first two items , That is to say F（n-1）+F（n-2）;
Code ：

public static int FI(int n) {
		if(n==1) {
			return 1;
		}
		else if(n==2) {
			return 1;// Recursive export 
		}
		else
			return FI(n-1)+FI(n-2);// Recursion 
		
		
	}

③ An array of former n Xiang He
Recursive export ： When n=1 when , The output value is 1;
Recursion ： Other situations , Before output （n-1） Item and plus n Item value , That is to say sum(n-1)+n
Code ：

public static int sum(int n) {
		if(n==1) {
			return 1;// Recursive export 
		}
		else
			return sum(n-1)+n;// Recursion 
	}

recursive procedure ：
① Take the first number on the left as the base ;
② Define two pointers in the first and last positions ;
③ The next pointer moves first , Then it's better than the benchmark number , stop it ;
④ The front pointer moves backward , Find a number larger than the benchmark number , stop it ;
⑤ Data interchange
Code ：

public class QuickSort {
	public static void main(String[] args) {
		int[] arr=new int[] {5,9,2,1,7,6,3,4,8,0};
		qucik(arr,0,arr.length-1);
		System.out.println(Arrays.toString(arr));
	}
	public static void qucik(int arr[],int left,int right) {
		if(left>right) {
			return;
		}
		int base=arr[left];
		int i=left;
		int j=right;
		while(i!=j) {
			while(arr[j]>=base && i<j) {
				j--;
			}
			while(arr[i]<=base && i<j) {
				i++;
			}
			int temp=arr[i];
			arr[i]=arr[j];
			arr[j]=temp;	
		}
		arr[left]=arr[i];
		arr[i]=base;
		
		qucik(arr,left,i-1);
		qucik(arr,i+1,right);
		
	}
	
	

Result chart ：

5. Merge sort
Merge sort uses Divide and conquer method The main idea of , Sort mainly by looking for intermediate variables
Code ：

public static void main(String[] args){
		int[] arr=new int[] {5,8,2,1,7,6,3,4,9,0};
	
	}
	
	public static void fen(int arr,int left, int right) {
		if(left>right) {
			return ;
		}
		int mid=(left + right)/2;
		
		fen(arr,left,mid);
		fen(arr,mid+1,right);
		
	}
	public static void he(int[] arr,int left, int right,int mid) {
		int s1=left;
		int s2=mid+1;
		// Define a temporary array 
		int[] temp=new int[right-left+1];
		int index=0;
		// Put the small data in the two arrays into the temporary array 
		while(s1<mid && s2<=right) {
			if(arr[s1]<=arr[s2]){
				temp[index]=arr[s1];
				index ++;
				s1 ++;
			}
			else {
				temp[index]=arr[s1];
				index ++;
				s2 ++;
			}
		}
		while(s1<mid) {
			temp[index]=arr[s1];
			index ++;
			s1 ++;
		}
		while(s1<right) {
			temp[index]=arr[s1];
			index ++;
			s2 ++;
		}
		for(int j=0;j<temp.length;j++) {
			arr[j+left]=temp[j];
		}
		
		
	}
	

Result chart ：