<Data Structure/Algorithm> 1.快速排序Quick Sort
快速排序Quick Sort
In fact, quicksort had always been a bit confusing to me, but after much thought, I finally had a breakthrough.
First of all, quicksort is a recursive algorithm. The core idea is to select a pivot in a sequence, partition the elements into two groups such that all elements on the left are smaller than the pivot and all elements on the right are greater than the pivot, and then recursively apply the same procedure to both sides.
So how do we actually perform this “partitioning into left and right”? The simplest approach works like this:
- Set up two pointers: a fast pointer and a slow pointer. The fast pointer is used for iteration, while the slow pointer marks a position.
- What position does the slow pointer mark? It’s the location where the next element smaller than the pivot should be placed.
- How is this position determined? Starting from the leftmost element, whenever we encounter an element smaller than the pivot, we place it at the left side and move the slow pointer one step to the right. Essentially, we put it at the current slow position, then increment
slow++
. - But what about the original element at the slow position? We simply swap it with the element currently pointed to by the fast pointer (the one that is smaller than the pivot).
- By doing this throughout the iteration, all elements smaller than the pivot are moved to the left side. The remaining larger elements naturally end up on the right side.
- However, we still need to handle the pivot itself. Typically, the pivot is chosen as either the leftmost or rightmost element, and we skip it during the iteration. For example, if we choose the leftmost element as the pivot, we start the loop from the second element. If we choose the rightmost element, the loop stops at the second-to-last element.
- Finally, the pivot needs to be placed in the middle, and the slow pointer happens to be right at the correct position. We just swap the pivot with the slow pointer. There are two possible approaches here:
- Approach 1: Swap first, then increment
slow
. In this case, after the loop ends,slow
points to the first element greater than the pivot (the leftmost element of the right partition). If the pivot was the left endpoint, swap it withslow - 1
so that the pivot ends up between the two partitions. If the pivot was the right endpoint, swap it directly withslow
, placing the pivot correctly between the two partitions. - Approach 2: Increment
slow
first, then swap. In this version, each swap is preceded byslow++
, meaning that after the loop ends,slow
points to the last element smaller than the pivot. The handling of pivot placement is similar to the first approach.
- Approach 1: Swap first, then increment
Here is the C++ code:
1 |
|
中文原文
事实上对于快速排序一直以来都是懵懵的,苦想后终于茅塞顿开。首先,快速排序是一个递归的算法,核心思想是在一个序列中选择一个分界值(Pivot),将该序列中的元素划分为左右两部分,左边的元素均小于分界值,右边的元素大于分界值。然后对左右两边分别递归地执行此操作。
那么怎样执行这个“分成左右两边”的操作呢?目前最简洁的方法是这样的。
- 设立一个快指针fast,一个慢指针slow。快指针用于循环,慢指针用于指向一个位置。
- 指向的位置是什么呢?就是下一次遇到比pivot值小的元素时,应该把它填在哪里。
- 那么这个位置怎么确定呢,很简单,从序列最左边开始,每找到一个比pivot值小的元素就放到左边,然后往右挪一下就行了。对应到slow指针也就是每次往slow指针位置放,然后slow++。
- 那么原来位置上的元素怎么办呢?直接和当前这个快指针指向的元素,也就是那个比pivot值小的元素,互换位置就好了。
- 这样做,遍历一遍后,比pivot小的值都往左边不断地堆放,最后全在左边了。剩下的比pivot大的值自然就跑到右边去了。
- 但是还有一个pivot值没有处理,这个值往往是选择序列最左边或者最右边的元素,我们在刚刚的遍历中直接略过。也就是如果选了最左边的元素,一开始遍历就直接从第二个元素开始了。如果是最右边的元素,遍历的时候就到倒数第二个元素停止。
- 最后剩下的slow元素,很明显是要放到中间的。注意到这个时候slow指针正好就在中间,交换位置即可。这里有两种情况:
- 一种是每次交换后slow再++,也就是下一次放就是直接放到slow的位置。这种情况下遍历结束后的slow应该是指向第一个比pivot大的元素,也就是右边序列的最左端。如果pivot是左端点则需要和slow-1位置互换,这样把slow-1也就是最后一个比pivot小的值换到最前面,如果pivot是右端点则直接和slow互换,这样把第一个比pivot大的值换到最后面。
- 第二种是先slow++再交换,这样每一次交换前需要先把slow++挪到下一个位置。这种情况下遍历结束后的slow就是最后一个比pivot小的元素。对于两种pivot位置和第一种情况同理。
以下是C++代码:
1 |
|
其实就是这么简单的道理,不知道自己以前为什么那么久没搞明白,还是太菜了。
<Data Structure/Algorithm> 1.快速排序Quick Sort
install_url
to use ShareThis. Please set it in _config.yml
.