Quicksort is a very popular and widely used sorting method with a relatively simple implementation that achieves an average time complexity of $O(n log n) $ . Although the worst time complexity is the same as bubble sort as $O(n^2) $, this situation is very rare.
With a simple optimization implementation, Quicksort only needs $O(log n) $ of extra storage, which is more than its competitor mergesort . Ideal for sorting in the real world.
The basic features of Quicksort are as follows:
- The implementation is simple and fast.
- Unstable ordering : After sorting, the relative position of elements of the same key value may change.
- Non-in-place sorting : In addition to the data itself, additional storage space is required to sort.
- Divide and Algorithm : The main problem is turned into several sub-problems, each broken.
Quicksort is a divide-and-conquer algorithm that continuously returns the following three steps:
- Select Pivot: Choose an element in the sequence, called Pivot.
- Split sequence: Reorder the sequence into two parts. Before the transition is smaller than the pivot, the element larger than the pivot is replaced by the pivot, and the pivot itself is located in its final correct position.
- Recursively: Repeat __pivot _, and _pivot _ respectively to repeat the above steps until the length of the new sequence is less than or equal to 1, and the segmentation is complete.