Algorithm idea:

The divide and conquer strategy used by quicksort. The basic idea is to select a base number and place the smaller number on its left and the larger number on its right. After all the comparisons, the left and right sequences are sorted in this way again until one of the numbers in the sequence is the end.

Quicksort process:

  1. Choose the first number (any number) as the base number.
  2. Put smaller than the base number in front, larger than the base number in the back, and then put the base number in the middle.
  3. Using the recursion method, continue the sequence on the left and right until only one number in the sequence is the end of the recursion.

Time complexity:

Best: Nlog2 (n): Nlog2 (n): Nlog2 (n) Worst: n2 :n ^2: n2 Average: Nlog2 (n): Nlog2 (n): Nlog2 (n)

Algorithm implementation:

C + + code:

// Query the location of the base number
int FindPos(int a[],int l,int r)
{
	int key=a[l];// Select the first number as the base number
	while(l<r)
	{
		while(l<r)// Query the first value on the right which is less than key
		{
			if(a[r]<key) // Check whether the current value is less than key
			{
				a[l++]=a[r];// Store the current value on the right to the left
				break;
			}
			r--;// If the current right-hand value is greater than key, judge the previous one
		}
		while(l<r)// Query the first value on the left greater than key
		{
			if(a[l]>key)// Determine whether the current value is greater than key
			{
				a[r--]=a[l];// Save the current left value to the right
				break;
			}
			l++;// If the value on the left is greater than the value on the key, the value on the left is greater than the key
		}
	}
	a[l]=key;// Store the base number at the current location
	return l;
}
void QuickSort(int arr[],int l,int r)
{
	if(l>=r) return;// The end condition of recursion
	int pos=FindPos(arr,l,r);// Query the position of the datum in the current sequence
	QuickSort(arr,l,pos- 1);// Sort to the left of the reference position
	QuickSort(arr,pos+1,r);// Sort to the right of the reference position
}
Copy the code