这是一个快速排序的变化,其中-在枢轴选择是基于计算值的平均值的最高和最低的数字。
pivot = (high + low)/2这样的枢轴通常是虚拟的。
这种方法对每个迭代执行一次传递,以确定<>高和低值。
我的理解是,这种方法需要最大限度的2 \cdot n \cdot \log_2(n)。
理由如下:
最好的情况是数字是排序的并且是顺序的。
例子: 1,2,3,4,5,6,7,8。
第一次运行将生成\frac{1+8}{2}=4.5,这反过来可以四舍五入为4;第二次运行将生成左子数组的\frac{1+4}{2}=2.5,右侧子数组的\frac{5+8}{2}=6.5,等等。
对上述情况来说,最坏的情况将是一个加倍的序列。实际上是2的幂序列。
例:1,2,4,8,16,32,64,128,256,512
但是,考虑到对于给定的数据类型(例如:整数),数字通常表示为字节(8)、短(16)、int (32)、长(64),最坏情况下的最大数将是: 2,147,483,648。基本上,对于一个整数数据类型,序列- 1,2,4,8,16,.,在30步之后,序列必须重复,最多达到2,147,483,648。
为了用字节(无符号)来说明相同的情况,序列如下所示:
1,2,4,8,16,32,64,128,256,1,2,4,8,16,32,64,128,256,1,2,4,8,16,32,64,128,256,...
仅仅因为字节不能容纳超过256 (无符号)。
因此,在最坏的情况下输入,方法:(high+low)/2仍然只需要处理深度的log_2 n,因为数字会重复。
虽然与数据类型本身相比,上面列出的数组中的元素数量不多.例如:在总容量的10%中,对于具有与数据类型所支持的最大值相当的大小的数据集,这种方法仍有可能对给定的数据集产生最坏的情况。
不太清楚的是:
假设最好的情况是在\mathcal{O}(n \cdot \log_2(n))中,而在最坏的情况下,对于大小与最大值相当的数据集,这些场景似乎也是n \cdot \log_2(n),对于一般情况场景也是这样吗?
据我所知,这是真的,因此整个方法都是在\mathcal{O}(n \cdot \log_2(n))中。
然而,我需要确认的方法,理解和结论。
package org.example.so.sorts.qs;
//import java.util.Arrays;
import java.util.Random;
/**
*
*
* Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*
*
*
* Simple Averaged Virtual Pivot - Quick Sort
*
*
*
* Unstable, In-place, Big-O-Notation Classification : n*log(n)
*
*
*
* A variation of quick sort where the pivot is calculated using simple average
* of highest and lowest values.
*
*
*
*
* @author Ravindra HV
* @version 0.2.1
* @since 2013
*/
public class QSortSAVP {
/*
* The pivot calculation works only for numbers with the same sign. As such,
* first step is to partition positive and negative numbers, thus preventing
* arithmetic overflow
*/
private static final int INITIAL_PIVOT = 0;
private static volatile int RECURSION_COUNT = 0;
private static volatile int MAX_RECURSION_DEPTH = 0;
private static volatile int RECURSION_DEPTH = 0;
private static final int[] POWERS_OF_TWO = { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384,
32768, 65536 };
public static void main(String[] args) {
// int[] arr = {0,4,2,6,-1,-5,-3,-7};
// int[] arr = {0,4,2,6,-1,-5,-3,-7,35,41,2,6,-34,76};
// int[] arr = {1,2,4,8,16,32,64,128,256,512};
// int[] arr = {1024,32,64,1,2,4,8,16,128,256,512};
// int[] arr = {-256,-512,-1,-2,-4,-8,-16,-32,-64,-128,};
// int[] arr =
// {1,2,4,8,16,32,64,128,256,512,1,2,4,8,16,32,64,128,256,512,1,2,4,8,16,32,64,128,256,512,1,2,4,8,16,32,64,128,256,512,1,2,4,8,16,32,64,128,256,512,1,2,4,8,16,32,64,128,256,512,1,2,4,8,16,32,64,128,256,512,1,2,4,8,16,32,64,128,256,512,1,2,4,8,16,32,64,128,256,512,1,2,4,8,16,32,64,128,256,512};
// int[] arr =
// {-2,1,1,1,1,1,-1,-1,-1,-1,-1,0,0,0,0,0,-1,-1,-1,-1,-1,0,0,0,0,0,1,1,1,1,1,2};
int[] arr = new int[1024 * 1024];
Random random = new Random();
for (int i = 0; i < arr.length; i++) {
arr[i] = random.nextInt(arr.length);
// arr[i] = i;
// arr[i] = arr.length-i;
// arr[i] = arr[i] % 1024;
// int j = i % POWERS_OF_TWO.length;
// arr[i] = POWERS_OF_TWO[j];
// if( i % 2 == 0) {
// arr[i] = arr.length-i;
// }
// else {
// arr[i] = random.nextInt(arr.length);
// }
}
/* */
// handlePrintLine(Arrays.toString(arr));
long start = System.currentTimeMillis();
sort(arr);
// Arrays.sort(arr);
long end = System.currentTimeMillis();
System.out.println("Time taken : " + (end - start) + "... Recursion count :" + RECURSION_COUNT+", Recursion-Depth :"+RECURSION_DEPTH+", MaxRecursionDepth :"+MAX_RECURSION_DEPTH);
// handlePrintLine(Arrays.toString(arr));
validate(arr);
// handlePrintLine("Recursion count : "+RECURSION_COUNT );
}
/**
* Sorts the given array in ascending order
*
* @param arr
*/
public static void sort(int[] arr) {
if (arr.length < 2) {
return;
}
sort(arr, INITIAL_PIVOT, 0, arr.length, true);
}
/**
* @param arr
* @param createCopy
* (to ensure correctness in the event of concurrent modification of
* given array)
* @return
*/
public static int[] sort(int[] arr, boolean createCopy) {
int[] resArr = null;
if (createCopy) {
int[] tempArr = new int[arr.length];
System.arraycopy(arr, 0, tempArr, 0, tempArr.length);
sort(tempArr);
resArr = tempArr;
} else {
sort(arr);
resArr = arr;
}
return resArr;
}
private static void sort(int[] arr, int pivotVal, int lowIndex, int highIndex, boolean firstIteration) {
RECURSION_COUNT++;
// handlePrintLine("First Print Statement");
// handlePrintLine("Low-Index : "+lowIndex);
// handlePrintLine("High-Index : "+highIndex);
// print(arr, lowIndex, highIndex);
// handlePrintLine("Pivot : "+pivotVal);
int tempLowIndex = lowIndex;
int tempHighIndex = highIndex;
while (tempLowIndex < tempHighIndex) {
while ((tempLowIndex < highIndex) && (arr[tempLowIndex] <= pivotVal)) {
tempLowIndex++;
}
if (!firstIteration && tempLowIndex == highIndex) {
// handlePrintLine("Returning...");
return; // all entries in given range are less than or equal to pivot..
}
while ((tempHighIndex > tempLowIndex) && (arr[tempHighIndex - 1] > pivotVal)) {
tempHighIndex--;
}
if (tempLowIndex < tempHighIndex) {
swap(arr, tempLowIndex, tempHighIndex - 1);
tempLowIndex++;
tempHighIndex--;
}
}
// handlePrintLine("Final-Low-Index : "+tempLowIndex);
// handlePrintLine("Final-High-Index : "+tempHighIndex);
// handlePrintLine("Second Print Statement");
// print(arr, lowIndex, highIndex);
if ((tempLowIndex - lowIndex) > 1) {
int leftPartPivotVal = determinePivot(arr, lowIndex, tempLowIndex);
RECURSION_DEPTH++;
MAX_RECURSION_DEPTH = (RECURSION_DEPTH>MAX_RECURSION_DEPTH) ? RECURSION_DEPTH:MAX_RECURSION_DEPTH;
sort(arr, leftPartPivotVal, lowIndex, tempLowIndex, false);
RECURSION_DEPTH--;
}
if ((highIndex - tempLowIndex) > 1) {
int rightPartPivotVal = determinePivot(arr, tempLowIndex, highIndex);
RECURSION_DEPTH++;
MAX_RECURSION_DEPTH = (RECURSION_DEPTH>MAX_RECURSION_DEPTH) ? RECURSION_DEPTH:MAX_RECURSION_DEPTH;
sort(arr, rightPartPivotVal, tempLowIndex, highIndex, false);
RECURSION_DEPTH--;
}
}
/**
*
* Pivot is calculated as the simple average of the highest and lowest elements,
* while ensuring that there is no overflow.
*
*
* @param arr
* @param lowIndex
* @param highIndex
* @return
*/
private static int determinePivot(int[] arr, int lowIndex, int highIndex) {
int pivotVal = 0;
int lowVal = arr[lowIndex];
int highVal = lowVal;
for (int i = lowIndex; i < highIndex; i++) {
if (arr[i] < lowVal) {
lowVal = arr[i];
}
if (arr[i] > highVal) {
highVal = arr[i];
}
}
pivotVal = lowVal + ((highVal - lowVal) / 2);
// pivotVal = lowVal+((highVal-lowVal)>>1);
return pivotVal;
}
private static void swap(int[] arr, int lowIndex, int highIndex) {
int tempVal = arr[lowIndex];
arr[lowIndex] = arr[highIndex];
arr[highIndex] = tempVal;
}
private static void print(int[] arr, int lowIndex, int highIndex) {
for (int i = lowIndex; i < highIndex; i++) {
if (i == 0) {
handlePrint(arr[i]);
} else {
handlePrint(" " + arr[i]);
}
}
handlePrintLine("");
}
private static void validate(int[] arr) {
boolean sorted = true;
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
sorted = false;
break;
}
}
if (sorted) {
handlePrintLine("SUCCESS : ARRAY SORTED. Length : " + arr.length);
} else {
handlePrintLine("ERROR : ARRAY NOT SORTED. Length : " + arr.length);
}
}
private static void handlePrint(Object object) {
System.out.print(object.toString());
}
private static void handlePrintLine(Object object) {
System.out.println(object.toString());
}
}基本上,目标是确定它是否可与java在其Arrays.sort()实现中使用的三种方法的中位数相媲美。
在我运行的测试用例中,它似乎与三种算法的中位数所花费的时间相当--甚至对于随机数据集也是如此。所以,我想知道这个概念是否也很好,或者仅仅是偶然的,并且有一个数据集,其中3的中间值比这个方法更好。
发布于 2018-12-28 19:07:35
发布于 2018-11-15 13:43:49
the goal is to determine whether [pivot selection as average of extrema] is comparable to median-of-three --这可能是说这里介绍的枢轴选择与MoT相比是怎样的?如果这是这篇文章的目标,而不是代码的目标,那么CR是错误的论坛。(这些初步的说明完成后,我将或多或少地跟随源自上而下。)
个人不喜欢: 代码,乍一看我不知道, a)是什么想法创造它 b),我可以用它做什么道德。 - -浪费屏幕空间 (即。在这里,我建议将许可证信息从文档注释中删除,使用空行将不(仅在视觉上)分隔的东西分隔开来,并且尽可能少地使用标记,尽可能少地侵入(例如,段落最后一行的
)。
我忽略了关于政务司司长. 的描述--您对 的发现--如何比较快速排序枢纽选择方案( )--您提出的方案如何与以前的工作-- (这将有助于在 .提出类似的问题) - -这段代码的存在理由(是的,我是在说源代码)。外部文档确实是分开的。如果有几年的可访问性希望,我可以使用超链接。我不想用我的技能在网上找到东西。)
class QSortSAVP (第二S代表什么?)考虑将递归处理、枢轴选择(完成)、分区和“驱动程序”分离(main()看起来是类型--我更喜欢单独的/嵌套类)。实现一个interface Sorter。As such, first step is…这个评论是最新的吗?( arithmetic overflow将在哪里成为一个问题?参见determinePivot()的S文档注释。您应该能够摆脱firstIteration的(当前)特例。)[] sort([], boolean createCopy)看起来太过了。我更喜欢在sort([] arr)的S文档注释(特别是如果返回了它的论点)或[] sortCopy([])中提到一个副本的情况。sort([] arr, pivotVal, int lowIndex, int highIndex, …) -侵入性跟踪阻碍了可读性。如果需要,请使用适当的包。-我不太明白// all entries in given range are less than or equal to pivot (可以想象它们是这样的)-- return;是正确的,因为determinePivot()__never是合适的(我在任何地方都没有找到文档),而且所有条目都是相等的--没有传递(以某种方便的方式)关于在调用该方法和int determinePivot([] arr, int lowIndex, int highIndex)之间选择枢轴的信息:从lowIndex到highIndex的总体低点将保持在从lowIndex到tempLowIndex的低位,类似于高。-如果有的话,只需处理(MAX_)RECURSION_DEPTH就可以处理RECURSION_COUNT --在此方法顶部而不是在每次递归调用之前确定支点void handlePrint(object)和…Line()参见关于日志/跟踪包的建议https://codereview.stackexchange.com/questions/207266
复制相似问题