普通快排与随机快排的世纪大战

2024-08-24 07:18

本文主要是介绍普通快排与随机快排的世纪大战,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

以下文章来源于微信公众号“老肥码码码” ,作者斐波那契小李

 

点击上方“算法与数据之美”,选择“置顶公众号”

更多精彩等你来!

算法一直是计算机学科中一个非常核心的内容,学习大黑书可以让我们年轻人得到充沛的力量(也就是少点头发),在程序的海洋里快乐徜徉。

排序算法是算法之中一个既基础又核心的内容,而快速排序则是比较排序中的佼佼者。今天我们就一起来探究一下快速排序。

普通快速排序

快速排序是一个经典的分治算法,解决分治问题的三个步骤就是 分解、解决、合并。

拆开来看看快速排序的基本思想:

分解 :将输入数组A[l..r]划分成两个子数组的过程。选择一个p,使得A被划分成三部分,分别是A[l..p-1],A[p]和A[p+1..r]。并且使得A[l..p-1]中的元素都小于等于A[p],同时A[p]小于等于A[p+1..r]中的所有元素。

解决:递归调用快速排序,解决分解中划分生成的两个子序列的排序。

合并:因为子数组都是原址排序的,所以无需进行合并操作,数组A[p..r]已经有序。

算法导论书上给出了简单易懂的伪代码,我在这直接给出Python的实现代码

def Quick_Sort(A,p,r):if p<r:q=Partition(A,p,r)Quick_Sort(A,p,q-1)Quick_Sort(A,q,r)def Partition(A,p,r):x=A[r]i=p-1for j in range(p,r):if A[j]<=x:i+=1A[i],A[j]=A[j],A[i]A[i+1],A[r]=A[r],A[i+1]return i+1

这里看到数组的划分是直接选择了子数组的最后一个元素,那么当待排序列已经有序时,划分出的子序列便有一个序列是不含任何元素的,这使得排序的性能变差。为了改善这种情况,我们可以选择引入一个随机量来破坏有序状态。

快速排序的随机化版本

我们可以通过在选择划分时随机选择一个主元来实现随机快速排序。仅需对上述代码做出小小的改动。

def Quick_Sort_Random(A,p,r):if p<r:q=Partition1(A,p,r)Quick_Sort(A,p,q-1)Quick_Sort(A,q,r)def Partition1(A,p,r):k=random.randint(p,r)A[k],A[r]=A[r],A[k]return Partition(A,p,r)

性能比较

是骡子是马我们拉出来溜溜,我对两种快排的性能做了一个简单的测试。首先是一定数量的随机序列,运行的时间单位为秒,下表中的结果是经多次运行所取得的平均值。

方法1031041051061075*107108
普通快排0.002045570.024539950.323358134.8364108463.91342704456.205160781176.27041785
随机快排0.002288480.032929490.397340495.4132348766.26046769451.385529991108.05737074

也可以使用可视化的方法将上表变得更加清楚,普通排序在数据量较小时具有一定的性能优势,随机快排可能是因为添加了随机选择这一项操作而影响了部分性能,但是随着数据量进一步增大,两者之间的性能会非常接近。

接下来是对有序序列进行测试,

方法103104105106
普通快排0.06262696///
随机快排0.034402280.451898777.2805512095.54553382

普通快排在数据量非常小的时候就把栈给挤爆喽,从另一侧面反映出随机快排的必要性,在处理比较极端也就是完全有序的序列时具有较大的优势。

今天的分享就到这里啦,Bye~

提前祝大家

元旦快乐

2020 红红火火~

   

编程到底难在什么地方?

S2云顶夺魁助手一键配置!

纯前端实现人脸识别自动佩戴圣诞帽

这篇关于普通快排与随机快排的世纪大战的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1101816

相关文章

尼采:在世纪的转折点上

孤独是一颗值得理解的心灵寻求理解而不可得,它是悲剧性的;无聊是一颗空虚的心灵寻求消遣而不可得,它是喜剧性的;寂寞是寻求普通人间温暖而不可得,它是中性的。我最孤独的时候就是无聊和寂寞过后无法排解才让我感到孤独!

