Note: all the data used in my test are of the type that can be compared in size without duplicate elements, and the sorting is in ascending order.
In fact, the idea of fast sorting is very similar to bubble sorting. Bubble sorting is to complete the sorting through the continuous exchange between two adjacent elements. I think fast sorting can be understood as starting from two adjacent elements and then developing to two adjacent array segments for backtracking and comparison, and finally complete the sorting.

1. Algorithm description of quick sorting

Like merge sort, fast sort uses the typical idea of recursion - divide and conquer. I first select a pivot element as the intermediate element, and the elements not larger than it are placed on the left, and the elements not smaller than it are placed on the right. Because I sort a random number array, I select the first element for each sorting as the pivot element. When the sorted elements are not random, I can use the three median score method to select the pivot element. When the element segmentation is completed, put the pivot element in the middle of the left and right array segments, and then sort recursively in the left and right array segments. When there is only one element to be sorted, the sorting is completed.

2. Function implementation of quick sorting

Fast scheduling function:
First, judge the size relationship between the start position and the end position. If the start position is greater than the end position, it means that there is only one element without sorting. Then, declare two variables i and j respectively, record the start position and end position, and select the first element as the hub element. Carry out a cycle with equal termination conditions i and J. in the cycle, if i is less than j, move J to the first element subscript less than the hub element encountered each time, and then move i to the first element subscript greater than the hub element encountered, and the moving order cannot be reversed, because moving i first may cause the situation that i is greater than J, At that time, the exchange hub location will be wrong. Then, in the case of i < J, exchange the two unit elements, so that the elements not larger than the hub element enter the left and the elements not smaller than the hub element enter the right (considering the case of equal elements, the special treatment of boundary conditions is avoided through redundant exchange, which enhances the robustness of the program). When the cycle ends, the element segmentation is completed, Move the pivot element to the middle of the left and right array segments, and then sort the left and right array segments recursively.

/*Some statements
typedef int ElementType;
const int N=1000;
*/
void QuickSort(ElementType a[],int begin,int end){
	if(begin>end) return ;				//Only one element does not need to be sorted
	int i=begin,j=end;
	ElementType temp=a[begin],t;  /*Because this sorting is a random number array, the data is random,
Therefore, the first element can be directly used as the hub element, otherwise the hub element can be determined by the three median value method*/ 
	while(i!=j){		//When i equals j, it means that the elements on both sides have been divided and the cycle ends 
/*The order of the two loops cannot be reversed. The first loop looks for the subscript of the element larger than the pivot element on the left every time,
The second loop looks for the subscript of the element smaller than the pivot element on the right each time*/		
		while(a[j]>=temp&&j>i) j--;	 
		while(a[i]<=temp&&j>i) i++;	
		if(i<j){		//Write explicitly to avoid calling exchange functions and improve sorting speed 
			t=a[i];
			a[i]=a[j];
			a[j]=t;
		}
	}	/*The next two steps are to move the pivot element to the appropriate position, because the element on the left after the cycle is completed
 Less than or equal to the hub element, and the element on the right is greater than or equal to the hub element, so the hub element does not need to enter the sorting*/ 
	a[begin]=a[i];
	a[i]=temp;
	QuickSort(a,begin,i-1);	//Sort elements on the left of pivot element 
	QuickSort(a,i+1,end);				//Sort elements on the right of pivot element 
}

3. Analysis of quick sort

3.1 time complexity analysis

The running time of quick sort depends on whether the partition is balanced. When the partition is unbalanced, the performance of quick sort will drop to close to insertion sort. If the partition is balanced, the performance of quick sort is the same as merge sort. Therefore, the worst time complexity of quick sorting is O (N) ²), The average time complexity is O(nlogn). Therefore, using the first subscript of the array as the hub element is usually a bad method, because if the data is not random, it will lead to unbalanced division and reduce the fast scheduling performance. A better method is to select the hub element by using the three-point median method.

3.2 operation example analysis

Here, I generate an array of random numbers from 1 to N. the selection of n is 10000001000000000000, which is too small and the running time is too short. Note that the array should be declared outside the main function. The length of the array declared in the main function should not be too large, because the local variables in the main function are placed in the stack section, and too many local variables will lead to stack overflow.
Function to generate random array:

void Randomize(ElementType num[],int length){
	int i=0;
	srand((ElementType)time(NULL));
	for(;i<length;i++) num[i]=i+1;
	for(i=length-1;i>0;i--) Swap(&num[i],&num[rand()%i]);
} 
void Swap(ElementType* a,ElementType* b){
	ElementType temp=*a;
	*a=*b;
	*b=temp;
}

Average time of 10 runs under different array lengths:

10000	100000	1000000
0.002	0.0245	0.2697

3.3 overall code

#include<stdio.h>
#include<stdlib.h>
#include<time.h>
typedef int ElementType;
const int N=1000000;
ElementType num[N]={0};
void Swap(ElementType*,ElementType*);
void Randomize(ElementType [],int);
void QuickSort(ElementType [],int,int);
int main(void){
	clock_t start=0,finish=0;
	Randomize(num,N);
	start=clock();
	QuickSort(num,0,N-1);
	finish=clock();
	//for(int i=0;i<N;i++) printf("%d\n",num[i]);
	printf("time is:\n%lf",(double)(finish-start)/CLOCKS_PER_SEC);
	return 0;
}
void QuickSort(ElementType a[],int begin,int end){
	if(begin>end) return ;				//Only one element does not need to be sorted
	int i=begin,j=end;
	ElementType temp=a[begin],t;  /*Because this sorting is a random number array, the data is random,
Therefore, the first element can be directly used as the hub element, otherwise the hub element can be determined by the three median value method*/ 
	while(i!=j){		//When i equals j, it means that the elements on both sides have been divided and the cycle ends 
/*The order of the two loops cannot be reversed. The first loop looks for the subscript of the element larger than the pivot element on the left every time,
The second loop looks for the subscript of the element smaller than the pivot element on the right each time*/		
		while(a[j]>=temp&&j>i) j--;	 
		while(a[i]<=temp&&j>i) i++;	
		if(i<j){		//Write explicitly to avoid calling exchange functions and improve sorting speed 
			t=a[i];
			a[i]=a[j];
			a[j]=t;
		}
	}	/*The next two steps are to move the pivot element to the appropriate position, because the element on the left after the cycle is completed
 Less than or equal to the hub element, and the element on the right is greater than or equal to the hub element, so the hub element does not need to enter the sorting*/ 
	a[begin]=a[i];
	a[i]=temp;
	QuickSort(a,begin,i-1);	//Sort elements on the left of pivot element 
	QuickSort(a,i+1,end);				//Sort elements on the right of pivot element 
}
void Swap(ElementType* x,ElementType* y){
	ElementType temp=*x;
	*x=*y;
	*y=temp;
}
void Randomize(ElementType a[],int length){
	srand((ElementType)time(NULL));
	for(int i=0;i<length;i++) a[i]=i+1;
	for(int i=length-1;i>0;i--) Swap(&a[i],&a[rand()%i]);
}

summary

Quick sort is a sort algorithm with fast running speed. Although its worst case is close to insertion sort, it can avoid the worst case with a little effort. In terms of time complexity, the average time complexity of quick sorting is O(nlogn), and in terms of space complexity, the average space complexity of quick sorting is O(logn). Although fast sorting is not as stable as merge sorting, the space complexity of merge sorting is high, and the worst case can be avoided with a little effort. In general, the average time and space complexity of fast scheduling are relatively good. It is a widely used sorting algorithm.