[1. quick sort]

Quick sort

Ideas ：

1. Determine the cut-off point ：q[l] , q[(1 + r)/2] , q[r] , Random
2. Adjust the range of the interval ： Make in On the left side of the dividing point is the number all <= x, The numbers on the right of the dividing point are all >= x ( Key treatment )
3. Recursively handle the left and right segments

Method 1： The realization idea of violence method

1. Create two arrays a[ ] , b[ ]
2. Traverse q[l ~ r] , If the current q[i] <= x , Just insert into the array a[ ] in , If the current q[i] >= x , Just insert into the array b[] in .
3. take a[ ] Put the number in q[ ] in , And then b[ ] Put the number in q[ ] in , here q[ ] The numbers are ordered .

characteristic ：

1. It takes two extra spaces a[ ] , b[ ]
2. The time complexity is still O(n)

Method 2： Realization of double pointer

1. Two hands i , j One pointing to the left , The other one points to the right , Two hands At the same time, go to the middle
2. as long as i < x, here i Go to Right Move a bit , Until I met i >= x , here i Stop moving , Start moving j , as long as j > x, j Just go Left Move a bit , until j <= x , here j Stop moving . In exchange for i and j After the value of , Pointer all the way Move one bit in the middle .
3. until i and j Meet or pass through . here i The numbers on the left are <= x , j The numbers on the right are >= x.
4. Compare the number on the left with the number on the right , Continue recursion separately , Repeat the above steps .

give an example

subject

Give you a length of n The whole number sequence of .
Please use quick sort to sort this sequence from small to large .
And output the ordered sequence in order .


Input format
There are two lines of input , The first line contains integers n.
The second line contains n It's an integer （ All integers are in 1∼109 Within the scope of ）, Represents the whole sequence of numbers .


Output format
The output is one line , contain n It's an integer , It's an ordered sequence .


Data range
1 ≤ n ≤ 100000


sample input ：

5
3 1 2 4 5

sample output ：

1 2 3 4 5

Code

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
int n;
int q[N];

void quick_sort(int q[], int l, int r)
{
     
if (l >= r) return;
 int x = q[(l + r) / 2], i = l -1 ,j = r + 1;      // Set the dividing point 
  while (i < j)                                    // Loop traversal , When i  And  j  If it overlaps or crosses, it exits 
   {
     
       do i ++; while (q[i] < x);
       do j --; while (q[j] > x); 
       if (i < j) swap(q[i], q[j]);
     } 
     quick_sort(q, l ,j);                          // Recursive two sides respectively 
     quick_sort(q, j + 1, r);
}

int main()
 {
     
     int i;
     scanf("%d", &n);
     for (i = 0; i < n; i ++) scanf("%d", &q[i]);
     
     quick_sort(q, 0, n - 1);
     
     for (i = 0; i < n; i ++) printf("%d ", q[i]);
     return 0;
}

In addition to using do while, You can also use while loop

void quick_sort(int array[], int low, int high)
{
     
     int i = low; 
     int j = high;
     if(i >= j) 
     {
     
         return;
     }
	 int temp = array[low];
	 while(i <= j) 
	{
     
		 while(array[j] >= temp && i < j)
		 {
     
 				  j--;
    	 }
	 	 while(array[i] <= temp && i < j) 
	 	 {
     
   			      i++;
	 	 }
		 if(i < j) 
	 	 {
     
   	     swap(array[i], array[j]);
   	     }
    }
     // Benchmark temp Put it in your place ,（ The first i A place ）
	swap(array[low], array[i]);
	quick_sort(array, low, i - 1);
	quick_sort(array, i + 1, high);
}