AI学习指南深度学习篇-带动量的随机梯度下降法的基本原理

AI学习指南深度学习篇——带动量的随机梯度下降法的基本原理 引言 在深度学习中,优化算法被广泛应用于训练神经网络模型。随机梯度下降法(SGD)是最常用的优化算法之一,但单独使用SGD在收敛速度和稳定性方面存在一些问题。为了应对这些挑战,动量法应运而生。本文将详细介绍动量法的原理,包括动量的概念、指数加权移动平均、参数更新等内容,最后通过实际示例展示动量如何帮助SGD在参数更新过程中平稳地前进。

Chapter 13 普通组件的注册使用

欢迎大家订阅【Vue2+Vue3】入门到实践 专栏,开启你的 Vue 学习之旅! 文章目录 前言一、组件创建二、局部注册三、全局注册 前言 在 Vue.js 中,组件是构建应用程序的基本单元。本章详细讲解了注册和使用 Vue 的普通组件的两种方式:局部注册和全局注册。 本篇文章参考黑马程序员 一、组件创建 ①定义 Vue 组件是一种具有特定功能的 Vue 实

快排Java

快速排序的复杂度 快排代码 package leetcode;import java.util.Arrays;public class QuickSort {public static void quickSort(int[] array, int low, int high) {if (low < high) {int pivotIndex = partition(array, low,

AI学习指南深度学习篇-带动量的随机梯度下降法简介

AI学习指南深度学习篇 - 带动量的随机梯度下降法简介 引言 在深度学习的广阔领域中,优化算法扮演着至关重要的角色。它们不仅决定了模型训练的效率,还直接影响到模型的最终表现之一。随着神经网络模型的不断深化和复杂化,传统的优化算法在许多领域逐渐暴露出其不足之处。带动量的随机梯度下降法(Momentum SGD)应运而生,并被广泛应用于各类深度学习模型中。 在本篇文章中,我们将深入探讨带动量的随

stl的sort和手写快排的运行效率哪个比较高?

STL的sort必然要比你自己写的快排要快,因为你自己手写一个这么复杂的sort,那就太闲了。STL的sort是尽量让复杂度维持在O(N log N)的,因此就有了各种的Hybrid sort algorithm。 题主你提到的先quicksort到一定深度之后就转为heapsort,这种是introsort。 每种STL实现使用的算法各有不同,GNU Standard C++ Lib

箭头函数跟普通函数的区别

箭头函数(Arrow Function)和普通函数(Function Declaration/Expression)在 JavaScript 中有一些重要的区别,主要体现在以下几个方面: 1. 语法 箭头函数: 语法更简洁,没有 function 关键字。 对于单一表达式函数,结果会隐式返回,不需要 return 关键字。 不需要使用大括号 {},但如果使用,必须显式返回值。 示例:

HDD 顺序和随机文件拷贝和存储优化策略

对于机械硬盘(HDD),顺序拷贝和随机拷贝涉及到磁头的移动方式和数据的读取/写入模式。理解这些概念对于优化硬盘性能和管理文件操作非常重要。 1. 顺序拷贝 定义: 顺序拷贝指的是数据从硬盘的一个位置到另一个位置按顺序连续读取和写入。这意味着数据在硬盘上的位置是线性的,没有跳跃或回溯。 特点: 磁头移动最小化:由于数据是连续的,磁头在读取或写入数据时只需要在磁盘的一个方向上移动,减少了寻道时

热泵专用压缩机与普通压缩机的区别

普通压缩机和低温压缩机在空气源热泵机组上应用对比: 1.普通压缩机 1.低温工况运行时,压缩机高压缩比、产生过热、润滑油变质、涡旋盘磨损等;高温工况运行时,电机过载、轴承磨损、电机绕组超过极限。 2.高水温运行时,高冷凝温度,电机过载、过热;润滑油变质,涡旋盘磨损、轴承磨损,电机绕组超过极限。 3.在低温工况时,能力不够和能效比低,经济性差,在-10度以下能力衰减可达40%以上,COP<1.5W/