python的两种随机数选取key值的快速排序算法的实现

零：环境

python 3.6.5

JetBrains PyCharm 2018.1.4 x64

一：基于百度百科的思路

源地址：https://baike.baidu.com/item/快速排序算法/369842?fromtitle=快速排序&fromid=2084344&fr=aladdin

原文:

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它左边，所有比它大的数都放到它右边，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

一趟快速排序的算法是：

1）设置两个变量i、j，排序开始的时候：i=0，j=N-1；

2）以第一个数组元素作为关键数据，赋值给key，即key=A[0]；

3）从j开始向前搜索，即由后开始向前搜索(j--)，找到第一个小于key的值A[j]，将A[j]和A[i]的值交换；

4）从i开始向后搜索，即由前开始向后搜索(i++)，找到第一个大于key的A[i]，将A[i]和A[j]的值交换；

5）重复第3、4步，直到i=j； (3,4步中，没找到符合条件的值，即3中A[j]不小于key,4中A[i]不大于key的时候改变j、i的值，使得j=j-1，i=i+1，直至找到为止。找到符合条件的值，进行交换的时候i， j指针位置不变。另外，i==j这一过程一定正好是i+或j-完成的时候，此时令循环结束）。

　　分析:

　　　　这种快速排序的方法可以理解成通过一轮交换将key值交换到某个正确位置上，该位置的左侧的全部元素都不高于key，右侧元素都不低于key

　　　　百度百科选取的左侧的第一个元素作为key值，然后首先从右侧开始找，使得在右侧的合适的值找到之后，发生交换时，key值肯定会随之被来回交换，可以理解成每次寻找都是在找key值对面一侧的适合元素，key值被动的变化位置，到最后被交换到key所应该在的合适的位置

　　　　而random选取随机值的话因为key位置的不确定性，所以为了在遇到key值时，为了能将key值也像百度百科那样随之来回交换到正确位置，在寻找合适元素时的判断条件不应该添加等号，以下是例子。

[76, 2, 32, 4, 56, 65, 45, 78, 32, 96, 32, 32, 42, 1, 78, 4, 126]

v_数组 = [126, 2, 32, 4, 56, 65, 45, 78, 32, 96, 32, 32, 42, 1, 78, 4, 76]

　　　首先一开始假设我们随机到第五个元素为key值，即56为key值，左边界为0，右边界为len(v_数组)-1，即16

　　　　1：第一轮交换

　　　　假设我们先从左侧开始找

　　　　根据上面的快速排序原则，我们从左边找的时候先找第一个比key值大的数，但是为了让我们能够匹配到key值，我们要先找第一个大于等于key值的数

　　　　根据描述可以看到第一个元素就是

　　　　所以我们开始进入到元素交换环节

v_数组[v_左边界],v_数组[v_右边界] = v_数组[v_右边界],v_数组[v_左边界]

　　　　此时的数组情况应该为v_左边界:0　　v_右边界:16

[76, 2, 32, 4, 56, 65, 45, 78, 32, 96, 32, 32, 42, 1, 78, 4, 126]

　　　　2：第二轮交换

　　　　左侧找完了我们该从右侧开始找

　　　　同上面的原理，找到第一个小于等于key的数

　　　　因为126大于key值56，所以v_右边界-=1

　　　　此时5<key，所以v_右边界不变，为15，开始交换

　　　　此时的数组情况应该为v_左边界:0　　v_右边界:15

[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         pass
29     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_插入位置+=1
18             #   跳过key位置
19             if v_插入位置 == p_key位置:
20                 v_插入位置+=1
21     #   将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要-1
29         v_插入位置-=1
30     if v_插入位置-1>p_左边界:
31         f_随机数版本(p_列表,p_左边界,v_插入位置-1,random.randint(p_左边界,v_插入位置-1))
32     if v_插入位置+1<p_右边界:
33         f_随机数版本(p_列表,v_插入位置+1,p_右边界,random.randint(v_插入位置+1,p_右边界))
34 
35     pass

　　　　以上皆为自己的思考

　　　　转载请注明出处