百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 编程网 > 正文

十大排序算法(四)--- 快速排序 快速排序算法视频

yuyutoo 2024-10-12 01:09 6 浏览 0 评论

十大排序算法(四)--- 快速排序

快速排序算法采用的是分治法的思想(Divide and Conquer), 它把一个待排序的数组,以某个元素或者称为基准(这里记为PIVOT)为界,分为两个子数组,比PIVOT小的全部移到到PIVOT左边,比PIVOT大的全部移动到PIVOT右边。再分别对以PIVOT分开的两个子数组重复该过程,直到无法再分。

快速排序正常情况下时间复杂度为O(nlogn)。最坏情况下为O(n^2)。最坏情况发生在每次排序都需要移动所有剩下待排序的元素,这种情况虽然很少发生,但是为了避免这样的情况可以采用随机选择PIVOT元素的方法来预防。下面描述算法的实现步骤:

  1. 随机的从待排序数组中选择一个元素作为PIVOT
  2. 将所有比PIVOT小的数放到PIVOT的左边,比PIVOT大的数放到PIVOT的右边。跟PIVOT一样大的数,放到左右都可以。这个步骤称为Partition。这样以PVIOT为界分成了左右两个子数组。
  3. 对#2分成两个子数组递归进行#1~#3操作,直到排序完成。

假设我们要对A[5, 3, 6, 1, 2, 8]留个数进行排序,下图展示了排序的过程。

绝大多数情况下,快速排序是高效的,但是快速排序不是稳定的。下面是python的代码实现。有兴趣的同学,也可以用其它编程语言尝试实现一下。

import random

A = [5, 3, 6, 1, 2, 8]

def quick_sorting(data, left, right):

if left >= right : return

mark = random.randint(left, right)

data[left], data[mark] = data[mark], data[left]

mark = left

tmp = data[left]

for i in range(left+1, right+1):

if data[i] < tmp:

mark += 1

data[i], data[mark] = data[mark], data[i]

data[left], data[mark] = data[mark], data[left]

quick_sorting(data, left, mark-1)

quick_sorting(data, mark+1, right)

def main():

right=len(A)-1

left = 0

#Ascending

quick_sorting(A, left, right)

print(A)

if __name__=='__main__':

main()

将上面的代码保存到一个文本文件,后缀名修改为.py。可以用python解释器执行一下,会输出如下结果:

可以看到,排序正确。

相关推荐

MySQL中的数据类型(mysql数据类型有哪些,并举例)

MySQL中的数据类型...

mysql窗口函数over中rows_MySQL窗口函数

下面的讲解将基于这个employee2表:mysql>SELECT*FROMemployee2;+----+-----------+------+---------+---------...

别再说你精通数据库,MySQL的设计和列类型选取真的很有讲究

总想写一篇MySQL的设计和列类型选取的文章,一直挤不出时间。天天晚上都要加班,正逢5.1放假,抽了几天就有了此文。如果对朋友们能有帮助的话,关注一波不过分吧?求关!选择更优的数据类型尽量选择存储空间...

MySQL数据库知识(mysql数据库相关知识)

MySQL是一种关系型数据库管理系统;那废话不多说,直接上自己以前学习整理文档:查看数据库命令:(1).查看存储过程状态:showprocedurestatus;(2).显示系统变量:show...

数据库:MySQL 高性能优化规范建议

数据库命令规范所有数据库对象名称必须使用小写字母并用下划线分割所有数据库对象名称禁止使用MySQL保留关键字(如果表名中包含关键字查询时,需要将其用单引号括起来)数据库对象的命名要能做到见名识意,...

MySQL实战——表结构设计之数字类型

整型不建议刻意去用unsigned属性,因为在做一些数据分析时,SQL可能返回的结果并不是想要得到的结果。比如在财务的场景下,经常会做一些加减操作。MySQL要求unsigned数值相减之...

MySQL数据库入门(四)数据类型简介

在MySQL中数据类型有以下五种:数字整数:常用的有2种,一是int型,int型最多可以表示10位数字(无符号的4开头,有符号的2开头;二是tinyintunsigned,用来表示年龄(值范围是0-...

mysql常用语句超级详细汇总(mysql常用语法)

1.连接数据库:连接本地数据库:mysql-uroot-p连接远程数据库:mysql-h192.169.22.199-uroot-p退出数据库:exit...

MYSQL——CAST()函数的用法(mysql中case)

语法为:Cast(字段名as转换的类型),其中类型可以为:CHAR[(N)]字符型DATE日期型DATETIME日期和时间型...

MySQL存储引擎背后的真相:为何InnoDB并非所有场景的最佳选择

MySQL存储引擎背后的真相:为何InnoDB并非所有场景的最佳选择引言部分你是否遇到过这样的情况:明明已经按照最佳实践选择了MySQL的InnoDB引擎,却发现某些查询依然缓慢得令人沮丧?或者当你的...

MySQL 表分区?涨知识了(mysql数据表分区)

1.什么是表分区...

《MySQL必知必会》_笔记08(mysql必知必会mobi)

第19章插入数据一、数据插入概述INSERT语句用于向数据库表中插入(添加)数据,是SQL中常用的数据操作语句之一。它可以用多种方式使用,包括插入完整的行、插入行的一部分、插入多行以及插入某些查询的...

当 SQL Server(mssql-jdbc) 遇上 BigDecimal → 精度丢失,真坑!

开心一刻  中午和哥们一起喝茶  哥们说道:晚上喝酒去啊...

MYSQL有哪些数据类型(mysql有哪些数据类型,有哪些运算符)

整理下以便查阅,还想吐槽下:这头条怎么就不能给文章分类呢?整数类型...

使用MySQL分区的注意事项(使用mysql分区的注意事项有哪些)

MySQL分区是将一个表分解成多个区块进行操作和保存,从而降低每次操作的数据量,提高性能。从逻辑上看,只有一个表,但物理上这个表可能由多个物理分区组成,每个分区都是一个独立的对象,可以进行独立处理。...

取消回复欢迎 发表评论: