前言
在上一期,我们学习了希尔排序以及插入排序。今天给大家带来的是被加入 C 语言库里的排序算法——快速排序。
一、快速排序(初阶)
1. 算法思想
快速排序有一个 key 值,叫基准元素,可以理解为就是要排序数组的第一个数字。在第一次快速排序结束后,这个 key 值位置发生改变,其他元素位置也发生一定改变。最后在 key 的左边都是小于 key 的数,在 key 的右边都是大于 key 的数。这就是一次快速排序,此时 key 的顺序就被排好了,后续也不需要动。然后,将整个数组以 key 分成两个左右两个区间,并在这两个区间循环刚刚的步骤,直到区间不可再分(区间只剩一个元素),此时排序结束。
一句话总结,快速排序就是不断将比 key 小的数放左边,把比 key 大的数放右边,最后完成排序。
2. 实现思路
(1)定 key 值
第一步:定 key 值。快速排序有一个 key 值,叫基准元素,现在可以理解为就是第一个数字(后续还会再改进)。后续的排序就是围绕这个基准元素 key 来进行的。
(2)大小交换
第二步:大小交换。我们可以发现,视频中有两个小人,一个从左边往右走,一个从右往左走。先右小人一直向左走,直到遇到比 key 大的数停下;再左小人一直向右走,直到遇到比 key 小的数停下。当两小人都停下后,两小人所对应的值就互相交换,大的数换到右边,小的数换到左边。
(3)循环
第三步:循环。两小人继续一个左走,一个右走,满足条件时继续交换,然后重复,直到两小人相遇循环停止。
(4)交换 key
第四步:交换 key。此时将 key 与两小人相遇点的值进行交换。此时在 key 的左边都是小于 key 的数,在 key 的右边都是大于 key 的数。此时 key 就已经排好序,后续也不需要再动,第一轮快速排序结束。
(5)分割区间
第五步:分割区间。现在,key 就已经排好序,后续也不需要再动。此时将 key 左右的区间分割开来,分成左右两个区间。然后分别对这两个区间重复第一轮的排序:定 key 值、大小交换、循环、交换 key、分割区间。
(6)结束
第六步:结束。当每个区间分割成只剩下一个元素时,自然也不需要继续循环,就可以跳出循环。当所有的区间都只剩下一个元素时,都跳出循环时,排序也就完成了。
3. 实现代码
void QuickSort1(int* a, int left, int right) {
if (left >= right) // 判断是否继续,当区间只有一个数时跳出循环
return;
int key = left; // 确定 key 的值,为第一个元素
int L = left;
int R = right; // 先将左右的下标记录下来,以免后面丢失
(left < right) {
(left < right && a[right] >= a[key])
right--;
(left < right && a[left] <= a[key])
left++;
Swap(&a[left], &a[right]);
}
Swap(&a[right], &a[key]);
key = right;
QuickSort1(a, L, key - );
QuickSort1(a, key + , R);
}


