快速排序
以升序为例
何为快速排序
- 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法。
- 基本思想：任取待排序元素序列中的某个元素作为基准值，按照该排序码将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
- 例如下图就是将数字“5”放在正确位置上的过程
- 将区间按照基准值划分为左右两半部分的常见方法有：
方法一：挖坑法
- 挖坑法顾名思义，就是在待排数组的某一特定位置“挖坑”，然后用另外的元素填坑，从而达到将区间按照基准值划分为左右两半部分的目的
实现的基本思想
处理第一个数
- 由于现在还没有数据处在正确的位置，因此排序区间是整个数组的长度
- 可以将待排数组的第一个数（最左边的数）作为基准值key，同时将这个位置设为坑pivot
- 设区间最左边的下标为left，最右边的下标为right，此时坑的位置即最左边left
int key = nums[0]; //基准值 int pivot = 0; //坑的位置 int left = 0; //区间最左边 int right = numsSize - 1; //区间最右边
- 由于是升序排序，要做到基准值key左边的元素全小于key，右边的元素全大于key。而坑pivot现在在左边，因此我们要利用右边的right，通过对其的移动找到小于key的数，并将这个数“挖走”，并填入坑pivot中，此时，被挖走的位置就成了新的坑
//right不断向左移动，找到小于key的数 while (left < right && nums[right] >= key) right--; //将满足条件的数“挖走”，并填入坑pivot中 nums[pivot] = nums[right]; //被挖走数字的区域变成新的坑 pivot = right;
- 这样坑pivot就到了右边，右边放的应该是大于基准值key的数，因此我们就要通过移动left来找到小于key的数，将其挖走并填入坑pivot中，同样，被挖走的位置也成了新的坑
//left不断向右移动，找到大于key的数 while (begin < end && nums[begin] <= key) begin++; //将满足条件的数“挖走”，并填入坑pivot中 nums[pivot] = nums[begin]; //被挖走数字的区域变成新的坑 pivot = begin;
- 通过循环，不断移动left和right，直到不能满足条件
left < right，此时第一个数就被放到正确的位置了。
放置第一个数的具体过程
我们以数组{5,8,2,9,1,3,7,4,6}为例：
放置第一个数实现代码
void QuickSort(int* nums, int numsSize) { int key = nums[0]; //基准值 int pivot = 0; //坑的位置 int left = 0; //区间最左边 int right = numsSize - 1; //区间最右边 while (begin < end) { //right不断向左移动，找到小于key的数 while (left < right && nums[right] >= key) right--; //将满足条件的数“挖走”，并填入坑pivot中 nums[pivot] = nums[right]; //被挖走数字的区域变成新的坑 pivot = right; //left不断向右移动，找到大于key的数 while (begin < end && nums[begin] <= key) begin++; //将满足条件的数“挖走”，并填入坑pivot中 nums[pivot] = nums[begin]; //被挖走数字的区域变成新的坑 pivot = begin; } //将基准值填入最后坑的位置 nums[pivot] = key; }
处理所有数
- 我们能够将一个数放在正确的位置，那么自然其他的数我们也可以用类似的方法来处理
- 这里我们利用分治思想：分而治之。大问题分成类似的子问题，子问题再分成子问题……直到子问题不能再分割。
- 处理完第一个数后，整个待排序列已经被分割成了两个子序列：
[0,pivot - 1]和[pivot + 1, right]，我们可以利用同样的办法将个子区间继续分割，这样越来越多的元素到了正确的位置，直到每个区间的长度为1或0就可以表明待排序列以已经有序 - 我们用递归来解决：
实现代码
void QuickSort(int* nums, int begin, int end) { //如果区间长度为1或0，则表示只有一个数，直接退出 if (begin >= end) return; int key = nums[begin]; //基准值 int pivot = begin; //坑的位置 int left = begin; //区间最左边 int right = end; //区间最右边 while (left < right) { //right不断向左移动，找到小于key的数 while (left < right && nums[right] >= key) right--; //将满足条件的数“挖走”，并填入坑pivot中 nums[pivot] = nums[right]; //被挖走数字的区域变成新的坑 pivot = right; //left不断向右移动，找到大于key的数 while (left < right && nums[left] <= key) left++; //将满足条件的数“挖走”，并填入坑pivot中 nums[pivot] = nums[left]; //被挖走数字的区域变成新的坑 pivot = left; } //将基准值填入最后坑的位置 nums[pivot] = key; //递归处理子区间 QuickSort(nums, begin, pivot - 1); QuickSort(nums, pivot + 1, end); }
方法二：左右指针法
实现的基本思想
- 左右指针法其实和挖坑法的思想十分类似，同样是先确定一个基准值key，然后通过左边的left找大于key的数和右边的right找小于key的数，然后进行一定的操作，从而达到有序
- 不同点在于：左右指针法不会挖坑，而是在在右边的right找到小于key的数后，直接让左边的left找大于key的数，然后交换这两个值
//找到小于基准值的数 while (left < right && nums[right] >= key) right--; //找到大于基准值的数 while (left < right && nums[left] <= key) left++; //交换这两个数 Swap(&nums[right], &nums[left]);
- 同样的，不断循环，直到不能满足条件
left < right结束，最后再交换基准值和left、right相遇位置的数。
int key = nums[begin]; //基准值 int left = begin; int right = end; while (left < right) { //找到小于基准值的数 while (left < right && nums[right] >= key) right--; //找到大于基准值的数 while (left < right && nums[left] <= key) left++; //交换这两个数 Swap(&nums[right], &nums[left]); } //交换相遇值和基准值 Swap(&nums[begin], &nums[left]);
一趟循环的具体过程：
- 和挖坑法一样，知道处理一个数，我们就可以用递归的方法来对其余的数进行处理
整体实现代码
void QuickSort(int* nums, int begin, int end) { if (begin >= end) return; int key = nums[begin]; //基准值 int left = begin; int right = end; while (left < right) { //找到小于基准值的数 while (left < right && nums[right] >= key) right--; //找到大于基准值的数 while (left < right && nums[left] <= key) left++; //交换这两个数 Swap(&nums[right], &nums[left]); } //交换相遇值和基准值 Swap(&nums[begin], &nums[left]); QuickSort(nums, begin, left - 1); QuickSort(nums, left + 1, end); }
方法三：前后指针法
实现的基本思想
- 前后指针法和前面两种方法不同，这里要定义指针prev指向待排区域的起始位置，指针cur指向prev的后一个位置
int prev = begin; int cur = begin + 1;
- 令cur不断向右移动遍历待排区域，当碰到小于基准值key的数就停止，同时让prev也向右移动一个（即prev++），交换prev和cur位置的数据
- 不断循环，直到cur遍历完整个数组
while (cur <= end) { if (nums[cur] < key) { prev++; Swap(&nums[cur], &nums[prev]); } cur++; }
- 最后，再将基准值放到正确的位置，即将最后prev和begin位置的元素交换位置
Swap(&nums[begin], &nums[prev]);
- 可能有小伙伴会疑惑，为什么当
nums[cur] < key时，将prev++，再交换cur和prev位置的数据，就可以将小的数据放在前面，大的数据放在后面，我通过下面这张图来解释：
一趟循环具体过程
改进
- 如果待排数组是这样的：
- 那么会出现这样的情况：
- 因此我们可以对if判断多加一个条件：
++prev != cur，这样就可以避免对一个数字进行交换了
实现代码
void QuickSort(int* nums, int begin, int end) { if (begin >= end) return; int key = nums[begin]; int prev = begin; int cur = begin + 1; while (cur <= end) { if (nums[cur] < key && ++prev != cur) Swap(&nums[cur], &nums[prev]); cur++; } Swap(&nums[begin], &nums[prev]); //对余下数字进行递归整理 QuickSort(nums, begin, prev - 1); QuickSort(nums, prev + 1, end); }
方法四：非递归
- 我们知道，递归有一个致命的缺陷，即如果递归的深度太深，就可能会发生栈溢出，从而导致程序无法正常运行
- 因此我们有必要掌握快速排序的非递归算法
- 通过上面的递归讲解，我们知道，快速排序实际上就是不断重复将一个数放到正确位置这一过程，在这个过程中，待排序列会被分割成数个长度已知的子序列，因此可以用分治思想和递归来解决
- 而要利用非递归来解决快速排序，我们可以利用数据结构中的栈，来进行模拟递归。
实现的基本思路
- 由于C语言的局限性，我们要用到栈，当然就要先创造一个栈，并实现有关其的基本操作。这里不赘述，如有疑问，可以去看看栈的相关操作
- 在递归解法中，我们是对不断细分的子区间进行数据的整理，同样的，在非递归解法中，我们也需要利用这些不断细分的子区间来进行排序，而要能够像递归一样利用这些子区间，就需要用栈来对这些子区间的左右端的下标进行存储，为了方便讲解，我们先来看看具体的过程展示：
具体做法
- 假设我们要对长度为numsSize的数组进行排序
- 先将数组两端的下标入栈
/* 注意先后顺序 由于栈先入后出的特性 应该先入后面的，再入前面的 */ StackPush(st, numsSize - 1); StackPush(st, 0);
- 进入循环，循环进行的条件为栈不能为空
- 取出栈顶的两个元素，作为待排区间的左右端
- 我们可以用挖坑法、前后指针法、左右指针法这三种方法对这一段区间进行一趟排序（即得到一个数正确的位置），同时得到这个正确位置的下标
- 这样，这个正确位置就将待排序列分割为了两个子序列
- 如果左边的子序列长度大于一，那么就将这个子序列的左右端入栈，对右序列进行相同的处理
- 重复上述步骤，直到栈空
实现代码
//挖坑法的一趟排序（即将一个数放在正确位置） int PartSort(int* nums, int begin, int end) { int key = nums[begin]; //基准值 int pivot = begin; //坑的位置 int left = begin; //区间最左边 int right = end; //区间最右边 while (left < right) { //right不断向左移动，找到小于key的数 while (left < right && nums[right] >= key) right--; //将满足条件的数“挖走”，并填入坑pivot中 nums[pivot] = nums[right]; //被挖走数字的区域变成新的坑 pivot = right; //left不断向右移动，找到大于key的数 while (left < right && nums[left] <= key) left++; //将满足条件的数“挖走”，并填入坑pivot中 nums[pivot] = nums[left]; //被挖走数字的区域变成新的坑 pivot = left; } //将基准值填入最后坑的位置 nums[pivot] = key; //返回正确位置的下标 return pivot; } void QuickSort(int* nums, int numsSize) { ST* st = (ST*)malloc(sizeof(ST)); StackInit(st); //初始化栈 //先将待排序列的左右端点入栈 StackPush(st, numsSize - 1); StackPush(st, 0); //当栈不为空进行循环 while (!StackEmpty(st)) { //出栈，得到序列区间 int begin = StackFront(st); StackPop(st); int end = StackFront(st); StackPop(st); //进行一趟排序，得到一个数的正确位置 //这一位置将待排序列分割为两个子序列 int key_index = PartSort(nums, begin, end); //如果右边的子序列长度大于一，那么将左右端点入栈 if (end - key_index > 0) { StackPush(st, end); StackPush(st, key_index + 1); } //如果左边的子序列长度大于一，那么将左右端点入栈 if (key_index - begin > 0) { StackPush(st, key_index - 1); StackPush(st, begin); } } }
时间复杂度
由于四种方法的思想有共通之处，故拿挖坑法为例
- 我们先看其一趟排序：
//挖坑法的一趟排序（即将一个数放在正确位置） int PartSort(int* nums, int begin, int end) { int key = nums[begin]; //基准值 int pivot = begin; //坑的位置 int left = begin; //区间最左边 int right = end; //区间最右边 while (left < right) { //right不断向左移动，找到小于key的数 while (left < right && nums[right] >= key) right--; //将满足条件的数“挖走”，并填入坑pivot中 nums[pivot] = nums[right]; //被挖走数字的区域变成新的坑 pivot = right; //left不断向右移动，找到大于key的数 while (left < right && nums[left] <= key) left++; //将满足条件的数“挖走”，并填入坑pivot中 nums[pivot] = nums[left]; //被挖走数字的区域变成新的坑 pivot = left; } //将基准值填入最后坑的位置 nums[pivot] = key; //返回正确位置的下标 return pivot; }
- 实际上就是left，right两个指针分别从左右遍历一次待排区间，时间复杂度为O(N)
- 记下来，就是对这一过程进行不断递归，直到待排区间被分割为一个数，我们可以将这个分割过程看成是一棵满二叉树的情况：
- 因此，递归的时间复杂度就是O(log2N)
- 综上，快速排序的时间复杂度为O(NlogN)
优化
处理最坏情况（以挖坑法为例）
- 先下结论：对于快速排序，最坏情况就是当数组为有序时（无论是正序还是逆序）
- 为了处理类似的情况，我们就要对基准值的取值进行改变，我们一般采用三数取中的方法来进行对key的取值
- 三数取中：比较待排区间两端点和中间的数，选择不大不小的那一个，和左端点的值交换，再将左端点的值作为基准值key
三数取中实现代码
int GetMid(int* nums, int left, int right) { int mid = (right - left) / 2 + left; if (nums[left] <= nums[mid]) { if (nums[right] > nums[mid]) return mid; else if (nums[right] > nums[left]) return right; else return left; } else //nums[left] > nums[mid] { if (nums[right] > nums[left]) return left; else if (nums[right] > nums[mid]) return right; else return mid; } }
改善后的代码
void QuickSort(int* nums, int begin, int end) { if (begin >= end) return; /* 为了不改变后序代码的逻辑 三数取中后，应交换中间数和开头数 */ int index = GetMid(nums, begin, end); Swap(&nums[index], &nums[begin]); int key = nums[begin]; //基准值 int pivot = begin; //坑的位置 int left = begin; //区间最左边 int right = end; //区间最右边 while (left < right) { //right不断向左移动，找到小于key的数 while (left < right && nums[right] >= key) right--; //将满足条件的数“挖走”，并填入坑pivot中 nums[pivot] = nums[right]; //被挖走数字的区域变成新的坑 pivot = right; //left不断向右移动，找到大于key的数 while (left < right && nums[left] <= key) left++; //将满足条件的数“挖走”，并填入坑pivot中 nums[pivot] = nums[left]; //被挖走数字的区域变成新的坑 pivot = left; } //将基准值填入最后坑的位置 nums[pivot] = key; QuickSort(nums, begin, pivot - 1); QuickSort(nums, pivot + 1, end); }
