如果数组的元素数为偶数，那么哪个值将成为快速排序的“完美”轴心？
在快速排序算法中，轴心（pivot）是用来划分数组的元素的值。它被选为数组中的一个元素，并且将数组分为两个部分：小于轴心值的元素和大于轴心值的元素。
对于数组元素数为偶数的情况，我们可以选择任意一个元素作为轴心。因为快速排序算法的思想是通过不断地将数组分割成更小的子数组来进行排序，而不是直接比较数组中的元素。因此，选择哪个元素作为轴心并不会影响最终的排序结果。
然而，为了提高快速排序算法的效率，我们通常会选择数组中的中间元素作为轴心。这样做的好处是可以尽量均匀地将数组分割成两个部分，从而减少排序的时间复杂度。
总结起来，对于数组元素数为偶数的情况，任意一个元素都可以作为快速排序的“完美”轴心。
相关·内容
3回答
我有一个练习，其中我必须改进一个算法。此算法接受一个数组，并将偶数放在左侧(排序)，将赔率放在右侧(未排序)。算法效率很低，所以我必须改进它。
以下是练习的原始代码，我必须“改进”：
public void what (int [] arr) {
int temp;
for (int i=0; i<arr.length; i++)
if (arr[i]%2 == 0) {
temp = arr[i];
for (int j=i; j>0; j--)
arr[j] = ar
浏览 0提问于2013-06-15得票数 1
回答已采纳
1回答
我想我知道快速排序algorithm.But，我需要帮助来找出它最坏的情况。
让我们看一下下面的快速排序代码->
void quicksort(int arr[],int low,int high) //low and high are pased from main()
{
int m;
if(low<high)
{
m=partition(arr,low,high);
quicksort(arr,low,m-1);
quicksort(arr,m+1,high);
}
}
int partition(int arr[],int low,int high)
浏览 0提问于2014-11-03得票数 2
我读到可以让快速排序在O(nlogn)上运行
该算法表示，在每一步中选择中位数作为枢轴
但是，假设我们有这样的数组：
10 8 39 2 9 20
哪个值将是中位数？
在数学中，如果我没记错的话，中位数是(39+2)/2 = 41/2 = 20.5
但是我的数组中没有20.5
提前感谢
浏览 0提问于2012-01-03得票数 3
回答已采纳
4回答
这是快速排序还是合并排序？
、、、、
下面是函数： def sort(unsorted):
less = []
equal = []
greater = []
if len(unsorted) < 1:
return unsorted
pivot = unsorted[-1]
for element in unsorted:
if element < pivot:
less.append(element)
if element == pivot:
equal.appen
浏览 27提问于2017-08-12得票数 0
回答已采纳
此实现在任意大小的数组上清除堆栈：
function quickSort(arr){
let pivot = arr[arr.length-1]
return quickSort(arr.filter((num) => (num < pivot)))
.concat(quickSort(arr.filter((num) => (num >= pivot))))
}
为什么这个不起作用？如果它可以修复，我该怎么做呢？
浏览 2提问于2016-11-05得票数 0
import random, timeit
#Qucik sort
def quick_sort(A,first,last):
global Qs,Qc
if first>=last: return
left, right= first+1, last
pivot = A[first]
while left <= right:
while left <=last and A[left]<pivot:
Qc= Qc+1
left= left + 1
浏览 19提问于2020-04-27得票数 1
回答已采纳
2回答
我检查了K&R书中的快速排序代码，2小时后我仍然不能理解第一个交换(swap(a, left, (left+right)/2);)实现了什么。我试着删除它，但排序仍然有效。有人能解释一下吗？这是一个性能问题吗？如果是这样，为什么呢？这个动作在我看来似乎是随机的(也就是说，在一些数字组上，它将提高性能，而在一些数字上则不会)。
谢谢。
void qsort(int a[], int left, int right)
{
int i, last;
if (left >= right)
return;
swap(a, left, (left+
浏览 2提问于2015-05-09得票数 2
3回答
人们普遍认为，快速排序的最佳情况是O(nlogn)，因为每次都会将数组划分为大约一半。也有人说，假设数组是排序的，最坏的情况是n^2。
难道我们不能通过设置一个名为swap的布尔值来修改快速排序吗？例如，如果第一次传递没有初始交换位置，那么我们可以假设数组已经排序，因此不再对数据进行进一步分区。
我知道修改后的冒泡排序通过检查交换来使用这一点，允许最好的情况是O(n)而不是O(n^2)。这种方法可以应用于快速排序吗？为什么或者为什么不？
浏览 0提问于2011-12-23得票数 3
回答已采纳
好吧，我想对给定的3值使用快速排序，不管是什么值，我如何才能得到最坏的情况，也就是9操作？
有没有人可以画一棵树，并展示它是如何显示nlogn和n^2操作的？我试着在网上找过了，但我还是没能画出一幅合适的画来说明这一点。
浏览 7提问于2016-09-07得票数 0
1回答
这是我的实现。当我放入100个大小为1000000的数组时，排序时间为300秒。我的另一个算法，合并排序，做了40秒。我想知道，是否有一些东西可能会减慢我的算法。
template <typename TYP> void quick_sort(TYP *tab, int poczatek, int koniec) {
int i = poczatek;
int j = poczatek;
int srodek = (poczatek + koniec) / 2;
int piwot = tab[srodek];
swap(tab[srodek], tab[ko
浏览 0提问于2021-03-23得票数 1
3回答
也就是说，当给定一个已经排序的列表时，快速排序的性能会更好吗？我不明白为什么会出现这种情况，但可能我并不完全理解算法。
此外，当我们在排序时向列表中添加新数据时，快速排序是否可以继续进行？在我看来，算法在一开始就需要所有数据的全集才能“工作”。
浏览 2提问于2013-10-09得票数 0
2回答
我这里有我的Quick sort类
package week4;
class QuickSort<T extends Comparable<? super T>> {
public void display(T[] array) {
int index;
for (index = 0; index < array.length - 1; index++)
System.out.print(array[index] + ", ");
System.out.printl
浏览 0提问于2018-07-29得票数 1
4回答
尝试理解快速排序的复杂性
、、、、
我知道当轴心是最小或最大的元素时，最坏的情况会发生。然后，其中一个分区是空的，我们对N-1个元素重复递归
而是如何计算到O(N^2)
我已经读了几篇文章，但仍然不能完全理解它。
同样，最好的情况是轴是数组的中值，并且左右部分的大小相同。但是，值O(NlogN)是如何计算的呢？
浏览 1提问于2016-10-28得票数 1
有没有人能用“简单的英语”直观而正式地解释一下QuickSort n log是怎么回事？根据我的理解，它必须遍历n个项目，并且它做了这个log n times...Im，不知道如何用语言来表达为什么它做了这个log n次。
浏览 0提问于2012-05-03得票数 61
回答已采纳
1回答
这是我的快速排序代码，它选择最正确的值作为轴心：
def qsort_right(self, array):
less = []
equal = []
greater = []
last_value = len(array) - 1
if len(array) > 1:
pivot = array[last_value]
for i in array:
if i < pivot:
less.append(i)
if i == piv
浏览 2提问于2014-07-27得票数 0
大O表示快速排序，
当pivot索引创建平衡分区时，这意味着什么。
我知道pivot索引是这样的索引，索引左边的数字之和等于索引右边的数字之和。
在创建平衡分区和不创建平衡分区时，它如何影响复杂性？
浏览 0提问于2018-10-17得票数 0
我想说它最糟糕的时间复杂度仍然是n log n，因为我使用中间元素作为轴心，所以即使数组已经排序，当它从分区方法返回时，它仍然是数组的一半。我可能错了，我的DS不是最好的
public static void quicksort(int [] arr, int low, int high){
if(low < high){
int pivot = partition(arr, low, high);
quicksort(arr, low, pivot);
quicksort(arr, pivot+1, high);
浏览 0提问于2020-09-15得票数 0
5回答
嘿，谁能告诉我每一个的基本算法和每一个的跟踪序列。我很困惑，网上有很多方法，我真的不知道哪一个是最简单/最聪明的。谢谢。
浏览 15提问于2010-12-06得票数 2
回答已采纳
我看了一段Youtube的视频，视频中一些学生演示了不同的算法来求出两个排序数组的中位数:算法详见：。我正在尝试实现他的“比较中值”算法，结果遇到了栅栏问题之类的问题。我决定将“中位数”定义为N元素数组中的元素N/2。我的实现总体上是杂乱无章的，而且无法正常工作。
下面是我用来比较我的另一个函数的函数：
template <typename T>
T M2SA_Dumb(std::vector<T> A, std::vector<T> B)
{
if (A.size() == 0 || B.size() == 0)
throw st
浏览 0提问于2014-05-29得票数 0
2回答
我读了所有的解释，这里，但仍然不相信。我认为合并是n*n，我知道我错了，但不确定在哪里。以下是我的想法：
假设我们对8个元素进行排序，这就是算法(假设我对此有正确的想法)：
doSort(int begin, int end, int[] arr) {
if(end != begin) {
int mid = begin + (end - begin)/2;
doSort(begin,mid);
doSort(mid + 1, end);
merge(arr, begin, mid, mid + 1, end);
浏览 0提问于2016-02-18得票数 2
例如，当枢轴是数组中的最高或最低值时。
对于使用2个指针的快速排序，1个指针从左端到右，另一个从右端到左，当指针发现一个元素相对于轴心位置不正确时停止，当两个指针都停止时，它们交换元素并从该位置继续。但是，为什么一个糟糕的枢轴选择会使快速排序成为O(n^2)？
浏览 0提问于2012-12-19得票数 0
1回答
据说，一个特定的分区算法可以导致稳定的快速排序，我想知道需要什么细节才能做到这一点？
如果任何人有创建这样的算法的示例或提示，将是有帮助的
浏览 1提问于2016-03-09得票数 4
1回答
我想知道当从CLRS使用快速排序时，假设轴心总是在n/3位置时，这是不是正确的递归。
我的循环如下所示
浏览 0提问于2016-10-13得票数 3
1回答
我读到过，旋转点可以是3个数字的中位数，底部，中间和顶部。但是，这会产生溢出吗？如果中位数返回的值大于数组大小，会发生什么情况？我假设this的选择是通过假设数组值不能长于数组大小来实现的。我想我对pivote到底是什么感到困惑。
浏览 2提问于2011-06-28得票数 1
回答已采纳
我试着在网上翻看我可爱的课本(没有用)。根据科尔门的书I'm book off，我们将使用数组中的第一个元素作为轴心。我只是不知道该怎么做，因为第一个元素恰好是1。
该数组如下所示：
1、16、2、3、14、5、12、7、10、8、9、17、19、21、23、26、27
同样，书中算法的问题是它选择第一个元素作为轴心。一旦我们将1与所有其他元素进行比较，并发现没有其他元素小于或等于，那么我们将交换枢轴和子数组的中间元素，其中左侧的子数组小于枢轴，右侧的子数组大于枢轴。但是如果我们的轴心是1，那么我们就没有办法交换。真的很困惑，任何帮助都是很好的。这本书的标题是算法导论，第三版，如果有人
浏览 5提问于2013-06-04得票数 3
回答已采纳
所以我知道线性的O(N)是n，插入是n**2，二进制是log(n)，合并是nlogn
因此，合并排序是大型列表的最佳搜索。上面的哪一个是最适合小列表的，比如有多小？谢谢
浏览 1提问于2014-02-19得票数 0
2回答
我试图解决的一个问题，我写了一个脚本：
def is_prime?(num)
(2...num).each do |divisor|
return false if num % divisor == 0
end
true
end
def circular_prime(num)
circular_primes = []
if num < 2
return false
end
(2..num-1).each do |number|
is_prime?(number)
result = [number.to_s]
(0..n
浏览 1提问于2015-08-25得票数 2
回答已采纳
7回答
什么是确定性快速排序？
、、、
我一直在读有关快速排序的文章，发现有时它被称为“确定性快速排序”。
这是普通快速排序的替代版本吗？普通的快速排序和确定性的快速排序有什么区别？
浏览 0提问于2010-02-23得票数 11
回答已采纳
2回答
我想知道我们是否可以以某种方式修改快速排序算法，以产生O(n logn)的最坏情况时间复杂度。虽然这可以通过置换数据来完成，然后假设我们将获得平均情况的复杂性，而不是最坏的情况。但这并不是一个完全证明的解决方案，因为在置换之后，我们可能再次陷入最坏的情况。你有没有其他的办法可以建议。
浏览 0提问于2012-03-02得票数 9
回答已采纳
2回答
这是快速排序算法的一部分代码，但我真的不知道它为什么使用rand() %n，请帮助我谢谢
Swap(V,0,rand() %n) // move pivot elem to V[0]
浏览 0提问于2010-06-08得票数 3
回答已采纳
3回答
我将从一步一步地解释我要做什么。首先，我创建了一个包含N个素数的数组，如下所示：
bool isPrime(int n) {
if(n <= 1) return false;
for(int i = 2; i * i <= n; i++)
if(n % i == 0) return false;
return true;
}
int p[n + d], j = 0;
for(int i = 0; j < n + d; i++) {
if(isPrime(i)) {
p[j] = i;
浏览 8提问于2020-10-23得票数 0
回答已采纳
3回答
我想设计一种算法来确定数组A是否为复数，并返回该元素。
当数组中存在元素x时，如果超过一半的数组与x相同，则该数组是复数。
我想知道是否有更有效的分而治之的算法，比我现在的算法运行得更好。
Assume you have the array
aaabbcac
我将递归地拆分数组，直到得到大小为2的子数组，如下所示。
aa ab bc ac
从这里开始，我将比较子元素中的每个元素，看看它们是否相等:如果相等，则返回元素，否则返回false。
aa ab bc ac
a f f f
所以现在我有了一个元素A和3个false的数组。
我想把它们组合成这样：
a f f f
a
浏览 3提问于2011-03-01得票数 6
回答已采纳
3回答
快速排序和优化的快速排序之间的根本区别是什么？快速排序的改进是什么？Java是如何决定使用这种排序而不是合并排序的？
浏览 2提问于2010-05-06得票数 5
回答已采纳
1回答
Lomuto分区是一种用于快速排序的简单分区算法。Lomuto算法对子数组A[left] ... A[right]进行分区，并假设A[left]是一个枢轴。如何修改此算法以使用给定的pivot P (与A[left]不同)对A[left] ... A[right]进行分区？
浏览 0提问于2010-11-14得票数 1
回答已采纳
1回答
一个测试要求我实现一个排序算法，它对一个数组进行排序，当大小为N>1000时，通过合并排序，否则通过快速排序和透视随机选择。然后假设要比较的关键字由1，M上随机分布的整数组成，M应该是多少才能使上述算法运行得最好？ 如果大小为<=1000，我让Quick Sort处理合并排序的递归调用。在我看来，由于随机键、随机枢轴和Hoare的分区方案不会因为重复的元素而减慢，如果M比N小得多，Quick sort将以最佳状态运行，而Merge sort对于特定的数组大小运行相同，而不管键分布如何，那么M在这里的用途是什么？
浏览 48提问于2020-01-07得票数 1
我有数据(3是轴心)：
281374
我从左边和右边移动两个指针
首先，我有2和4，所以我什么都不交换
然后我有8和7，所以我交换了，并有：
273184
现在我在3和1中有了pinter，所以我交换：
271384
现在left pointer = rightpointer -1，所以我应该快速排序：
271 | 384
分开，对吧？
但如果我这样做了，我会得到这样的结果：
127 | 348
这不是排序数据！
我哪里搞错了？
浏览 1提问于2013-06-24得票数 0
回答已采纳
1回答
我在序列化以下结构时遇到了问题。我已经把范围缩小到，问题在变量objects中，包含了HashMap中的特征结构。我会尽力解释我的情况：
我有以下主要结构，我有兴趣从它获得数据：
#[derive(Serialize)]
pub struct System {
pub objects: HashMap<(u32, u32), Box<dyn CommonObjects>>,
pub paths: Vec<Path>,
pub loops: Vec<Loop>,
pub physics: Physics,
浏览 4提问于2022-09-09得票数 0
回答已采纳
2回答
快速排序实现，找不到错误
、、、、
我想用一些不同的枢轴策略来实现这个快速排序算法，但其中存在一些逻辑错误。你能帮我找一下吗？
#include <iostream.h>
#include<stdlib.h>
#include<stdio.h>
#include<conio.h>
int arr[100],i,pivot,left,right,sum=0,a,n=10;
int partition();
void quickSort(int* ,int ,int );
void main()
{
clrscr();
int i,n=20;
for(i
浏览 0提问于2011-04-13得票数 0
回答已采纳
2回答
给定一个数字数组( a[0], a[1], ..., a[n-1] )，我们将得到以下类型的查询：
输出k-th在范围a[i], a[i+1], ..., a[j]中的最大数字
每个查询能否在多对数时间(以n格式)回答这些查询？如果没有，是否有可能将结果平均，并得到一个很好的摊销复杂度？
编辑：可以使用持久段树来解决这个问题
浏览 0提问于2014-10-10得票数 6
回答已采纳
1回答
递归关系，分析算法
、、、
好吧，我有一些困难，完全理解递归关系。
例如，如果我在最坏的情况下使用Θ表示法分析快速排序，给数组一个未排序正数的输入；
当基本情况为n <= 3时，我使用I对小数组进行排序。时间: O(1)还是O(n^2)？
我使用线性搜索将轴心设置为所有元素的中位数。时间:Θ(n)
对透视的左右进行划分，并进行递归。时间:2* T(n/2)我想
那么递归是否为: T(n) = O(1) +Θ(n) +2* T(n/2)？
有些东西告诉我，基本情况将花费O(n^2)时间，因为如果输入足够小，那将是最坏的情况。那么会不会给出递归公式: T(n) = O(n^2) +Θ(n) +2* T(n/2)？
浏览 0提问于2018-09-08得票数 1
1回答
我是prolog编程的新手。
我希望更改prolog程序返回的值，使其返回true / false，而不是标准的yes或no。
考虑一个非常简单的例子:例如simple.P
node(1).
isNode(X) : node(X)
在prolog命令行中，如果我键入isNode(1)，它将返回yes，如下所示：
isNode(1).
yes
我的问题是：
如何将此从“是”改为“真”？
浏览 3提问于2013-03-03得票数 2
回答已采纳
我只想得到理论上的原因，而不是实验结果。另外，我们如何确定数据大小是小的还是大的？
我没有解释清楚，我的意思是当输入数据的大小很小时，我们通常选择使用插入排序或不使用快速排序，这是正确的。所以我想知道为什么？
浏览 1提问于2013-10-27得票数 3
回答已采纳
3回答
因为最坏情况下的快速排序复杂度为O(n^2)
在升序情况下，当pivot选择第一个或最后一个元素时，它会给出O(n^2)的正确最坏情况复杂度，因为树的一个子元素总是空的
但是当pivot选择了中间时，我会感到困惑吗？它将树一分为二，使其复杂度为O(n.logn)
假设10 20 30 40 50 60 70 pivot=40
(10 20 30 ) 40 (50 60 70)
左侧枢轴20，右侧枢轴60
(10) 20 (30)
(50) 60 (70)
正确吗？
浏览 10提问于2014-07-08得票数 3
给出了一个具有'n‘值的数组(n <= 10^5 )；我们必须计算每个元素的xor，并计算其xor可以写成具有相同奇偶校验的两个素数之和的对。我的代码是：
#include
#include
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int testCases;
cin >> testCases;
for (int i = 0; i < testCases; i++) {
long long n;
cin >> n;
lo
浏览 0提问于2018-09-10得票数 -1
当传递一个简单的比较函数时，我非常努力地“查看”对Array.sort()的调用中发生了什么。我已经走到了这一步，但这些数字似乎从未加起来，我想知道JavaScript是如何得出结论的。也许我漏掉了其中的一些基本点。
var nums = new Array(40,20,230,65);
var b = a.sort(function(a,b){
return a-b;
});
所以，我就这样想出来了：
40-20 = 20 = (>0) so，a或20,40
230-65 = 165 (>0) so b，a或230,65
40-65 = -25 (<0)
浏览 4提问于2011-02-13得票数 0
1回答
首先将所选的pivot元素移动到数组末尾的动机是什么？我能看到的唯一一件事是，当递增较低的索引i时，我们不需要检查i<n，而只需要检查ai < pivot。
是这样吗？
塔克恩斯
安迪
浏览 0提问于2011-03-31得票数 2
回答已采纳
1回答
使用预置间隔的合并
、、、
我试图阻止对mergesort的任何不必要的递归调用，因为我的数组是由部分预置的，例如：
22, 233, 445, 1055, 1, 14, 94, 74545, 75, 134, 323, 9090, 2, 43, 6342, 323452
我使用的是通用的合并实现。
void merge(int a[], int low, int mid, int high)
{
int b[10000];
int i = low, j = mid + 1, k = 0;
while (i <= mid && j <= high) {
浏览 1提问于2014-02-19得票数 6
回答已采纳
我知道算法的最坏情况-当元素已经排序或所有元素都相同时，但想知道算法从nlgn的复杂性移动到n2的点。
浏览 34提问于2014-09-07得票数 -3
2回答
因此，我正在学习QuickSort，并且对运行时间有一点困惑。输入有三种类型:升序、降序和随机序。如果我们从子数组的第一个位置( input )选择pivot，我知道按升序或降序对输入进行排序需要O(n^2)。对随机顺序输入进行排序需要O(nlogn)还是仍然需要O(n^2)时间？
浏览 10提问于2020-11-30得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM活动推荐
腾讯云开发者
