腾讯云

文章/答案/技术大牛

发布

社区首页 >问答首页 >排序为1/3的数组上的正常和随机快速排序

问排序为1/3的数组上的正常和随机快速排序
EN

Stack Overflow用户

提问于 2020-12-03 07:32:33

回答 1查看 141关注 0票数 0

我试图计算在具有以下属性的数组上应用快速排序(随机或正常)的时间复杂度：

数组在前2/3中没有排序，最大的元素是t。

下一个1/3被排序，这里的所有元素都大于t\

我知道，在正常的快速排序中，选择这两个部分之间的屏障会导致不必对下一个1/3排序，但我无法找到一种形式(数学)方法来计算时间复杂性的渐近界。

提前感谢

randomized-algorithm

sorting

big-o

complexity-theory

quicksort

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-12-03 07:49:12

随机快速排序相当于先对数组进行洗牌，然后应用朴素的快速排序。洗牌需要线性时间，这样就可以得到快速排序的平均时间复杂度，而不考虑部分排序的输入，即O(n log )。

朴素快速排序在这些输入上将具有二次时间复杂度，因为最终元素t将被选择为支点，t发生在排序区域之前，因此该区域将被选择为一个完整的分区。朴素快速排序将在( n /3)中占用这个分区的二次时间，这在n中是二次的。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/65129024

复制

JavaScript 数组排序——快速排序[通俗易懂]

java https 网络安全

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/133116.html原文链接：https://javaforall.cn

全栈程序员站长

2022/08/14

7260

iOS数组的快速排序

ios 排序

// 方法1:NSComparator NSArray *listGroupname = [self.listTeams sortedArrayUsingComparator:^(NSString *n1,NSString *n2) { NSString *val1 = [[NSString alloc]init]; NSString *val2 = [[NSString alloc]init]; if (val1 > val2) { return NS

艳艳代码杂货店

2021/10/30

5720

排序之快速排序(上)

其他

希尔排序相当于直接插入排序的优化，它们同属于插入排序类，堆排序相当于简单选择排序的优化，它们同属于选择排序类。而快速排序其实就是冒泡排序的升级，它们都属于交换排序类。即它也是通过不断的比较和移动交换来实现排序的，只不过它的实现，增大了记录的比较和移动的距离，将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面，从而减少了总的比较次数和移动交换次数，而不是像冒泡排序那样左右两两进行比较和交换。

青石路

2018/09/10

1.6K0

数组快速排序

int 递归排序数据数组

快速排序是在数据源中抽取一份数据作为样本，与所有需要排列的数据进行对比，根据需要把比样本小的数据放置到数据源的左侧位置，比样本大的数据放置到数据源的右侧位置。以此来对数据进行排序。具体实现如下：

我与梦想有个约会

2023/10/20

1110

只含有1、2、3的数组排序

编程算法

不要举 00 11 22 、 22 11 00 、 11 00 22 这类特点明显不够随机的用例。

陈黎栋

2020/02/18

5860

QuickSort-随机快速排序

其他

