No more nonsense , Look at the code first
#define _CRT_SECURE_NO_WARNINGS 1 // Quick sorting algorithm , Recursive solution #include <stdio.h> void
swap(int* a, int* b) { int c = 0; c = *a; *a = *b; *b = c; } void Compare(int
arr[], int one, int end) { int first = one;// Leftmost array subscript int last = end;// Rightmost array subscript
int key = first;// Scalar for comparison ( Select the first leftmost element ) if (first >= last) { return; } while
(first < last) { while (first < last && arr[last] >= arr[key])// Find a number smaller than the scalar on the right {
last--; } while (first < last && arr[first] <= arr[key])// Find a number larger than the scalar on the left { first++;
} if(first < last)// Analyze the values found by the exchange swap(&arr[first], &arr[last]); } if (first ==
last) { int mite = key;// Swap scalars to where they should go , Reselect scalar swap(&arr[mite], &arr[last]); }
Compare(arr,one,first-1);// Left recursive sort Compare(arr,first+1,end);// Recursive sort on the right } int
main() { int arr[] = { 5,4,6,5,2,1}; int i = 0; int len = sizeof(arr) / 4;
Compare(arr,i,len-1);// Pass the subscript of the first and last element for (i = 0; i < len; i++) { printf("%d ",
arr[i]); } return 0; }
First, what is a quick sort algorithm : Quick sort is by Tony · A sort algorithm developed by Hall . On average , sort n Items to Ο(nlogn) Secondary comparison . In the worst case, you need Ο(n2)
Secondary comparison , But this is not common . in fact , Quick sort is usually significantly better than others Ο(nlogn) Faster algorithm , Because of its internal loop (inner
loop) It can be implemented efficiently on most architectures .

The worst case scenario for quicksort is O(n²), For example, the fast arrangement of sequential sequence . But what is the expected time for its sharing O(nlogn), And O(nlogn)
The constant factor implied in the notation is very small , The specific complexity stability is equal to O(nlogn) The merge order is much smaller . therefore , For most random sequences with weak order , Quick sort is always better than merge sort .

Quick sort uses divide and conquer (Divide and conquer) Strategy to put a serial (list) It is divided into two subseries (sub-lists)

Simply put , Select a benchmark ( Select the first data here ), Compare with other data , Put the smaller one in front of it , The bigger one is behind it . Then it is divided into two parts based on this benchmark ( The bigger part , A smaller part ), Select the benchmark of the two parts respectively , Then compare , Divide after comparison , Repeat , Until there is only one data in each part , End of sorting .

graphic -->

Code explanation :< Using recursion >

1, First, you need to create an array , Array first data subscript , The last data subscript has three parameters , Arrays are used to store data , Then create a Compare() Quick sort function , Finally, print out the ordered sequence we need .
int main() { int arr[] = { 5,4,6,5,2,1}; int i = 0; int len = sizeof(arr) / 4;
Compare(arr,i,len-1);// Pass the subscript of the first and last element for (i = 0; i < len; i++) { printf("%d ",
arr[i]); } return 0;
2,Compare() Function creation

Unsigned return types are used here , Because no return value is required

To ensure that the subscripts of the first and last elements of the array remain unchanged , establish first and last Two local variables record the subscripts of the first and last elements of the array

establish key The subscript data is used as the benchmark
void Compare(int arr[], int one, int end) { int first = one;// Leftmost array subscript int last
= end;// Rightmost array subscript int key = first;// Scalar for comparison ( Select the first element on the far left )
3, First, judge whether the sequence has only one element , If there is only one element , The function ends .

4, Start to implement the main comparison part of the function

4.1, If the first data on the left is selected as the benchmark , Start from the right ,

4.2, Start with the first data on the right key Compare , If it is larger than it, continue to compare to the right (last--), Until we find a better one key Small data , Then stop .

4.3, Now start from the left key compare , If than key Small, continue to compare (first++), If than key Larger than the one found on the right key Exchange large numbers . Then keep looking on the right , Repeat the above steps .

4.4, until first>=last Time , Stop looking , And exchange at this time first Subscript data and key Value of

4.5, Divide and conquer thought , At this time key Subscript array as boundary , Divided into larger ones , Two smaller parts , Repeat the above steps before , Until there is only one data , Stop sorting . Recursive solution .
void Compare(int arr[], int one, int end) { int first = one;// Leftmost array subscript int last
= end;// Rightmost array subscript int key = first;// Scalar for comparison ( Select the first leftmost element ) if (first >= last) {
return; } while (first < last) { while (first < last && arr[last] >=
arr[key])// Find a number smaller than the scalar on the right { last--; } while (first < last && arr[first] <=
arr[key])// Find a number larger than the scalar on the left { first++; } if(first < last)// Analyze the values found by the exchange swap(&arr[first],
&arr[last]); } if (first == last) { int mite = key;// Swap scalars to where they should be , Reselect scalar
swap(&arr[mite], &arr[last]); } Compare(arr,one,first-1);// Left recursive sort
Compare(arr,first+1,end);// Recursive sort on the right }
swap() Exchange function , Because it needs to affect values outside the exchange function , Use pointer parameters .
void swap(int* a, int* b) { int c = 0; c = *a; *a = *b; *b = c; }

Technology
©2019-2020 Toolsou All rights reserved,
C++ of string of compare usage Python Study notes ( one )evo Tool usage problems ——Degenerate covariance rank, Umeyama alignment is not possibleRISC-V_GD32VF103-TIMER0 timer interrupt java Array subscript variable _Java Basic grammar : array be based on stm32 Control four-wheel trolley motor drive ( one ) be based on redis Design of liking function Software engineering career planning mysql Query random data by conditions _MySQL Random query of several qualified records centos7 install RabbitMq