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.
Quick sort steps
Quicksort uses a divide-and-conquer strategy to divide a list into two sub-lists.
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:
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
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~