import java.util.Arrays; public class QuickSort { public static void quickSort(int[] arr) { if (arr == null || arr.length < 2) { return; } sort(arr, 0, arr.length - 1); } public static void sort(int[] arr, int L, int R) { if (L < R) { /

2018/08/20

4260

数组查找、冒泡排序、快速排序（一）

java

数组查找是一种常见的算法，用于在一个已排序或未排序的数组中查找指定的值。常用的数组查找算法包括线性查找、二分查找、哈希表查找等。

玖叁叁

2023/05/10

4120

数组查找、冒泡排序、快速排序（二）

java

冒泡排序是一种简单的排序算法，它的实现原理是：每次比较相邻的两个元素，如果它们的顺序不正确就交换它们的位置，这样每一轮排序都会将最大的元素冒泡到数组的末尾。由于每次排序都只能将一个元素归位，因此需要进行n-1轮排序才能完成整个排序过程。

玖叁叁

2023/05/10

3540

Java 数组、排序和查找（1）

char int max 数据类型数组

数组可以进行存放多个同一类型的数据。数组是一种引用数据类型，即数组就是一组数据。

周小末天天开心

2022/10/26

6700

Java 数组、排序和查找（3）

java python int 数组

思路： 1. 定义一个字符串数组 2. 接收用户输入，遍历数组，逐一比较，如果有，则提示信息，并退出

周小末天天开心

2022/10/26

5280

堆排序和快速排序

其他

python03-05-05希尔排序计算机科学9.2&9.3希尔排序与堆排序（浙江大学陈越、何钦铭

热心的社会主义接班人

2018/08/02

3570

冒泡排序和快速排序的java实现

编程算法

转发请注明原创地址 http://www.cnblogs.com/dongxiao-yang/p/6264831.html

sanmutongzi

2020/03/04

4740

Leetcode No.912 排序数组（快速排序）

编程算法

示例 2：输入：nums = [5,1,1,2,0,0] 输出：[0,0,1,1,2,5]

week

2021/11/29

3090

js数组排序—自定义快速排序

java https 编程算法网络安全腾讯云测试服务

如果数组元素为非数字类型，必须要手动指定排序规则，否则可能会产生诡异的结果。比如，两个字符串相减结果为NaN，这回导致排序不生效。

全栈程序员站长

2022/08/22

3.4K0

基础和常用的排序算法：冒泡排序，选择排序，插入排序，快速排序

工作基础排序排序算法数组

冒泡排序是一种基础的排序算法，通过重复地交换相邻元素来工作，如果它们的顺序错误就互换位置，直到没有元素需要交换。

运维开发王义杰

2023/09/26

2400

快速排序数组+递归实现

编程算法

1. 用一个自定义的分割方法split()选取用来作分割的元素(也称为partition主元)，最简单的分割方法是选定待排范围的第一个数为partition主元，一趟快排完成后，主元e是数组arr中第i个元素，主元e左边的元素都不大于e，主元e右边的元素都大于e； 2. 使用两个跟踪变量(forward和backward)，递归地对从i到backward采用快速排序方法quickSort()，并递归地对从forward到i采用快速排序方法quickSort()； 3. backward从后向前递减，forward从前向后递增。forward从前往后扫，当出现第一个比主元大的数，将该数放进arr[i]; backward从后向前扫，当出现第一个比主元小的数时，将该数放进arr[i]. 当forward与backward相等时，停止...

Enjoy233

2019/03/05

6520

选择排序和快速排序（Java）

编程算法

选择排序思想：指针指向数组头，从指针位置到数组尾遍历最小值位置，将该位置与指针位置交换值，指针向后位移一位，循环遍历最小值实现代码：

aruba

2021/12/06

6790

数组快速排序再解

变量递归排序数据数组

我们以前是写过数组快速排序的例子的，当时因为时间问题并没有详细记录快速排序的过程是怎么样的。本文在此对数组快速排序做一个详解，希望对学习者有所帮助。

我与梦想有个约会

2023/10/20

1420

(3)交换排序之快速排序

编程算法 http

suveng

2019/09/17

4050

java冒泡排序和快速排序

其他

一、冒泡排序 1.算法介绍设排序表长为n，从后向前或者从前向后两两比较相邻元素的值，如果两者的相对次序不对(A[i-1] > A[i])，则交换它们，其结果是将最小的元素交换到待排序序列的第一个位置

三哥

2018/06/15

1.3K0

相似问题

随机快速排序:低分区大小的概率为1

随机快速排序

有人能澄清快速排序和随机快速排序的区别吗？

对象数组列表上的插入和快速排序

为小数据选择排序和快速排序

添加站长进交流群

领取专属 10元无门槛券

AI混元助手 在线答疑

关注 腾讯云开发者公众号

洞察 腾讯核心技术

剖析业界实践案例

问排序为1/3的数组上的正常和随机快速排序
EN