拓展：快速排序详解及应用
Info
已完成网站教程、网站习题、配套插件中所有多语言代码的校准，解决了之前 chatGPT 翻译可能出错的问题~
读完本文，你不仅学会了算法套路，还可以顺便解决如下题目：
| LeetCode | Difficulty |
|---|---|
| 215. Kth Largest Element in an Array | 🟠 |
| 912. Sort an Array | 🟠 |
Prerequisites
Before reading this article, you should first learn:
In the previous article Detailed Explanation of Merge Sort Algorithm, the principles and applications of the merge sort algorithm were described from the perspective of binary trees. Many readers found it ingenious. So, I will capitalize on this momentum and today, continue to explain the principles and applications of the quicksort algorithm using the perspective of binary trees.
QuickSort Algorithm Approach
First, let's take a look at the code framework of quicksort:
void sort(int[] nums, int lo, int hi) {
if (lo >= hi) {
return;
}
// partition the nums[lo..hi]
// such that nums[lo..p-1] <= nums[p] < nums[p+1..hi]
int p = partition(nums, lo, hi);
// recursively partition the left and right subarrays
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}void sort(int nums[], int lo, int hi) {
if (lo >= hi) {
return;
}
// partition the nums[lo..hi]
// such that nums[lo..p-1] <= nums[p] < nums[p+1..hi]
int p = partition(nums, lo, hi);
// recursively partition the left and right subarrays
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
}def sort(nums: List[int], lo: int, hi: int):
if lo >= hi:
return
# partition the nums[lo..hi]
# such that nums[lo..p-1] <= nums[p] < nums[p+1..hi]
p = partition(nums, lo, hi)
# recursively partition the left and right subarrays
sort(nums, lo, p - 1)
sort(nums, p + 1, hi)func sort(nums []int, lo int, hi int) {
if lo >= hi {
return
}
// partition the nums[lo..hi]
// such that nums[lo..p-1] <= nums[p] < nums[p+1..hi]
p := partition(nums, lo, hi)
// recursively partition the left and right subarrays
sort(nums, lo, p-1)
sort(nums, p+1, hi)
}var sort = function(nums, lo, hi) {
if (lo >= hi) {
return;
}
// partition the nums[lo..hi]
// make nums[lo..p-1] <= nums[p] < nums[p+1..hi]
var p = partition(nums, lo, hi);
// recursively partition the left and right subarrays
sort(nums, lo, p - 1);
sort(nums, p + 1, hi);
};In fact, if you compare them, you'll find that quicksort is essentially a preorder traversal of a binary tree:
// Binary tree traversal framework
void traverse(TreeNode root) {
if (root == null) {
return;
}
// ***** Pre-order position *****
print(root.val);
// *******************
traverse(root.left);
traverse(root.right);
}// Binary tree traversal framework
void traverse(TreeNode* root) {
if (root == nullptr) {
return;
}
// ***** Pre-order position *****
cout << root->val << endl;
// *******************
traverse(root->left);
traverse(root->right);
}# Binary tree traversal framework
def traverse(root: TreeNode):
if not root:
return
# Pre-order position
print(root.val)
traverse(root.left)
traverse(root.right)// Binary tree traversal framework
func traverse(root *TreeNode) {
if root == nil {
return
}
// Pre-order position
fmt.Println(root.Val)
traverse(root.Left)
traverse(root.Right)
}// Binary tree traversal framework
var traverse = function(root) {
if (root === null) {
return;
}
// ***** Pre-order position *****
console.log(root.val);
// *******************
traverse(root.left);
traverse(root.right);
};Additionally, in the previous article 归并排序详解, I summarized merge sort in one sentence: first sort the left half of the array, then sort the right half, and finally merge the two halves.
At the same time, I posed a question, asking you to summarize quicksort in one sentence. Here is my answer:
Quicksort is about sorting one element first, and then sorting the remaining elements.
Why do I say this? Let me explain step by step.
The core of quicksort is the partition function. The role of the partition function is to find a pivot point p in nums[lo..hi] and rearrange the elements so that nums[lo..p-1] are all less than or equal to nums[p], and nums[p+1..hi] are all greater than nums[p]:
If all elements to the left of an element are smaller and all elements to the right are larger, what does that mean? It means that the element itself has been placed in the correct position, right?
So, what the partition function does is essentially sort the nums[p] element.
Once one element is sorted, what next? You just need to sort the remaining elements.
Which elements are left? A bunch on the left and a bunch on the right. Go ahead, recursively sort the subarrays using the partition function to sort the remaining elements.
From a binary tree perspective, we can think of the subarray nums[lo..hi] as the values in the nodes of a binary tree, and the sort function as a traversal function of the binary tree.
Referring to the pre-order traversal of a binary tree, the process of quicksort is illustrated in the following GIF: