首页 > 其他分享 >快速排序原理,及为何使用

快速排序原理,及为何使用

时间:2023-12-04 22:36:30浏览次数:29  
标签:标准值 复杂度 元素 数组 为何 原理 排序

1.原理

对于每一次函数调用,选当前数组的第一个元素为标准值,遍历数组,把所有小于标准值的元素放到标准元素的左边,大于等于标准值的元素放到右边。知道调用函数中的数组长度小于2。

2.为何使用

1).虽然时间复杂度不稳定->(O2),但是在许多应用场景中,我们并不需要稳定性。
2).没有病态的比较,即当a<b,b<c时,若再对a和c进行比较,就叫做病态的比较,显然对快速排序,病态比较不会发生。
3).空间复杂度小,快速排序是原地排序(python实现还蛮简单的,C语言?)

标签:标准值,复杂度,元素,数组,为何,原理,排序
From: https://www.cnblogs.com/pure4knowledge/p/17876172.html

相关文章

  • 【组成原理-指令】扩展操作码的树形解法
    仿照哈夫曼树(或前缀编码,Prefix-free)的解法,目前先不解释具体怎么画了,直接放例题,大家自己慢慢品味吧。【例1】某指令系统指令长16位,操作码字段为4位,地址码字段为4位,采用扩展操作码技术,形成三地址指令15条、二地址指令15条、一地址指令15条、零地址指令16条。【解......
  • 排序 - 插入排序
    插入排序直接插入排序算法描述将一条记录插入到有序表中,得到新的有序表。将需要调整位置的元素暂存在r[0]处,然后再进行插入。算法实现voidInsertSort(SqList&L){for(i=2;i<=L.length;i++)if(L.r[i].key<L.r[i-1].key){L.r[0]=L.......
  • 详解RSA加密原理
    密码学密码学是指研究信息加密,破解密码的技术科学。密码学的起源可追溯到2000年前。而当今的密码学是以数学为基础的。密码学的历史大致可以追溯到两千年前,相传古罗马名将凯撒大帝为了防止敌方截获情报,用密码传送情报。凯撒的做法很简单,就是对二十几个罗马字母建立一张对应......
  • Cadence SPB 22.1 -- 层次原理图设计06Day
    1、自上而下:先设计好母图,再用母图的方块图来设计子图①、创建分级模块(HierarchicalBlock),在原理图设计的页面,执行菜单命令“Place”→“HierarchicalBlock”。    ②、在弹出的对话框中,输入分级模块的名称,选择合适的参数,单击“OK”按钮。     ......
  • AcWing 785. 快速排序
    题面:给定你一个长度为\(n\)的整数数列。请你使用快速排序对这个数列按照从小到大进行排序。并将排好序的数列按顺序输出。原题链接:785.快速排序-AcWing需要注意的几个点:左右哨兵的发动顺序;相同元素的相对位置;边界划分问题[1]。#include<bits/stdc++.h>usingna......
  • 详解十大经典排序算法(三):插入排序(Insertion Sort)
    算法原理每次从无序部分选择一个元素,将其插入到有序部分的正确位置,重复这个过程直至整个数组有序。算法描述插入排序是一种简单直观的排序算法,它的基本思想是将一个待排序的元素插入到已经排序好的序列中的适当位置,从而得到一个新的、长度加一的有序序列。插入排序的过程类似于整理......
  • 算法之快速排序2基准元素的选择
    一:概述基准元素,英文是pivot,在分治的过程中,基准元素为中心,把其他的元素移动到它的左右两边。二:具体说明最简单的方式就是选择数列的第1个元素。这种选择在绝大多数情况下是没有问题的。但是,假如有一个原本逆序的数列,期望排列成顺序数列,那会出现什么情况呢?整个数列被分成了两部分,每一......
  • asyncio协程库实现原理剖析
    目录迭代器可迭代对象&迭代器自定义迭代器生成器生成器就是迭代器生成器的4个状态用yield重构迭代器生成器三种应用场景生成器进阶函数运行机制函数对象和代码对象函数运行帧同步和异步协程yield表达式yield表达式的优先级send()用法yield表达式作为函数入参使用close()结束生成......
  • Redis的内存回收原理,及内存过期淘汰策略详解
    Redis内存回收机制Redis的内存回收主要围绕以下两个方面1Redis过期策略:删除过期时间的key值2Redis淘汰策略:内存使用到达maxmemory上限时触发内存淘汰数据Redis的过期策略和内存淘汰策略不是一件事,实际研发中不要弄混淆了,下面会完整的介绍两者。Redis过期策略过期策略通常有以......
  • 深入了解汉字转拼音转换工具:原理与应用
    一、引言汉字作为世界上最古老、最具象形意的文字之一,承载了数千年的历史文明。然而,在现代信息技术环境下,汉字的输入、输出和检索等方面存在一定的局限性。拼音作为汉字的一种音标表达方式,能够有效地解决这些问题。本文将为您介绍一款汉字转拼音转换工具,帮助您更好地理解和应用......