python实现快速排序 -- 详细思路分析

1. 快速排序思想

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列的目的。

2. 快速排序实现步骤

假设有一个列表[5,7,3,3,6,2,1,4,10]，需要使用快速排序，将其排序为有序列表。

2.1 第一次排序

---

• 首先，将列表的首个元素作为中间值，使用mid_value接收。【mid_value =5】
• 创建两个游标，low游标放置于0号索引位置【开头】，high游标放置于n-1索引位置【末尾】

step1

---

• 先移动high游标，当high游标所指元素比mid_value大时，high游标左移【移到4】
• 当high游标所指元素比mid_value小时，游标停留在当前位置【移动到4时，4比mid_value小，则high游标停留在当前位置】
• 将high游标当前位置的元素的值赋给low游标所指的位置【5 --> 4】

step2

---

• low游标往右走，当low游标所指的元素比mid_value小时，low游标右移【移到7】
• 当low游标所指的元素比mid_value大时，游标停留在当前位置【移动到7时，7比mid_value大，则low游标停留在当前位置
• 将low游标当前位置的元素赋值给high游标所指的位置【4 --> 7】

step3

---

• high游标当前位置的元素变为7后，当前值比mid_value大，所以high游标可以继续往左走，1的值比mid_value小，则high游标停留在当前位置

• 将high游标当前位置的元素赋值给low游标所指的位置，即7 --> 1

  
  step4

---

• low游标当前位置的元素变为1后，当前值比mid_value小，所以low游标可以继续往右走。不断和右边的元素比较，如果比mid_value小，则继续右移，直到去到6元素所在的位置，6比mid_value大，所以low游标停留在当前位置
• 将low游标所处位置的元素的值赋值给high游标所指位置，即1 --> 6

step5

---

• high游标继续往左走，2比mid_value小，所以high停留在当前位置
• 将high游标所指位置元素的值赋值给low游标所指位置，即6 --> 2

step6

---

• low游标往右走，此时low和high游标重合
• 当low和high相等时，将mid_value赋值给此时位置的元素

step7

以上便是第一次排序的过程图
通过以上过程，可以实现以下代码

def quick_sort(target_list):
    n = len(target_list)
    # 将alist的第一个元素作为中间值
    mid_value = target_list[0]
    low = 0
    high = n-1
    
    # 当low小于high时，两个游标都可以移动
    while low < high:
        # high游标所对应元素比mid_value大时，high游标往左走
        while low < high and target_list[high] > mid_value:
            
            high -= 1
        # 当条件不满足时说明遇到的元素比mid_value小
        # 此时将high游标所处位置的元素放到low游标所处的位置
        target_list[low] = target_list[high]

        while low < high and target_list[low] < mid_value:
            # low游标往右走
            low += 1
        target_list[high] = target_list[low]
        
    # 从循环退出时，low游标和high游标位置重合,把mid_value放到此位置
    target_list[low] = mid_value

---

2.2 第n次排序

根据快速排序的思想，我们排序好中间值后，会对中间值左边的列表和右边的列表再次使用快速排序，核心部分的代码基本不变，因此我们可以使用递归的方法来完成多次排序。

8.png

• 由于我们需要在同一个list上操作，因此不能使用列表切片的方式传入进行递归，我们需要传入first和last参数，用于表示截取同一个列表。first代表起使位置索引，last代表末尾位置索引
• 递归时，左边的列表就可以表示为quick_sort(alist,first,low-1);右边的列表可以表示为quick_sort(alist,low+1,last)
• 当列表只有一个元素或没有元素的时候，就终止递归，即first >= last时，结束递归
• 代码实现

def quick_sort(target_list,first,last):
    # 当first大于等于last时，则终止递归
    if first >= last:
        return
    # 将alist的第一个元素作为中间值
    mid_value = target_list[first]
    # 设置low和high两个游标
    low = first
    high = last
    while low < high:
        # high 左移,可以把相等的情况放到high或者low任意一边处理
        while low < high and target_list[high] >= mid_value:
            high -= 1
        target_list[low] = target_list[high]
        
        # low右移
        while low < high and target_list[low] < mid_value:
            low += 1
        target_list[high] = target_list[low]
    
    # 从循环退出时，low = high
    target_list[low] = mid_value
    
    # 把mid_value左右分为两部分进行递归操作
    # 对mid_value左边的元素进行递归操作
    quick_sort(target_list,first,low-1)
    # 对mid_value右边的元素进行递归操作
    quick_sort(target_list,low+1,last)
    
    return target_list