This is the fifth day of my participation in the August More text Challenge. For details, see:August is more challenging

If you want to keep writing, write a series. What can I write about? Program = algorithm + data structure, which shows the importance of algorithm. This series of old poems tries to explain the algorithm clearly in the simplest language, from shallow to deep, if you are interested, you can pay attention to the column.

In interviews, quicksort algorithms are often tested. The examiner may not ask you to write quicksort by hand, but you have to explain how it works. Important things need to be remembered and repeated.

Description of quicksort algorithm

1 starts by setting a delimiter that separates the left and right parts of the array.

2 places numbers greater than or equal to the boundary value to the right of the boundary value and vice versa.

3 Then, the data on the left and right can be sorted independently. For the left array data, we can take a boundary value and divide the part of the data into the left and right parts. Similarly, we can put a smaller value on the left and a larger value on the right. You can do the same thing with the array data on the right.

4 Repeat the above process, and you can see that this is a recursive definition. After recursively sorting the left part, recursively sorting the right part. When the left and right parts are sorted, the whole array is sorted.

Quicksort diagram

Let’s say we start with the sequence x array: 5,3,7,6,4,1,0,2,9,10,8.

First, ref=5, I =1, j=10, the first number smaller than 5 is x8=2, so the sequence is: 2, 3, 7, 6, 4, 1, 0, 5, 9, 10, 8.

I =1, j=8, and the first number greater than 5 is x3=7, so the sequence is 2,3,5,6,4,1,0,7,9,10,8.

In this case, I =3, j=8, from the 8th place, the first number less than 5 is x7=0, so 2,3,0,6,4,1,5,7,9,10,8.

In this case, I =3, j=7, from the third place, the first number greater than 5 is x4=6, so 2,3,0,5,4,1,6,7,9,10,8.

In this case, I =4, j=7, from the 7th place, the first number less than 5 is x6=1, so 2,3,0,1,4,5,6,7,9,10,8.

In this case, I =4, j=6, from the fourth place to the sixth place, there is no number larger than 5, in this case, I =j=6, ref becomes a dividing line, the numbers before it are smaller than it, and the numbers after it are larger than it, you can use the same method to sort the fractions before and after it.

Quicksort implementation

#include <iostream> using namespace std; void Qsort(int arr[], int low, int high){ if (high <= low) return; int i = low; int j = high + 1; int key = arr[low]; While (arr[++ I] < key) {if (I == high){break; }} /* while (arr[--j] > key) {if (j == low){break; } } if (i >= j) break; Int temp = arr[I]; int temp = arr[I]; arr[i] = arr[j]; arr[j] = temp; } /* int temp = arr[low]; arr[low] = arr[j]; arr[j] = temp; Qsort(arr, low, j - 1); Qsort(arr, j + 1, high); } int main() { int a[] = {57, 68, 59, 52, 72, 28, 96, 33, 24}; Qsort(a, 0, sizeof(a) / sizeof(a[0]) - 1); /* for(int I = 0; i < sizeof(a) / sizeof(a[0]); i++) { cout << a[i] << " "; } return 0; }/* Reference data structure p274(Tsinghua University Press, Yan Weimin)*/Copy the code

Quicksort is one of the most common interview sorting algorithms I’ve seen, so if you need an interview, try to find out.

To learn more algorithm problems, or to more project source code, please move to the public number: poetic code.

Now that I’m in. Let’s go with a “like”.