Basic idea of quick sorting (easy to understand + examples) "suggestions collection"

Hello everyone , I meet you again , I'm your friend, Quan Jun .

Quick sort

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Today, I saw a quick sorting article written by the great God Blog , awe , I think it's so simple to sort quickly Let's have a simple try

The basic idea of quick sorting is

1、 Take a number from the sequence as the reference number first

2、 Partition process , Put all the larger numbers to the right of it , Less than or equal to its number all put it to the left

3、 Repeat the second step for the left and right sections , Until there is only one number in each interval

To sum up, it is Number of pits to be filled + Divide and conquer method

Here are some examples , There are three main parameters ,i Is the starting address of the interval ,j Is the end address of the interval ,X Is the current starting value

First step ,i=0,j=9,X=21

0	1	2	3	4	5	6	7	8	9
21	32	43	98	54	45	23	4	66	86

The second step , from j Start with , Look back and forward , Find the ratio X The small first number a[7]=4, here i=0,j=6,X=21 Replace

0	1	2	3	4	5	6	7	8	9
4	32	43	98	54	45	23	21	66	86

The third step , Look from front to back , Find the ratio X The first big number a[1]=32, here i=2,j=6,X=21

0	1	2	3	4	5	6	7	8	9
4	21	43	98	54	45	23	32	66	86

Step four , from j=6 Start with , From the back to the front , Find the ratio X The small first number a[0]=4, here i=2,j=0,X=21, Find out j<=i, So the first round ends

You can find 21 The previous numbers are better than 21 Small , The following numbers are better than 21 Big Next, for two subintervals [0,0] and [2,9] Repeat the above operation

The process is given directly below , I'll explain it in detail

i=2,j=6,X=43

0	1	2	3	4	5	6	7	8	9
4	21	43	98	54	45	23	32	66	86

i=4,j=6,X=43

0	1	2	3	4	5	6	7	8	9
4	21	32	98	54	45	23	43	66	86

i=4,j=5,x=43

0	1	2	3	4	5	6	7	8	9
4	21	32	43	54	45	23	98	66	86

i=5,j=5,x=43

0	1	2	3	4	5	6	7	8	9
4	21	32	23	43	45	54	98	66	86

Then it is divided into two sub intervals [2,3] and [5,9]

… The final order is the final answer

0	1	2	3	4	5	6	7	8	9
4	21	23	32	43	45	54	66	86	98

summary ：

1．i =L; j = R; The first pit will be excavated a[i].

2．j– Find a smaller number from back to front , After finding it, dig out this number and fill the previous pit a[i] in .

3．i++ Find a larger number from front to back , After finding it, dig out this number and fill it in the previous pit a[j] in .

4． And repeat 2,3 Two steps , until i==j, Fill the reference number in a[i] in .

---

Code

class Solution { 
   
	public void sort(int left,int right,int[] array) { 
   
		if (left>=right) return ;
		int start=left;
		int end=right;
		int flag=left;
		while(left<right) { 
   
			while ((left<right)&&(array[right]>=array[flag])) { 
   
				right--;
			}
			if (array[right]<array[flag]) { 
   
				int tmp=array[right];
				array[right]=array[flag];
				array[flag]=tmp;
				flag=right;
			}
			while ((left<right)&&(array[left]<=array[flag])) { 
   
				left++;
				}
			if (array[left]>array[flag]) { 
   
				int tmp=array[left];
				array[left]=array[flag];
				array[flag]=tmp;
				flag=left;
			}
		}
		sort(start, left-1, array);
		sort(left+1, end, array);
	}
}

Copy

Share an awesome learning java Website , Basic knowledge and architecture , Connect as follows ： http://how2j.cn?p=54321

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/148426.html Link to the original text ：https://javaforall.cn