def partition(array, p, r):
x = array[r]
j = i = p - 1
for k in range(p, r):
if array[k] < x:
i += 1
j += 1
# Crucial: Assignment order must be rotative.
array[k], array[j], array[i] = array[j], array[i], array[k]
elif array[k] == x:
j += 1
array[j], array[k] = array[k], array[j]
i += 1
j += 1
array[j], array[r] = array[r], array[j]
return i, j
def quickSort(array, p, r):
if p < r:
i, j = partition(array, p, r)
print('i j =', i, j)
quickSort(array, p, i-1)
quickSort(array, j+1, r)
Quick sort with equivalent elements. Θ(nlgn)
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 快速排序和冒泡排序类似，都是基于交换的思想，快速排序对冒泡排序进行了优化，从而更加快速高效（从名字就可以看出应该很...
- 前言 原文：[ javascript: 快速排序（Quick Sort） #146 ] 基本思想 1 在数据集之中...
