网站建设技术方案模板,在百度怎么建立自己的网站吗,wordpress透明主题,精选网站建立 推广 优化快速排序基本原理1.快速排序1.1 基本原理1.2 快速排序执行步骤1.2.1 分区包含步骤1.2.1 分区步骤1.3 快速排序大O记法表示2. 将[0,5,2,1,6,3]进行快速排序 【实战】2.1 第一次分区步骤2.2 第二次分区步骤2.3 第三次分区步骤2.4 第四次分区步骤3.快速排序代码实现1.快速排序
1.…
快速排序基本原理1.快速排序1.1 基本原理1.2 快速排序执行步骤1.2.1 分区包含步骤1.2.1 分区步骤1.3 快速排序大O记法表示2. 将[0,5,2,1,6,3]进行快速排序 【实战】2.1 第一次分区步骤2.2 第二次分区步骤2.3 第三次分区步骤2.4 第四次分区步骤3.快速排序代码实现1.快速排序
1.1 基本原理
快速排序依赖于一个名为分区的概念分区从数组随机选取一个值以此值轴将比它小的值放到它左边比它大的值放到它右边
1.2 快速排序执行步骤
1.2.1 分区包含步骤
比较每个值都要与轴做比较。交换在适当时候将左右指针所指的两个值交换位置。
1.2.1 分区步骤 第一次分区步骤 左指针逐个格子向右移动当遇到大于或等于轴的值时停止移动。右指针逐个格子向左移动当遇到小于或等于轴的值时停止移动。将两指针所指的值交换位置。重复步骤直至两指针重合或左指针移到右指针的右边。将轴与左指针所指的值交换位置【左指针轴时交换】。 子数组分区 6. 对其轴左右两侧的元素进行排序。 7. 对轴左右的两个子数组递归重复第 1、2 步两个子数组各自分区并形成各自的轴以及由轴分隔的更小的子数组。然后对这些子数组分区。 8. 当分出的子数组长度为 0 或 1 时排序结束。 每次分区完成时在轴左侧的那些值肯定比轴要小在轴右侧的那些值肯定比轴要大 轴数据的值放在了正确的位置。
1.3 快速排序大O记法表示
快速排序大O记法表示: O(NNN)
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, flagTrue):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 alistendsort(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
endsort(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 low1else:alist[high] alist[low]breakalist[low] middlesort(alist, left, low - 1)sort(alist, high 1, right)return alistprint(sort(alist, 0, len(alist) - 1))
