Fast sorting is a sort of divide and conquer algorithm.

There are three steps to quick sort:

(1) . decomposition: divide the array num into three segments, with the first number as the benchmark, and put all the larger ones on the right and all the smaller ones on the left.

(2) . recursive solution: decompose and sort the three segments, left and right.

(3) . merge: when decomposing to three or two numbers, you can arrange the order locally. The sorting of each part will be combined to form the sorting of the whole array.

 

swap is used to exchange values, nothing to say

void swap(int num[],int i,int j)   //To exchange the values of i and j 
{
	int t = num[i];
	num[i] = num[j];
	num[j] = t;
}

partition(int num[],int p,int r) is used to partition an array from the number of p-r positions, and to give the subscript of the reference number

int partition(int num[],int p,int r)
{
	int x = num[p];      //First, we need to get the value of the first element 
	int i = p,j = r + 1;  
	
	//Swap < x elements to the left area and > x elements to the right area
	while(true)          
	{
		//Find the position with the number greater than x behind the first position, and note that i cannot exceed r
		while(num[++i] < x && i<r);         
		
		//Find the position of the number less than x in front of the tail position. There is no need to specify the limit here, because if they are all greater than x, then the ordered array will automatically jump out in the next step 
		while(num[--j] > x);	 
		if(i>=j) break;
		
		//Exchange < x and > x numbers 
		swap(num,i,j);
	}
	num[p] = num[j];        //After jumping out of the loop, we need to put x where it should be 
	num[j] = x;
	return j;
}

 

qSort(int num[], int p,int r) is used to sort. For an array of n elements, the range is [0, n-1]

void qSort(int num[],int p,int r)
{
	if(p<r)
	{
		// We return the subscript value according to the partition function. We can distinguish the left and right regions, so we can sort them again
		int q = partition(num,p,r);
		
		//Sort left   
		qSort(num,p,q-1);
		
		//Sort right		 
		qSort(num,q+1,r);		 
	}
}

 

Algorithm complexity analysis:

Considering the complexity of the algorithm, we must consider the worst case and the best case

Worst case:

In each partition, only n-1 elements and 1 element can be divided, so n recursions are needed. Because the calculation time of partition is O(n). So the worst-case time complexity of the algorithm is O(n 2) (if n > 1, when n is 1, only recursion once is O(1))

Best case:

Every time we divide the region, we divide two regions equally, so we only need to recurse log ψ n times, 8 times (3 times).... because the total time of recursion in each layer is O(n), so the optimal time complexity is O(n*log ψ n).

 

Code:

#include <iostream>
using namespace std;

void swap(int num[],int i,int j)   
{
	int t = num[i];
	num[i] = num[j];
	num[j] = t;
}

int partition(int num[],int p,int r)
{
	int x = num[p];      
	int i = p,j = r + 1;  
	
	while(true)          
	{
		while(num[++i] < x && i<r);         
		while(num[--j] > x);	 
		if(i>=j) break;
		swap(num,i,j);
	}
	num[p] = num[j]; 
	num[j] = x;
	return j;
}

void qSort(int num[],int p,int r)
{
	if(p<r)
	{
		int q = partition(num,p,r); 
		qSort(num,p,q-1);	 
		qSort(num,q+1,r);		  
	}
}

int main()
{
	int num[10] = {7,2,1,3,5,8,9,6,1,3};
	qSort(num,0,9);
	for(int i=0;i<10;i++)	
	{
		printf("%d ",num[i]);
	}
	return 0;
}