Divide and conquer learning of algorithm (fast sorting)

Overall thinking

Branch step: decompose the problem
(1) Decomposition: decompose the original problem into a series of subproblems
(2) Solution: solve each sub problem recursively. If the subproblem is small enough, there is a direct solution;
(3) Merging: merging the results of subproblems into the solutions of the original problems

subject

1. Quick sort

(1) Title

It's the quick sorting of arrays

(2) Code

package com.lanqiao.vidio;

public class QuickSort {
	public static void main(String[] args) {
		int[] A = {9,6,1,5,8};
		sort(A,0,A.length-1);
		for(int a:A)
		{
			System.out.print(a+" ");
		}
	}
	public static void sort(int[] A,int p,int r)
	{
		if(p<r)
		{
			int q=partition(A,p,r);
			sort(A,p,q-1);
			sort(A,q+1,r);
		}
	}

	private static int partition(int[] A, int p, int r) {
		int pivot = A[p];
		int sp = p+1;
		int bigger = r;
		while(sp<=bigger)
		{
			if(A[sp]<=pivot)
			{
				sp++;
			}else {
				int temp = A[sp];
				A[sp]=A[bigger];
				A[bigger]=temp;
				bigger--;
			}
		}
		int temp = A[p];
		A[p]= A[bigger];
		A[bigger]=temp;
		return bigger;
	}
}

(3) Thinking

(1) The thought of division and Administration
(2) Select a pivot and locate it
(3) Pivot ordered left
(4) Pivot right ordered
(5) Overall order

(4) Pivot points

(1) Determine the left and right pointers sp and bigger. If sp < pivot, the pointer moves forward. Otherwise, the bigger exchanges with the sp element, and the bigger moves forward until sp > bigger completes the comparison
(2) After the exchange is completed, a pivot position is found. bigger, the right side is smaller than the pivot element, and the right side is larger than the pivot element
(3) Bigger is where the current pivot is located. Return to bigger, sort on the left side, find the pivot, locate the left pivot, and sort on the right side until all the pivots are in order.

2. Two way scanning

1. Code:

package com.lanqiao.vidio;

public class QuickSort1 {
	public static void main(String[] args) {
		int[] A = {9,5,8,1,6};
		sort(A,0,A.length-1);
		for(int a:A)
		{
			System.out.print(a+" ");
		}
	}

	private static void sort(int[] A, int i, int j) {
		if(i<j) {
			int p = petition(A,i,j);
			sort(A,i,p-1);
			sort(A,p+1,j);
		}
	}

	private static int petition(int[] A, int i, int j) {
		int pivot = A[i];
		int left = i+1;
		int right = j;
		while(left<=right)
		{
			while(left<=right&&A[left]<=pivot) left++;//Find the first number on the left greater than pivot
			while(left<=right&&A[right]>pivot) right--;//Find the first number on the right less than or equal to pivot
			if(left<right)
			{
				int temp = A[left];
				A[left]=A[right];
				A[right]=temp;
			}
		}
		int temp = A[i];
		A[i]=A[right];
		A[right]=temp;
		return right;
	}
}

2. Note:

(1) Before entering the pivot selection method, first judge the relationship between i and j, otherwise J may have been < 0 and still judge, leading to out of bounds.
(2) pivot selection optimization: select maximum + minimum / 2

3. Odd even separation (odd first, even last)

1, topic

All elements in an array are separated so that the odd number is first and the even number is last, and the order of size is not concerned

2, code

package com.lanqiao.vidio;

public class jiou {
	public static void main(String[] args) {
		int[] arr = {1,4,2,3,5,8,7};
		merge(arr,0,arr.length-1);
		for(int a:arr)
		{
			System.out.print(a+" ");
		}
	}
	
	private static void merge(int[] arr, int i, int j) {
		int left = i;
		int right = j;
		while(left<right)
		{
			while(left<=right&&arr[left]%2!=0) left++;
			while(left<=right&&arr[right]%2==0) right--;
			if(left<=right) {
				int temp = arr[left];
				arr[left]=arr[right];
				arr[right]=temp;
			}
			
		}
	}
}

3, train of thought

(1) Similar to a fast row, two pointers point back and forth respectively, find the first odd number and the first even number, and exchange the order until the pointers cross

4. Attention points

(1) In the process of outer while loop, notice to judge left and right before exchange. It is possible to cross in the last time, and then exchange will destroy the order.

4. Find the number k

1, problems

Find the largest k element in an array with high efficiency

2, code

package com.lanqiao.vidio;

public class SelectK {
	public static void main(String[] args) {
		int[] arr = {8,5,4,9,3,6};
		int  a = select(arr,3,0,arr.length-1);
		System.out.println(a);
	}

	private static int select(int[] arr, int k,int i,int j) {
		int p = petition(arr,i,j);
		int pK = p+1;//Principal element is the first element
		
		if(pK>k)
		{
			return select(arr,k,i,p-1);//Pay attention to the return method or continue to execute
		}else if(pK<k){
			return select(arr,k-pK,p+1,j);//Find elements in new sequence
		}else if(pK==k)
		{
			return arr[p];
		}
		return -1;
	}

	private static int petition(int[] arr, int i, int j) {
		int pivot = arr[i];
		int left = i+1;
		int right = j;
		while(left<=right)
		{
			while(left<=right&&arr[left]<pivot) left++;
			while(left<=right&&arr[right]>pivot) right--;
			if(left<=right)
			{
				Utils.swap(arr, left, right);
			}
		}
		Utils.swap(arr, i, right);
		return right;
	}
}

3, train of thought

(1) Similar to fast platoon, fast platoon determines the location of the pivot every time, and the location + 1 is the largest element. When the size of the element to be found is less than the location + 1 of the pivot, only find it on the left side, and discard the right side

4. Attention points

(1) Every time you find a method, pay attention to the return method instead of calling the method directly
(2) When finding the right side of the pivot, when finding the elements in the new sequence, the location of the elements to be found is different from the original one, which is k-pK: k-p+1: that is, in the new sequence, the number of the elements to be found originally

5. Find more than half of the numbers in the array

1. Ideas:

(1) Since we are looking for more than half of the figures. There must be a number more than half of the total number. Find the ordered middle value.
(2) Using the algorithm to determine the k-th largest number, find the middle number

6. Find the minimum available ID

1, topic

In an array, arrange in disorder (but 1, 2, 3, 4 should all be), find a number that does not appear in the array and is the smallest

2, train of thought

(1) Find the middle element and see if its size = k+1 (k: element subscript)
(2) = k+1: the left half is close, i.e. all elements exist, abandon and find from the right half
(3) > K + 1: a half part is sparse, i.e. the element is missing. Look for it from the left half, repeat like this, and finally determine

7. Sorting time complexity

Published 23 original articles, won praise 11, visited 1928
Private letter follow

Tags: less

Posted on Sat, 01 Feb 2020 08:18:11 -0800 by Wo0tHigh