Python的快速排序 逐步深入

因为有一个先入为主的概念：快速排序最牛。因此刚开始一听见快速 排序就不敢写，认为其绝对很复杂。

事实证明这种想法不能有！

简单粗暴地使用递归手写快速排序：

（为了面试时候能不怯场的直接手撕）

            
              # 简单粗暴的快速排序
# 存在额外的开销存放左右
# 要多次遍历数组
def quicksort(array):  # 直接递归
    if len(array)<2:   # 递归出口
        return array
    pivot_index = 0
    pivot = array[pivot_index]
    left_arr = [i for i in array[pivot_index+1:] if i<=pivot]
    right_arr = [i for i in array[pivot_index+1:] if i>pivot]
    return quicksort(left_arr) + [pivot] + quicksort(right_arr)

# 测试
import random
# seq = list(range(10))
# random.shuffle(seq)
seq = [random.randint(1,100) for i in range(10)]
print(seq)
quicksort(seq)
    
            
          

输出： 

            
              [4, 77, 14, 14, 33, 69, 63, 67, 87, 9]
[4, 9, 14, 14, 33, 63, 67, 69, 77, 87]

            
          

改进：

上述算法存在很多问题，已经写在注释里。因此考虑不创建额外数组的改进：

思路概述：

1. 以第一个元素作为pivot，left指针指向第二个元素，right指针指向最后一个元素。
2. 如果left指向的元素小于pivot，则left指针+1（即后移一个元素），接着判断，如果该元素大于pivot，left指针停止移动。
3. 如果right指向的元素大于pivot，则right指针-1（即前移一个元素），接着判断，如果该元素小于pivot，right指针停止移动。
4. 判断left是否大于right，是就跳出
5. 交换left和right所指向的元素。
6. 返回步骤2.
7. 跳出后，交换right所指和pivot所在位置的值。

            
              # 改进，不产生多余的开销
# 在原数组上用左右指针
def partition(array,beg,end): # pivot左边的都比pivot小，右边的都比pivot大
    pivot_index = beg
    pivot = array[pivot_index]
    left = pivot_index+1
    right = end
    
    while True:
        while left<=right and array[left]<=pivot:
            left += 1
        while left<=right and array[right]>pivot:
            right -=1
        if left>right:
            break
        else:
            array[left],array[right] = array[right],array[left]
    array[right],array[pivot_index] = array[pivot_index],array[right]
    return right              # 返回pivot的下标
    
def quicksort_pro(array,beg,end):   # 改进后的快速排序
    if beg < end :
        pivot = partition(array,beg,end)
        quicksort_pro(array,beg,pivot)
        quicksort_pro(array,pivot+1,end)
        
# 测试
import random
# seq = list(range(10))
# random.shuffle(seq)
seq = [random.randint(1,100) for i in range(6)]
print(seq)
quicksort_pro(seq,0,len(seq)-1)
print(seq)
    
            
          

以上。

参考：

https://www.bilibili.com/video/av26524049

https://www.bilibili.com/video/av26524633/?spm_id_from=trigger_reload