Max*_*axG 2 java sorting algorithm insertion-sort heapsort
我已经实现了Insertion排序和堆排序.理论上,Heap排序具有nlogn时间复杂度,插入具有n ^ 2.为什么,然后我的Insertion实现需要大约6倍的时间来排序100,000个长阵列？
我使用JMH来对每种排序算法的平均时间进行基准测试.这是我的基准代码:
import java.util.concurrent.ThreadLocalRandom;
import java.util.concurrent.TimeUnit;
import java.util.stream.IntStream;
import org.openjdk.jmh.annotations.Benchmark;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
public class MyBenchmark {
// setup the benchmark - create a new array for each iteration
@State(Scope.Thread)
public static class MyState {
int[] array = null;
@Setup(Level.Iteration)
public void doSetup() {
array = createArray(100000, 0, 100);
}
}
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.SECONDS)
public void insertionSort(MyState state) {
int[] array = state.array;
for (int i = 1; i < array.length; i++) {
int element = array[i];
for (int j = i - 1; j >= 0; j--) {
if (element < array[j]) {
int temp = array[j];
array[j] = element;
array[j + 1] = temp;
} else {
break;
}
}
}
}
@Benchmark
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.SECONDS)
public void heapSort(MyState state) {
int[] array = state.array;
sort(array, array.length);
}
public static void sort(int[] arr, int size) {
for (int i = 0; i < size;) {
maxHeapify(size, arr);
int temp = arr[0];
arr[0] = arr[size - 1];
arr[size - 1] = temp;
size--;
}
}
private static void maxHeapify(int size, int[] arr) {
int nonLeafs = size / 2;
for (int i = nonLeafs; i > 0; i--) {
int arrayPos = heapToArrayPos(i), leftChild = heapToArrayPos(leftChild(i)),
rightChild = heapToArrayPos(rightChild(i));
if (rightChild < size) {
if (arr[rightChild] < arr[leftChild]) {
if (arr[arrayPos] < arr[leftChild]) {
switchWithLeftChild(arrayPos, arr);
}
} else if (arr[arrayPos] < arr[rightChild]) {
switchWithRightChild(arrayPos, arr);
}
} else if (arr[arrayPos] < arr[leftChild]) {
switchWithLeftChild(arrayPos, arr);
}
}
}
private static int heapToArrayPos(int heap) {
return heap - 1;
}
private static int rightChild(int pos) {
return pos * 2 + 1;
}
private static int leftChild(int pos) {
return pos * 2;
}
private static void switchWithRightChild(int pos, int[] arr) {
int father = arr[pos];
int childPos = heapToArrayPos(rightChild(pos + 1)), child = arr[childPos];
arr[childPos] = father;
arr[pos] = child;
}
private static void switchWithLeftChild(int pos, int[] arr) {
int father = arr[pos];
int childPos = heapToArrayPos(leftChild(pos + 1)), child = arr[childPos];
arr[childPos] = father;
arr[pos] = child;
}
public static void main(String[] args) throws RunnerException {
Options opt = new OptionsBuilder().include(MyBenchmark.class.getSimpleName()).forks(1).build();
new Runner(opt).run();
}
public static int[] createArray(int length, int minValue, int maxValue) {
return IntStream.generate(() -> ThreadLocalRandom.current().nextInt(minValue, maxValue)).limit(length)
.toArray();
}
public static int[] createArray(int length) {
return createArray(length, 0, 10);
}
public static int[] createArray(int minValue, int maxValue) {
return createArray(10, minValue, maxValue);
}
}
以下是基准测试输出:
JMH 1.12(51天前发布)VM版本:JDK 1.8.0_65,VM 25.65-b01 VM调用程序:C:\ Program Files\Java\jdk1.8.0_65\jre\bin\java.exe VM选项:-Dfile.encoding = UTF-8 -Xbootclasspath:C:\ Program Files\Java\jdk1.8.0_65\jre\lib\resources.jar; C:\ Program Files\Java\jdk1.8.0_65\jre\lib\rt.jar; C :\ Program Files\Java\jdk1.8.0_65\jre\lib\jsse.jar; C:\ Program Files\Java\jdk1.8.0_65\jre\lib\jce.jar; C:\ Program Files\Java\jdk1 .8.0_65\jre\lib\charsets.jar; C:\ Program Files\Java\jdk1.8.0_65\jre\lib\jfr.jar; C:\ Program Files\Java\jdk1.8.0_65\lib\tools. jar
预热:20次迭代,每次1次
测量:20次迭代,每次1次
超时:每次迭代10次
线程:1次线程,将同步迭代
基准模式:平均时间,时间/操作
基准测试:org.sample.MyBenchmark.heapSort运行进度:0.00%完成,ETA 00:01:20
Fork:1 of 1
预热迭代1:17.651 s/op
预热迭代2:16.004 s/op
预热迭代3:14.640 s/op
预热迭代4:14.699 s/op
预热迭代5:14.836 s/op
预热迭代6:14.900 s/op
预热迭代7:14.758 s/op
预热迭代8:15.084 s/op
预热迭代9:15.652 s/op
预热迭代10:15.121 s/op
预热迭代11:15.315 s/op Warmup
Iteration 12:15.299 s/op Warmup
Iteration 13:15.234 s/op Warmup
Iteration 14:14.822 s/op
Warmup Iteration 15:15.078 s/op Warmup
Iteration 16:15.565 s/op
Warmup Iteration 17: 15.509 s/op
预热迭代18:15.189 s/op
预热迭代19:14.748 s/op
预热迭代20:14.902 s/op
迭代1:14.888 s/op
迭代2:15.381 s/op
迭代3:16.099 s/op
迭代4:15.536 s/op
Iteration 5:15.635 s/op
Iteration 6:16.446 s/op
Iteration 7:16.034 s/op
Iteration 8:15.828 s/op
Iteration 9:15.666 s/op
Iteration 10:16.071 s/op
Iteration 11 :15.962 s/op
迭代12:15
.777 s/op Iteration 13:15.757 s/op
Iteration 14:15.424 s/op
Iteration 15:15.449 s/op
Iteration 16:15.920 s/op
Iteration 17:14.609 s/op
Iteration 18:14.651 s/op
Iteration 19: 14.661 s/op
Iteration 20:14.607 s/op结果"heapSort":15.520±(99.9%)0.486 s/op [平均](min,avg,max)=(14.607,15.520,16.446),stdev = 0.560 CI(99.9%):[15.034,16.006](假设正态分布)
JMH 1.12(51天前发布)VM版本:JDK 1.8.0_65,VM 25.65-b01 VM调用程序:C:\ Program Files\Java\jdk1.8.0_65\jre\bin\java.exe VM选项:-Dfile.encoding = UTF-8 -Xbootclasspath:C:\ Program Files\Java\jdk1.8.0_65\jre\lib\resources.jar; C:\ Program Files\Java\jdk1.8.0_65\jre\lib\rt.jar; C :\ Program Files\Java\jdk1.8.0_65\jre\lib\jsse.jar; C:\ Program Files\Java\jdk1.8.0_65\jre\lib\jce.jar; C:\ Program Files\Java\jdk1 .8.0_65\jre\lib\charsets.jar; C:\ Program Files\Java\jdk1.8.0_65\jre\lib\jfr.jar; C:\ Program Files\Java\jdk1.8.0_65\lib\tools. jar预热:20次迭代,每次1次测量:20次迭代,每次1次超时:每次迭代10次线程:1次线程,将同步迭代基准模式:平均时间,时间/操作基准:org.sample.MyBenchmark.insertionSort
运行进度:50.00%完成,ETA 00:10:15分叉:1个1预热迭代1:1.726 s/op预热迭代2:1.636 s/op预热迭代3:1.968 s/op预热迭代4:1.970 s/op预热迭代5:1.961 s/op预热迭代6:1.966 s/op预热迭代7:1.962 s/op预热迭代8:1.961 s/op预热迭代9:1.959 s/op预热迭代10:1.965 s/op预热迭代11:1.966 s/op Warmup Iteration 12:1.970 s/op Warmup Iteration 13:1.964 s/op Warmup Iteration 14:1.952 s/op Warmup Iteration 15:1.955 s/op Warmup Iteration 16:1.956 s/op Warmup Iteration 17: 1.972 s/op预热迭代18:1.966 s/op预热迭代19:1.954 s/op预热迭代20:1.956 s/op
迭代1:1.969 s/op
迭代2:1.963 s/op
迭代3:2.050 s/op
迭代4:2.019 s/op Iteration 5:1.934 s/op
Iteration 6:1.953 s/op
Iteration 7:1.961 s/op
Iteration 8:1.972 s/op
Iteration 9:1.957 s/op
Iteration 10:1.956 s/op
Iteration 11 :1.975 s/op
Iteration 12:1.950 s/op
Iteration 13:1.965 s/op
Iteration 14:1.961 s/op
Iteration 15:1.950 s/op
Iteration 16:1.956 s/op
Iteration 17:1.975 s/op
Iteration 18:1.966 s/op
Iteration 19:1.959 s/op
Iteration 20:1.965 s /运结果"insertionSort":
1.968±(99.9%)0.022 s/op [平均](min,avg,max)=(1.934,1.968,2.050),stdev = 0.025 CI(99.9%):[1.946,1.990](假设正态分布)运行完成.总时间:00:09:55
基准模式Cnt评分误差单位
MyBenchmark.heapSort avgt 20 12.692±0.282 s/op
MyBenchmark.insertionSort avgt 20 2.024±0.020 s/op
编辑:由于我发布了问题,我在基准测试之前添加了@setup来设置数组,因此数组创建操作不会是一个因素.我再次运行基准测试,插入排序的结果几乎相同.堆平基准在平均上升3秒.我只发布了结果的更新摘要.
您的堆排序未正确实现.您发布的代码似乎在进行选择排序.也就是说,对于它调用的每个项目maxHeapify,获取堆中的第一个项目,将其放在最后,并减少计数.因此maxHeapify被称为size时间,每次都有减小的大小.最终内部循环的迭代次数maxHeapify就像是(n^2)/4.
您已经实现了具有复杂度O(n ^ 2)的美化选择排序.
执行就地堆排序的技巧是首先构建堆 - 一次 - 然后重新排列它以进行排序.你打了maxHeapify一次电话:
maxHeapify(size, arr);
完成后,你有一个有效的最大堆,最大的项目在arr[0]等等.这需要O(n)时间.
你想要的是一个按升序排列的数组.为此,您构建一个循环,从堆中复制最大项(即arr[0])并临时保存.然后,取出堆中的最后一项,将计数减一,然后将该项重新插入顶部,根据需要对其进行筛选.最后,将前一个最大项目放在先前由最后一个项目占据的位置.当count变为0时,你有一个排序数组:
int count = size;
while (count > 0)
{
int save = arr[0]; // save the largest item
arr[0] = arr[count-1]; // move last item to top
arr[count-1] = save; // and place the largest item
count = count - 1; // reduce the count
SiftDown(0); // sift item into place
}
你所做的就是先后调用removeMax堆,然后将结果存回到空出位置的数组中.
SiftDown 与将项目插入堆中时使用的方法相同.
有关使用O(n)heapify方法构建堆的完整示例,请参阅我的博客文章A Simple Heap of Integers.它在C#中,但我觉得很简单,如果你理解Java就可以理解它.我没有展示如何进行排序部分,但是使用上面的代码和几行,你应该做得很好.