目录
Review：
具体问题：
操作核心：
注：
操作分解：
操作实现：
问题（1）：进行不一样次数的 if / else 判断
问题（2）：通过判断条件为“小于哨兵的元素”行不通
问题（3）：
当采用【大于等于】作为循环条件（while）循环时候程序的运行原理（框架）
一开始
后来我们发现
你以为到这里我们终于要结束了吗？
然而并没有
最大的问题：
一开始（前面），我们以为：
而在后来我们又发现，实际上并没有那么简单：
真正的问题：
将问题在程序流程中具体化：
（1）：
（2）：
具体化的完整过程：
（1）：
（2）：
没有确认找到下一个放入空格的元素再进行下一步（换指针操作）
而是只要对下一个元素进行过了比较、进行了交换元素或移动该位置指针的操作，就进行下一步
修改最终结果如下：
我们只有在确定找到了比哨兵大/小的元素、确定进行了对空格的插入操作以后我们才换指针操作
而前面的程序不管有没有找到、交不交换，都进行换指针的操作
其实我们要修改的结果就是要让程序确定执行了插入空格的操作再进行下一步（下一轮）
标准答案：
Review：
具体问题：
运行逻辑机制问题，我们就拿PPT上的实例来说事吧：
将逐次具体操作转化为表格展示如下：
| 第几步 | 操作 | Low指向 | High指向 |
| 第1步 | 49变哨兵 | 1 | 8 |
| 第2步 | 49'不动，high--（第一个 if / else 判断） | 1 | 7 |
| 第3步 | 49不动，low++（第二个 if / else 判断） | 2 | 7 |
这里到了第三步，明显就开始出问题了：
空格里面还没有元素呢，你这个算法就开始超过他、跳跃到下一格，干什么？
重复比较无伤大雅，但是low移动了，危险！！！（要出错了）
这里很明显，我们可以看到，问题出在：
在第一个处理的元素被放到哨兵里后，我们又去拿这个元素本身比较哨兵
也就是自己比较自己，错过了这个空格；
而不是用这个空格来装第一个小于哨兵的元素
操作核心：
所以我们需要操作的就是：
从程序开头开始，一直监视这个程序运行操作的每一步，确保：
我们【第一个元素让出来的空格】装入【第一个小于哨兵的元素】
注：
监视：
更准确的来说，这里我们这个所谓的“监视”，指的是是重新手写一遍
从程序开头开始，直到【第一个元素让出来的空格】装入【第一个小于哨兵的元素】
这段过程，整个过程的所有操作的程序，全部重新自己一步一步手写一遍
操作分解：
而我们要（在一开始）手写的：
从程序开头开始，直到【第一个元素让出来的空格】装入【第一个小于哨兵的元素】
的整个过程的操作，也无非就是：
从程序开头开始，（一直）比较high指针：（先比较最后一位）
- 若【high指针指向元素】小于哨兵，就把元素放前面空格里面
- 若不是小于（>=）：
- 这个元素继续放后面
- 【high指针】继续往前寻找，比较前面一个元素和哨兵的大小
操作实现：
问题（1）：进行不一样次数的 if / else 判断
而这里，如果我们写程序还是跟着/像上一节那样，每次都简单的只是采用 if / else 判断语句，那么
我们对于不同的顺序表：
无疑每一次 都要进行不一样次数的 if / else 判断
（谁知道后面第一个小于哨兵的元素的位置有多前面）
这（样）无疑是不行的
问题（2）：通过判断条件为“小于哨兵的元素”行不通
既然我们的目的是要找到从后往前数第一个小于哨兵的元素
直接找到这个“第一个小于哨兵的元素”本身
如果设置条件为：通过【判断条件为“小于哨兵的元素”】直接查找的话
除非最后一个元素就小于哨兵，要不然根本不可能直接找到
如果有大于等于哨兵的元素我们根本跨不过去
if (low < high && L.r[high].key >= L.r[0].key)
{
if (low < high && L.r[high].key >= L.r[0].key)
{
...//无数个：
//【if (low < high && L.r[high].key >= L.r[0].key){} else 把元素放前面空格里面】语句
//根本写不完，实现不了，死循环
}
else 把元素放前面空格里面
}
else 把元素放前面空格里面所以，我们只能设置把判断循环条件改为不是小于（>=）哨兵的情况
问题（3）：
当采用【大于等于】作为循环条件（while）循环时候程序的运行原理（框架）
一开始
我们在写算法的时候想当然的以为
用【大于等于】作为循环条件（while）循环的时候，策略是退而求其次
先确定找到【小于（哨兵元素）的前面一个元素】；
然后再通过小于哨兵的元素的前面一个元素通过（+1）的方式找到该元素进行操作
后来我们发现
不对，上面写这个执行流程是我们想当然的结果
实际上，把循环条件改为【大于等于】哨兵时，程序运行的逻辑是：
如果大于等于：一直high--；
直到我们找到第一个小于哨兵的元素
程序退出循环时，high已经指向了交换时我们所需要指向的元素
直接找到了这个“第一个小于哨兵的元素”本身
而不是上一个元素
于是做出修改：
int 遍历(SqList &L, int low, int high)
{
L.r[0] = L.r[low];
while (low < high && L.r[high].key >= L.r[0].key)
high--;
L.r[low] = L.r[high];
while (low < high)
{
if (L.r[high].key < L.r[0].key)
{
L.r[low] = L.r[high];
low++;
}
else
high--;
if (L.r[0].key < L.r[low].key)
{
L.r[high] = L.r[low];
high--;
}
else
low++;
}
L.r[low] = L.r[high] = L.r[0];
return low;
}
void QuickSort(SqList& L, int low, int high)
{
int pivot = 遍历(L, low, high);
QuickSort(L, low, pivot-1);
QuickSort(L, pivot + 1, high);
}
int main()
{
SqList L;
cin >> L.length;
cin >> L.r->key;
QuickSort(L, 1, L.length);
}你以为到这里我们终于要结束了吗？
然而并没有
最大的问题：
然后，我们又继续深挖下去，发现这个程序的问题并没有那么简单：
一开始（前面），我们以为：
程序只因为在开头，由于第一个元素存入哨兵而出现了：
元素本身比较哨兵，也就是自己比较自己，错过空格；
的现象而产生的错误，重要的是：
我们以为这里是一个特殊情况，整段程序只有开头出现了问题
而在后来我们又发现，实际上并没有那么简单：
程序存在的在开头已经出现的（无法正确排序）问题，在后面后续（的）程序中同样存在：
真正的问题：
如果前/后面的空格还没补上，我们就开始移动前/后面的指针
那么这个空格就永远都不会再被填上了，于是（从此），我们就再也不能回去找不到这个空格了
然后后面的程序全部乱套，出大问题
将问题在程序流程中具体化：
（程序）真正（出现）的问题在于：
在还没有确定有：
（1）：
high指针指向的元素】已经移动（填充）到前面的空格中
我们就开始移动low指针，指向空格的后面一个元素
或者
（2）：
【low指针指向的元素】已经移动（填充）到后面的空格中
我们就开始移动high指针，指向空格的前面一个元素
具体化的完整过程：
（1）：
在还没有确定有：
high指针指向的元素】已经移动（填充）到前面的空格中
我们就开始移动low指针，指向空格的后面一个元素
当开始（新一轮）开头比较时（从第二个if/else语句开始）
如果我们碰到的情况是：high指针指向的元素并不比哨兵小
(L.r[high].key < L.r[0].key)不成立，所以执行else语句：high--；
执行第二个if/else语句：
到这里一切都还没什么问题，然后下一步就出问题了：
根据我们手动操作的流程，程序下一步本来应该继续执行“high--；”
但是在Project 1中，根据 Project 1的程序的操作流程，下一步的操作就是：
-
若low指向的首个元素大于哨兵：L.r[high] = L.r[low]；high--;
直接把high指针元素放进空格，此种情况除非倒数第二个元素恰好小于哨兵，否则也是错误的插入
-
若low指向的首个元素小于等于哨兵，low++；
直接移动low指针，再也找不到空格
（2）：
在还没有确定有：
【low指针指向的元素】已经移动（填充）到后面的空格中
我们就开始移动high指针，指向空格的前面一个元素
当开始（新一轮）开头比较时（从第二个if/else语句开始）
如果我们碰到的情况是：low指针指向的元素并不比哨兵大
(L.r[0].key < L.r[low].key)不成立，所以执行else语句：low++；
重新执行第一个if/else语句
若high指向的首个元素小于哨兵：L.r[low] = L.r[high];low++;
直接把low指针元素放进空格，此种情况除非第二个元素恰好大于哨兵，否则也是错误的插入
若high指向的首个元素大于等于哨兵， high--;
直接移动high指针，再也找不到空格
说到底，程序这个问题的核心，就是程序执行的操作：
没有确认找到下一个放入空格的元素再进行下一步（换指针操作）
而是只要对下一个元素进行过了比较、进行了交换元素或移动该位置指针的操作，就进行下一步
修改最终结果如下：
#include<iostream>
using namespace std;
#define MAXSIZE 20 //记录最大个数
typedef int KeyType; //关键字类型
typedef int InfoType;
//定义每个记录（数据元素）的结构
struct RecType
//Record Type：每条记录的类型
{
KeyType key; //关键字
InfoType otherinfo; //其他数据项
};
struct SqList
//顺序表(的)结构
{
RecType r[MAXSIZE + 1];
//类型为【记录类型】的数组
//r[0]一般做哨兵或缓冲区
int length; //顺序表长度
};
int 遍历(SqList& L, int low, int high)
{
L.r[0] = L.r[low];
while (low < high)
{
//从后往前遍历，指向小于等于哨兵的元素：退出循环、插入空格
while (low < high && L.r[high].key > L.r[0].key)
high--;
L.r[low] = L.r[high];
//继续，从前往后遍历，指向大于等于哨兵的元素：退出循环、插入空格
while (low < high && L.r[0].key < L.r[low].key)
low++;
L.r[high] = L.r[low];
}
L.r[low] = L.r[high] = L.r[0];
return low;
}
void QuickSort(SqList& L, int low, int high)
{
int pivot = 遍历(L, low, high);
QuickSort(L, low, pivot - 1);
QuickSort(L, pivot + 1, high);
}
int main()
{
SqList L;
cin >> L.length;
cin >> L.r->key;
QuickSort(L, 1, L.length);
}与前面我们写的程序不同的是：
我们只有在确定找到了比哨兵大/小的元素、确定进行了对空格的插入操作以后我们才换指针操作
而前面的程序不管有没有找到、交不交换，都进行换指针的操作
其实我们要修改的结果就是要让程序确定执行了插入空格的操作再进行下一步（下一轮）
当然，这样修改以后和标准答案还是有区别的，但不多：
标准答案：
int Partition(SqList& L, int low, int high)
{
L.r[0] = L.r[low];
KeyType pivotkey = L.r[low].key;
while (low < high)
{
while (low < high && L.r[high].key >= pivotkey)
high--;
L.r[low] = L.r[high];
while (low < high && L.r[low].key < pivotkey)
low++;
L.r[high] = L.r[low];
}
L.r[low] = L.r[0];
return low;
}
void QuickSort(SqList& L, int low, int high) {
if (low < high)
{
int pivotloc = Partition(L, low, high); //将L一份为二
QuickSort(L, low, pivotloc - 1); //对低子表递归排序
QuickSort(L, pivotloc + 1, high); //对高子表递归排序
}
}
int main()
{
}唯一的区别就是标准答案为了这个比较的节点还特地设立了一个变量 pivotkey
我感觉其实无所吊味，没什么卵用啦，还不如老子写的这个简单方便
就这样吧，Cnmd，写这篇文章搞这个快排折腾了老子至少一礼拜至少5天的时间，我是真NM无语
以上
