快速排序基本原理

1.快速排序

1.1 基本原理

• 快速排序依赖于一个名为分区的概念
• 分区：从数组随机选取一个值，以此值轴，将比它小的值放到它左边，比它大的值放到它右边

1.2 快速排序执行步骤

1.2.1 分区包含步骤

• 比较：每个值都要与轴做比较。
• 交换：在适当时候将左右指针所指的两个值交换位置。

1.2.1 分区步骤

• 第一次分区步骤

  1. 左指针逐个格子向右移动，当遇到大于或等于轴的值时，停止移动。
  2. 右指针逐个格子向左移动，当遇到小于或等于轴的值时，停止移动。
  3. 将两指针所指的值交换位置。
  4. 重复步骤，直至两指针重合或左指针移到右指针的右边。
  5. 将轴与左指针所指的值交换位置【左指针>轴时交换】。

• 子数组分区
  6. 对其轴左右两侧的元素进行排序。
  7. 对轴左右的两个子数组递归重复第 1、2 步，两个子数组各自分区，并形成各自的轴以及由轴分隔的更小的子数组。然后对这些子数组分区。
  8. 当分出的子数组长度为 0 或 1 时，排序结束。

• 每次分区完成时，在轴左侧的那些值肯定比轴要小，在轴右侧的那些值肯定比轴要大

• 轴数据的值放在了正确的位置。

1.3 快速排序大O记法表示

• 快速排序大O记法表示: O($N$)

2. 将[0,5,2,1,6,3]进行快速排序 【实战】

2.1 第一次分区步骤

2.2 第二次分区步骤

2.3 第三次分区步骤

2.4 第四次分区步骤

3.快速排序代码实现

# 方式一【有排序步骤输出】，根据最大索引排序
alist = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
def sort(alist, left, right, flag=True):if not flag:print('-' * 30 + '\tstart list\t' + '-' * 30)print(f"当前列表为：{alist},left:{left},right:{right}")axis_index = rightaxis = alist[axis_index]  # 轴值left_pointer = left  # 左指针right_pointer = right - 1  # 右指针if left_pointer > right_pointer:  # 判断左指针是否在右指针的右边，如果是:停止移动returnwhile True:while alist[left_pointer] < axis:left_pointer = left_pointer + 1while alist[right_pointer] > axis:  # 右指针向左移动right_pointer = right_pointer - 1if left_pointer < right_pointer:  # 指针未重合alist[left_pointer], alist[right_pointer] = alist[right_pointer], alist[left_pointer]print(f'左指针索引为:{left_pointer},右指针索引为:{right_pointer};左右指针交换后数组作为:{alist}')elif alist[left_pointer] > alist[axis_index]:alist[left_pointer], alist[axis_index] = alist[axis_index], alist[left_pointer]  # 轴值交换print(f'左指针索引为:{left_pointer},轴索引为:{axis_index};左指针与轴交换后数组作为:{alist}')breakelif left_pointer > right_pointer:print(f"左指针索引为:{left_pointer},右指针索引为:{right_pointer};左指针在右指针的右边，指针移动结束")breakprint(f'分区结束,数组为:{alist}')if left_pointer - left not in [0, 1]:print('-' * 30 + '\tleft list\t' + '-' * 30)sort(alist, left, left_pointer - 1)  # 排序左子数组if right - left_pointer not in [0, 1]:print('-' * 30 + '\tright list\t' + '-' * 30)sort(alist, left_pointer + 1, right)  # 排序右子数组return alistend=sort(alist, 0, len(alist) - 1, False)
print('-' * 30 + '\tend list\t' + '-' * 30)
print(f"最终排序结果为:{end}")# 方式二【无排序步骤输出】
alist = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
def sort(alist, left, right):axis_index = right        # 轴索引axis = alist[axis_index]  # 轴值left_pointer = left  # 左指针right_pointer = right - 1  # 右指针if left_pointer > right_pointer:  # 判断左指针是否在右指针的右边，如果是:停止移动returnwhile True:while alist[left_pointer] < axis:  # 左指针向右移动left_pointer = left_pointer + 1while alist[right_pointer] > axis:  # 右指针向左移动right_pointer = right_pointer - 1if left_pointer < right_pointer:  # 指针未重合，左右指针调换alist[left_pointer], alist[right_pointer] = alist[right_pointer], alist[left_pointer]elif alist[left_pointer] > alist[axis_index]: # 左指针>轴alist[left_pointer], alist[axis_index] = alist[axis_index], alist[left_pointer]  # 轴值交换breakelif left_pointer > right_pointer:  # 左指针在右指针的右边breakif left_pointer - left not in [0, 1]:sort(alist, left, left_pointer - 1)  # 排序左子数组if right - left_pointer not in [0, 1]:sort(alist, left_pointer + 1, right)  # 排序右子数组return alist
end=sort(alist, 0, len(alist) - 1)
print(f"最终排序结果为:{end}")# 方式三 ：根据索引0开始排序
alist = [6, 1, 2, 7, 9, 3, 4, 5, 10, 8]
def sort(alist, left, right):low = lefthigh = rightif low > high:returnmiddle = alist[low]while low != high:while low < high:if alist[high] > middle:high = high - 1else:alist[low] = alist[high]breakwhile low < high:if alist[low] < middle:low = low+1else:alist[high] = alist[low]breakalist[low] = middlesort(alist, left, low - 1)sort(alist, high + 1, right)return alistprint(sort(alist, 0, len(alist) - 1))