具有快速排序插入、排序删除和查找的数据结构
我正在寻找一个非常具体的数据结构。假设已知元素的最大数量。所有元素都是整数。允许复制。行动包括：
查阅如果我插入n个元素，a[0]是最小的元素，a[a.length-1]是最高的元素a[k]是k个最小的元素。所需运行时间：O（1）
插入。执行排序的插入，插入（b）其中b是一个整数。所需的运行时：O（log n）
删除。删除（i）删除第i个元素。所需的运行时：O（log n）
我想要一种数据结构，是这样吗？我的问题与语言无关，但我用C语言编写代码。
共有1个答案
我相信这样的数据结构是不存在的。对任何元素的恒定查找（例如索引）都需要连续的内存，这使得如果你想保持范围排序，在小于O（n）的地方插入是不可能的。
关于哈希表和包装器，有很多争论，但在提到它们时，有两件事需要记住：
>
哈希表在O（1）中具有平均访问权限（插入、删除、查找），但这假设很少有哈希冲突。如果您希望满足有关悲观复杂性的要求，则哈希表是不适用的，因为它们的悲观访问时间是O（n）。
哈希表本质上是无序的。大多数情况下，它们确实有用于存储（例如）数据桶的内部数组，但元素本身既不是都在连续内存中，也不是按某些属性排序的（除了它们的散列的模，散列本身应该为类似对象生成非常不同的值）。
为了不让你两手空空——如果你希望尽可能接近你的需求，你需要指定你会牺牲哪些复杂性来实现其他复杂性。我想推荐std:：priority_queue或std:：multiset。
>
std:：multiset*提供对其中每个元素的访问，但成本更高-O（log\n）。它还实现了插入和删除中的O（log_n）。
*小心-不要与不允许重复元素的std:：set混淆
-
java中是否有内置的数据结构可以为排序列表提供高效的性能？我还需要修改排序列表，包括插入和删除操作。我首先使用arraylist。我认为在插入和删除的情况下，arraylist的性能可能不够好。什么样的数据结构适合使用？如果没有足够快的内置数据结构，在设计自定义数据结构之前，我可以朝哪个方向走？
-
快速排序 from typing import List def quick_sort(arr: List, left, right) -> List: """ 快速排序是对冒泡排序的改进，核心思想是找到一个中值点pivot，然后将小于等于pivot的放在pivot的左边，大于pivot的放在右边，一直递归到无法拆分pivot点。 :param arr: :re
-
我在Java编码，我需要一个排序的整数数据结构，它有最大的O（log（n））插入时间和O（1）按索引查找。是否有一个内置的数据结构可以做到这一点，或者如果没有，我如何自己编程一个？ 我知道集合可以完成第一个任务，但要查找元素I，我需要在元素I之前遍历所有元素。
-
本文向大家介绍java数据结构之插入排序，包括了java数据结构之插入排序的使用技巧和注意事项，需要的朋友参考一下 插入排序就是把当前待排序的元素插入到一个已经排好序的列表里面。 一个非常形象的例子就是右手抓取一张扑克牌，并把它插入左手拿着的排好序的扑克里面。 插入排序的最坏运行时间是O(n2)， 所以并不是最优的排序算法。 如果输入数组已经是排好序的话，插入排
-
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要 Ο(nlogn) 次比较。在最坏状况下则需要 Ο(n2) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他 Ο(nlogn) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来。 快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两
-
1. 前言 本节内容是排序算法系列之一：快速排序，主要讲解了快速排序的主体思路，选取了一个待排序的数字列表对快速排序算法进行了演示，给出了快速排序算法的 Java 代码实现，帮助大家可以更好地理解快速排序算法。 2. 什么是快速排序？ 快速排序（Quick Sort），是计算机科学与技术领域中非常经典的一种排序算法，应用分治思想进行排序。 快速排序由于其时间复杂度优于大部分的排序算法，因而命名为快