- 深入理解算法中‘分割’的概念。
- 在序列变换中巧妙使用‘空位’， 使代码变得美观
- 推荐每个程序员可以在十分钟内写完如下代码
- 面试前，先写个快排
- 在入门一个新的程序语言时，不妨先写个快排练练
# Quick Sort
# 选取一个Key
# 对比： 将比Key小的放到左边，比Key大的放到右边
# 循环： 直至每个元素都与key对比过了
# 递归： key左侧的和key右侧的分别递归
list = [5,7,1,8,4]
count = len(list)
def quickSort(L, low, high):
print('\nquickSort: ', L, low, high)
i = low
j = high
if i >= j:
return L
# 为了序列调位方便 在序列中挖出一个空位
# 此时空位 序列中i的位置
key = L[i]
while i < j:
while i < j and L[j] >= key: # 遍历key右侧的值
j = j-1 # 若不小于key，j向左挪一个
# 此时序列中的空位为L[i]，赋值后变为L[j]
L[i] = L[j] #此时j指向的值小于key, 将其赋给i指向的位置（i值在key 值的左侧）
while i < j and L[i] <= key: #遍历key左侧的值
i = i+1 # 若不大于key, i 向右挪一个
# 此时序列中的空位为L[j], 赋值后变为L[i]
L[j] = L[i] #此时i 指向的值大于key，将其值赋给（空位）
print(L, i, j)
# 每循环一次调整序列中的两个值
# key右侧的一个值和key左侧的一个值
# 不断循环直到i = j，即key左侧的均小于key，右侧的均大于key
# 此时i = j ， 将key值放入空位中
L[i] = key
quickSort(L, low, i-1)
quickSort(L, j+1, high)
return L
quickSort(list,0,count-1)
无注释版
def quick_sort(lists, left, right):
# 快速排序
if left >= right:
return lists
key = lists[left]
low = left
high = right
while left < right:
while left < right and lists[right] >= key:
right -= 1
lists[left] = lists[right]
while left < right and lists[left] <= key:
left += 1
lists[right] = lists[left]
lists[right] = key
quick_sort(lists, low, left - 1)
quick_sort(lists, left + 1, high)
return lists
一行版---- 利用序列切片
import numpy as np
# 生成随机序列
randomList = np.random.randint(500,size=100)
print(randomList)
def qsort(numbers):
if len(numbers) == 0: return []
else: return qsort([i for i in numbers[1:] if i <= numbers[0]]) + [numbers[0]] + qsort([i for i in numbers[1:] if i > numbers[0]])
qsort(randomList)
