[4, 2, 32, 4, 56, 65, 45, 78, 32, 96, 32, 32, 42, 1, 78, 76, 126] 3：第三轮交换
这时⼜开始从左侧开始找
我们左侧的v_左边界在+1过程中遇到了key值56，为了抓住这个变量我们要就这样停⽌下来，开始交换 此时的数组情况应该为v_左边界:4 v_右边界:15
[4, 2, 32, 4, 76, 65, 45, 78, 32, 96, 32, 32, 42, 1, 78, 56, 126]
……以此类推
结束条件应当是v_左边界<=v_old右边界（v_old右边界为⼀开始的右边界，因为左右边界⼀直在变化所以先提取存起来） 结束的时候v_左边界就是key值所在位置
但是，假如左侧和右侧都找到了和key⼀样的key值的话就陷⼊了死循环
所以为了避免死循环应该在循环判断时添加⼀个条件，如果左右的值相等且都为key的话，那么从左侧找时那就继续+1，从右侧找时那就继续-1
其实交换是可以节省的，可以左右都找到或到临界点时才交换， 以下就是节省了⼀次交换的参考代码:
1 def f_第四题_左右交换_随机key(v_数组,t_左边界,t_右边界,t_key位置):
2 t_old左边界, t_old右边界, t_oldKey = t_左边界, t_右边界, v_数组[t_key位置] 3 while t_左边界 < t_右边界:
4 # ⽤⼩于号或⼤于号⽽不加上等于号是为了把key值能够交换到中间位置⽽省去了移除插⼊操作 5 # 判断左右相等是为了防⽌左右都遇到了和key⼀样的值⽽死循环
6 while (v_数组[t_左边界] < t_oldKey or v_数组[t_左边界] == v_数组[t_右边界] == t_oldKey) and t_左边界 < t_右边界 : 7 t_左边界 += 1
8 while (v_数组[t_右边界] > t_oldKey or v_数组[t_左边界] == v_数组[t_右边界] == t_oldKey) and t_左边界 < t_右边界: 9 t_右边界 -= 1
10 if t_左边界 < t_右边界:
11 v_数组[t_左边界], v_数组[t_右边界] = v_数组[t_右边界], v_数组[t_左边界]12 pass
13 if t_old左边界 < t_左边界 - 1:
14 f_第四题_左右交换_随机key(g_数组,t_old左边界, t_左边界 - 1, random.randint(t_old左边界, t_左边界 - 1))15 if t_左边界 + 1 < t_old右边界:
16 f_第四题_左右交换_随机key(g_数组,t_左边界 + 1, t_old右边界, random.randint(t_左边界 + 1, t_old右边界))17 pass
其实⾮递归写法也⽐较简单
可以定义⼀个伪栈v_上下界栈，在栈⾥添加左右边界和key位置，然后在函数退出时再Pop最后⼀个元素 以下是参考代码:
1 def f_第四题_左右交换_随机key(v_数组,t_左边界,t_右边界,t_key位置): 2 \"\"\"
3 百度的快排的⽆递归算法实现 4 :param v_数组: 数组参数
5 :param t_左边界: 想要排序的数组的左边界 6 :param t_右边界: 想要排序的数组的右边界 7 :param t_key位置: key的位置
8 :return: ⽆返回值暂时，可以修改…… 9 \"\"\"
10 v_上下界栈 = [[t_左边界, t_右边界, v_数组[random.randint(t_左边界,t_右边界)]]]11
12 while v_上下界栈:
13 t_左边界,t_右边界,t_oldKey = v_上下界栈[-1][0],v_上下界栈[-1][1],v_上下界栈[-1][2]14 while t_左边界 < t_右边界:
15 while (v_数组[t_左边界] < t_oldKey or v_数组[t_左边界] == v_数组[t_右边界] == t_oldKey) and t_左边界 < t_右边界:16 t_左边界 += 1
17 while (v_数组[t_右边界] > t_oldKey or v_数组[t_左边界] == v_数组[t_右边界] == t_oldKey) and t_左边界 < t_右边界:18 t_右边界 -= 1
19 if t_左边界 < t_右边界:
20 v_数组[t_左边界], v_数组[t_右边界] = v_数组[t_右边界], v_数组[t_左边界]21 pass
22
23 if v_上下界栈[-1][0] < t_左边界 - 1:
24 v_上下界栈.insert(-2, [v_上下界栈[-1][0], t_左边界 - 1, v_数组[random.randint(v_上下界栈[-1][0], t_左边界 - 1)]])25 if t_左边界 + 1 < v_上下界栈[-1][1]:
26 v_上下界栈.insert(-2, [t_左边界 + 1, v_上下界栈[-1][1], v_数组[random.randint(t_左边界 + 1, v_上下界栈[-1][1])]])27 v_上下界栈.pop(-1)28 pass29 pass
⼆：⽼师所讲的思路
⽼师的思路是都从⼀侧开始寻找
1：先找第⼀个⽐key⼤的数，我们⽤v_下标来遍历，找到之后那个位置我们就认为他是key值可能会插⼊的位置，并将v_下标赋值给v_插⼊位置。
从左往右找的效果会造成v_插⼊位置处的值的左侧必定都不⼤于key，但是右侧并不保证
2：在找到可能的插⼊位置之后再从v_插⼊位置处开始定义v_下标，v_下标负责寻找第⼀个⽐key⼩的值，然后找到之后将v_插⼊位置处的值与v_下标处的值交换，此时v_插⼊位置处的值是⽐key⼩的，所以v_插⼊位置要+=1 3：此时v_下标继续往后查找直到结尾 以下是例⼦
我们还以那个数组为例
v_数组 = [126, 2, 32, 4, 56, 65, 45, 78, 32, 96, 32, 32, 42, 1, 78, 4, 76]
我们还是假设56是key值 1:第⼀步
从左侧的第⼀个元素开始寻找第⼀个⽐key⼤的数，我们可以看到第⼀个元素就是 所以定义v_插⼊位置 = 0 2:第⼆步
定义v_下标 = v_插⼊位置
开始寻找第⼀个⽐key⼤的数，此时v_下标为1 所以我们要开始交换了 结果如下
[2, 126, 32, 4, 56, 65, 45, 78, 32, 96, 32, 32, 42, 1, 78, 4, 76]
3:第三步
v_插⼊位置处的值变成了⼩于key的值，所以v_插⼊位置需要加⼀
但是有⼀种特殊情况，当加⼀后遇到了key值之后我们要跳过这个key，所以还要继续+1 4:重复第⼆三步
因为我们忽略了key，所以key的位置必定不变，交换到最后v_插⼊位置的左侧必定都⼩于等于key,右侧都⼤于等于key，但是key还在原位，我们需要最后将key插⼊到v_插⼊位置然后再删除原来位置的key 以下是参考代码，关于特殊情况会在代码⾥注释
1 def f_随机数版本(p_列表,p_左边界,p_右边界,p_key位置): 2 v_插⼊位置,v_下标 = p_左边界,p_左边界 3 v_key = p_列表[p_key位置] 4 # 跳过key位置
5 # 因为我们这⾥最后是先insert再pop，所以插⼊到p_右边界+1即为插⼊到最后，不会出错 6 while v_下标<=p_右边界 and (p_列表[v_下标] < v_key or v_下标==p_key位置): 7 v_下标+=1
8 # 插⼊位置更新为下标位置
9 v_插⼊位置 = v_下标
10 # 带等于号是为了能够判断到最后⼀个元素11 while v_下标<=p_右边界:
12 while v_下标 <= p_右边界 and (p_列表[v_下标] >= v_key or v_下标==p_key位置):13 v_下标+=1
14 # 当v_下标有意义时，才交换15 if v_下标<=p_右边界:
16 p_列表[v_下标],p_列表[v_插⼊位置] = p_列表[v_插⼊位置],p_列表[v_下标]17 v_插⼊位置+=118 # 跳过key位置
19 if v_插⼊位置 == p_key位置:20 v_插⼊位置+=121 # 将Key值插⼊到指定位置
22 p_列表.insert(v_插⼊位置,v_key)
23 # 如果插⼊位置在key之前，则key位置就会往后推迟⼀位，所以需要pop +1 24 if v_插⼊位置 < p_key位置:25 p_列表.pop(p_key位置 + 1)26 else:
27 p_列表.pop(p_key位置)
28 # 插⼊位置在key之后的话，因为pop了key，所以插⼊位置处前⾯的元素会少，插⼊位置会指向下⼀个元素，所以为了正确指向key要-129 v_插⼊位置-=1
30 if v_插⼊位置-1>p_左边界:
31 f_随机数版本(p_列表,p_左边界,v_插⼊位置-1,random.randint(p_左边界,v_插⼊位置-1))32 if v_插⼊位置+133 f_随机数版本(p_列表,v_插⼊位置+1,p_右边界,random.randint(v_插⼊位置+1,p_右边界))3435 pass
以上皆为⾃⼰的思考 转载请注明出处
