wiki

**What is quick sort?**

The definition of Wikipedia is: *quick sort, also known as ***partition exchange sort ***, abbreviated as ***fast ****sort ***, a ***sorting algorithm ***. Under average conditions, sort n items*

*Comparisons. In the worst case*

*Comparisons, but this situation is not common. In fact, quicksort is usually significantly faster than other algorithms because its inner loop can be achieved very efficiently on most architectures.*

step

**Quick sort steps**

Quicksort uses a **divide-and-conquer** strategy to divide a list into two sub-lists.

- Pick an element from the sequence and call it a "pivot",
- Reorder the sequence, all elements smaller than the reference value are placed in front of the reference, and all elements larger than the reference value are placed behind the reference (the same number can go to either side). After this partition is over, the benchmark is in the middle of the sequence. This is called a partition operation.
- Recursively sort the sub-sequences of elements smaller than the reference value and the sub-sequences of elements greater than the reference value.

**For example?**

For example, there is an array

96 69 1314 520 666

1. Selecting a base number is the privot mentioned earlier, a number with a relatively large size.

Generally, the last number is taken. Here we take **666** as the base number. Compare the numbers in the array with **666** in turn. Put the numbers smaller than **666** on the left, and put those larger than **666** on the right. This has the following results:

96 69 520 666 1314

2. Determine the number of intervals. After the first step, there is only one number in the right interval, and there is no number to compare with it, so there is no need to repeat the operation. The left interval also has:

96 69 520

3. Repeat step 1, select **520** as the benchmark number, and get the comparison result:

96 69 520

4. Repeat step 1, select **69** as the benchmark number, and get the comparison result:

69 96

5. In this way, there is only one number on the left and right intervals, which marks the completion of the sorting. Finally, all the intervals are combined to get the sorting result:

69 96 520 666 1314

Code

**Code!**

def quick_sort(lst): _less = [] # Store the value less than the base number _greater = [] # Store the value greater than the base number # Recursive functions must have exit conditions if len(lst) <= 1: return lst # Base number, directly get the last one of src _pivot = lst.pop() for _item in lst: if _item <= _pivot: _less.append(_item) else: _greater.append(_item) # The python list used here is a feature that can be added directly # Recursive thinking is very important, to deal with more than 1 in the list return quick_sort(_less) + [_pivot] + quick_sort(_greater)

The code uses a recursive approach, and there are some optimizations, such as using a generator to optimize the value acquisition of the list.

l = [69, 96, 520, 666, 1314] print(quick_sort(l)) [69, 96, 520, 666, 1314]

**If you are still interested in today's content, why not like it before leaving?**

**If you are interested enough to appreciate me, donâ€™t hesitate~**

Reference: https://cloud.tencent.com/developer/article/1153744 A taste of Python quick sort-Cloud + Community-Tencent Cloud