python对数组的快排 加注释

数组的快排 加注释"/>

python对数组的快排 加注释

原理参考此图解法：

图解数组的快速排序【附源代码】_实现对一个数组的快速排序-CSDN博客

python代码：

法一：原地改数组

# 利用快速排序实现数组的快排 降序 升序同理def fastSort(arr,Left,Right):# 递归函数实现数组的快排# 终止条件if Right < Left:return# 需要记录当前的left和right 因为这样在下层递归中知道左区间左侧 和右区间右侧i = Leftj = Right# 单层递归逻辑 快排 → 找到一个基准 让数组左边大于基准 数组右边小于基准tmp = arr[0]    #一般以数组的第一个元素作为基准# 只要左指针位置 小于 右指针位置时 都分别左右指针移动 直至重合 说明单次快排结束while i < j:# 移动右指针 直至找到比tmp大的元素 赋给右指针(因为当前右指针位置所对应值是tmp或比tmp大的(在递归中) 要替换掉)while i < j and arr[j] <= tmp:j -= 1arr[i] = arr[j]# 移动左指针 直至找到比tmp小的元素 赋给右指针(因为当前右指针位置所对应值是比tmp大的 要替换掉)while i < j and arr[i] >= tmp:i += 1arr[j] = arr[i]# 跳出了循环说明i == jarr[i] = tmp# 此时arr[i] 的左边都比tmp大 右边都比tmp小 但顺序还是不知道的，因此用递归fastSort(arr,Left, i-1)  # 这里隐藏了个回溯过程 i还是没变fastSort(arr,i+1,Right)arr = [2,3,5,6,4,1]
fastSort(arr,0,len(arr)-1)
print(arr)#结果 [6, 5, 4, 3, 2, 1]

法二：开辟新的空间

def fastSort(arr):# 终止条件if len(arr) == 1:return arr# 单层递归逻辑small, cur, big = [], [], []# 以数组中第一个元素为基准base = arr[0]for num in arr:if num > base:big.append(num)elif num < base:small.append(num)else:cur.append(num)small = fastSort(small)big = fastSort(big)return small + cur + bigarr = [2,5,6,1,2,3]
print(fastSort(arr))# 结果 [1, 2, 2, 3, 5, 6]