代码:
# -*- coding: utf-8 -*-
"""通过数组交换的快速排序"""
import random
def quicksort(arr, left, right):
# 只有left < right 排序
if left < right:
pivot_index = partition(arr, left, right)
quicksort(arr, left, pivot_index - 1)
quicksort(arr, pivot_index + 1, right)
def partition(arr, left, right):
"""找到基准位置, 并返回"""
pivot_index = left
pivot = arr[left]
for i in range(left + 1, right + 1):
if arr[i] < pivot:
# 如果此处索引的值小于基准值, 基准值的位置后移一位
# 并将后移一位的值和这个值交换, 让基准位置及之前的始终小于基准值
pivot_index += 1
if pivot_index != i:
arr[pivot_index], arr[i] = arr[i], arr[pivot_index]
# 将基准值移动到正确的位置
arr[left], arr[pivot_index] = arr[pivot_index], arr[left]
return pivot_index
if __name__ == '__main__':
arr = []
for i in range(10):
arr.append(random.randint(1, 100))
print arr
quicksort(arr, 0, len(arr)-1)
print arr
