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

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

yuyutoo 2024-10-12 01:09 4 浏览 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解释器执行一下,会输出如下结果:

可以看到,排序正确。

相关推荐

国内外注塑机及电脑密码大全(常见注塑机通用密码)

一、国外注塑机(日本、德国等)东洋注塑机万能码:9422345日精注塑机密码:222|7777DAMEG注塑机密码:000000000新泻注塑机密码:241650|261450住友注塑机密码:...

并发编程实战来咯(并发编程的艺术和并发编程实战)

提到并发编程,就不得不提C++ConcurrencyinAction(SecondEdition)(《C++并发编程实战第2版》)啦!《C++并发编程实战第2版》英文原版&中文译版看到这个...

无锁队列Disruptor原理解析(无锁队列应用场景)

队列比较队列...

理解 Memory barrier(内存屏障)(内存屏障 volatile)

...

并发编程 --- CAS原子操作(cas概念、原子类实现原理)

...

无锁CAS(附无锁队列的实现)(cas是一种无锁算法)

本文所有代码对应的Github链接为:https://github.com/dongyusheng/csdn-code/tree/master/cas_queue...

Linux高性能服务器设计(linux 服务器性能)

C10K和C10M计算机领域的很多技术都是需求推动的,上世纪90年代,由于互联网的飞速发展,网络服务器无法支撑快速增长的用户规模。1999年,DanKegel提出了著名的C10问题:一台服务器上同时...

浅谈Go语言的并发控制(go语言 并发)

前言本文原创,著作权归...

Datenlord |Etcd 客户端缓存实践(etcd 数据存储)

简介和背景...

无锁编程——从CPU缓存一致性讲到内存模型

缓存是一个非常常用的工程优化手段,其核心在于提升数据访问的效率。缓存思想基于局部性原理,这个原理包括时间局部性和空间局部性两部分:...

打通 JAVA 与内核系列之 一 ReentrantLock 锁的实现原理

...

如何利用CAS技术实现无锁队列(cas会锁总线吗)

linux服务器开发相关视频解析:...

Kotlin协程之一文看懂Channel管道

概述Channel类似于Java的BlockingQueue阻塞队列,不同之处在于Channel提供了挂起的send()和receive()方法。另外,通道Channel可以...

详解C++高性能无锁队列的原理与实现

1.无锁队列原理1.1.队列操作模型...

Javascript 多线程编程的前世今生

...

取消回复欢迎 发表评论: