当前位置: 首页 > news >正文

快速排序基本原理

快速排序基本原理

  • 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 分区步骤

  • 第一次分区步骤

    1. 左指针逐个格子向右移动,当遇到大于或等于轴的值时,停止移动。
    2. 右指针逐个格子向左移动,当遇到小于或等于轴的值时,停止移动。
    3. 将两指针所指的值交换位置。
    4. 重复步骤,直至两指针重合或左指针移到右指针的右边。
    5. 将轴与左指针所指的值交换位置【左指针>轴时交换】。
  • 子数组分区
    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, 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))

在这里插入图片描述

http://www.lryc.cn/news/5070.html

相关文章:

  • Android开发笔记-提纲(连载中....)
  • React Native(一)
  • Kotlin 26. Kotlin 如何播放音频文件
  • recv和明文收包分析
  • 【IVIF的超分重建】
  • “深度学习”学习日记。--加深网络
  • 2023前端面试总结含参考答案
  • 总览 Java 容器--集合框架的体系结构
  • 即便考分很好也不予录取的研究生复试红线,都是原则性问题
  • Android java创建子线程的几种方法
  • UVa 11212 Editing a Book 编辑书稿 IDA* Iterative Deepening A Star 迭代加深搜剪枝
  • 第一章:unity性能优化之内存优化
  • 2023年家族办公室研究报告
  • Typescript快速入门
  • 如何激励你的内容团队产出更好的创意
  • 机械设备管理软件如何选择?机械设备管理软件哪家好?
  • 深入浅出带你学习shiro-550漏洞
  • 项目(今日指数之环境搭建)
  • PCL 基于投影点密度的建筑物立面提取
  • DDD 参考工程架构
  • 重建,是2023年的关键词
  • 动手写操作系统-00-环境搭建以及资料收集
  • 【scipy.sparse包】Python稀疏矩阵详解
  • 从写下第1个脚本到年薪30W,我的自动化测试心路历程
  • JAVA八股、JAVA面经
  • GAN系列基础知识
  • Linux/CenterOS 7.9配置汉化gitlab服务器
  • 山洪灾害监测预警平台 山洪灾害监测预警系统解决方案 以人为本 科学防御
  • The Number Of ThreadPoolExecutor
  • Linux(Linux各目录结构详解)