问题：
这是一种新的排序算法吗？“用Java和伪码实现”
郁博学
我知道这可能是一个愚蠢的问题，也许是今天最愚蠢的问题，但我不得不问它：这个排序算法是我发明的吗？
昨天，关于一个基于交换的排序算法，我有一点灵感。今天，我实施了它，而且奏效了。
它可能已经存在了，因为有许多不那么流行的排序算法，对它们的信息很少或根本没有，而且几乎没有实现。
描述：基本上，这个算法采取一个项目，他们一对，然后一个项目再次...直到名单的末尾。对于每个项/对，在距离对空间或项相同半径距离的每两个项进行比较，直到到达数组的边框，然后在需要时交换这些项。对列表中的每个对/项重复此操作。
一种基于英语的伪代码：
FOR i index to last index of Array (starting from 0)
L index is i - 1
R index is i + 1
//Odd case, where i is the center
WHILE (L is in array range and R is in array range)
IF item Array[L] is greater than Array[R]
EXCHANGE item Array[L] with Array[R]
END-IF
ADD 1 to R
REST 1 to L
END-WHILE
//Even case, where i is not the center
L index is now i
R index in now i + 1
WHILE (L is in array range and R is in array range)
IF item Array[L] is greater than Array[R]
EXCHANGE Array[L] with Array[R]
END-IF
ADD 1 to R
REST 1 to L
END-WHILE
END FOR
这是在Java的实施情况：
//package sorting;
public class OrbitSort {
public static void main(String[] args) {
int[] numbers ={ 15, 8, 6, 3, 11, 1, 2, 0, 14, 13, 7, 9, 4, 10, 5, 12 };
System.out.println("Original list:");
display(numbers);
sort(numbers);
System.out.println("\nSorted list:");
display(numbers);
}
//Sorting algorithm
public static void sort(int[] array) {
for(int i = 0; i < array.length; i++){
int L = i - 1;
int R = i + 1;
//Odd case (with a central item)
while(L >= 0 && R < array.length){
if(array[L] > array[R])
swap(array, L, R);
L--;
R++;
}
//Even case (with no central item)
L = i;
R = i + 1;
while(L >= 0 && R < array.length) {
if(array[L] > array[R])
swap(array, L, R);
L--;
R++;
}
}
}
//Swap two items in array.
public static void swap(int[] array, int x, int y) {
int temp = array[x];
array[x] = array[y];
array[y] = temp;
}
//Display items
public static void display(int[] numbers){
for(int i: numbers)
System.out.print(" " + i);
System.out.println();
}
}
我知道可以更短，但这只是一个早期的实现。
它可能运行在O(n^2)，但我不确定。
那么，你觉得呢？它已经存在了吗？
共有1个答案
毕浩渺
对我来说，它看起来像是一个修改过的气泡排序algo，对于输入元素的某些排列可能表现得更好。虽然不一定公平，但我使用您的输入数组对预热周期做了一个基准测试，以比较：
- java.util.arrays.sort()，这是一个 <罢工> 合并 快速排序实现
- bubblesort.sort()，冒泡排序ALGO的Java实现
- orbitsort.sort()，您的ALGO
结果：
input size: 8192
warmup iterations: 32
Arrays.sort()
iterations : 10000
total time : 4940.0ms
avg time : 0.494ms
BubbleSort.sort()
iterations : 100
total time : 8360.0ms
avg time : 83.6ms
OrbitSort.sort()
iterations : 100
total time : 8820.0ms
avg time : 88.2ms
当然，性能取决于输入大小和排列
简单的代码：
package com.sam.tests;
import java.math.BigDecimal;
import java.math.RoundingMode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Random;
import java.util.concurrent.Callable;
public class SortBenchmark {
public static class OrbitSort {
// Sorting algorithm
public static void sort(int[] array) {
for (int i = 0; i < array.length; i++) {
int L = i - 1;
int R = i + 1;
// Odd case (with a central item)
while (L >= 0 && R < array.length) {
if (array[L] > array[R])
swap(array, L, R);
L--;
R++;
}
// Even case (with no central item)
L = i;
R = i + 1;
while (L >= 0 && R < array.length) {
if (array[L] > array[R])
swap(array, L, R);
L--;
R++;
}
}
}
// Swap two items in array.
public static void swap(int[] array, int x, int y) {
int temp = array[x];
array[x] = array[y];
array[y] = temp;
}
}
public static class BubbleSort {
public static void sort(int[] numbers) {
boolean swapped = true;
for (int i = numbers.length - 1; i > 0 && swapped; i--) {
swapped = false;
for (int j = 0; j < i; j++) {
if (numbers[j] > numbers[j + 1]) {
int temp = numbers[j];
numbers[j] = numbers[j + 1];
numbers[j + 1] = temp;
swapped = true;
}
}
}
}
}
public static class TestDataFactory {
public static enum ElementOrder {
Ascending, Descending, Random
}
public static int[] createIntArray(final int size, final ElementOrder elementOrder) {
int[] array = new int[size];
switch (elementOrder) {
case Ascending:
for (int i = 0; i < size; ++i)
array[i] = i;
break;
case Descending:
for (int i = 0; i < size; ++i)
array[i] = size - i - 1;
break;
case Random:
default:
Random rg = new Random(System.nanoTime());
for (int i = 0; i < size; ++i)
array[i] = rg.nextInt(size);
break;
}
return array;
}
}
public static class Benchmark {
// misc constants
public static final int NANOS_PER_MSEC = 1000000;
// config constants
public static final int BIGDECIMAL_PRECISION = 6;
// constant defaults
public static final long AUTOTUNING_MIN_ITERATIONS_DEFAULT = 1;
public static final long AUTOTUNING_MIN_DURATION_DEFAULT = 125;
public static final long BENCHMARK_MIN_ITERATIONS_DEFAULT = 1;
public static final long BENCHMARK_MAX_ITERATIONS_DEFAULT = Integer.MAX_VALUE;
public static final long BENCHMARK_TARGET_DURATION_DEFAULT = 125;
// private static final ThreadMXBean threadBean =
// ManagementFactory.getThreadMXBean();
public static final long getNanoTime() {
// return threadBean.getCurrentThreadCpuTime();// not good, runs at
// some time slice resolution
return System.nanoTime();
}
public static class Result {
public String name;
public long iterations;
public long totalTime; // nanoseconds
public Result(String name, long iterations, long startTime, long endTime) {
this.name = name;
this.iterations = iterations;
this.totalTime = endTime - startTime;
}
@Override
public String toString() {
final double totalTimeMSecs = ((double) totalTime) / NANOS_PER_MSEC;
final BigDecimal avgTimeMsecs = new BigDecimal(this.totalTime).divide(new BigDecimal(this.iterations).multiply(new BigDecimal(NANOS_PER_MSEC)),
BIGDECIMAL_PRECISION, RoundingMode.HALF_UP);
final String newLine = System.getProperty("line.separator");
StringBuilder sb = new StringBuilder();
sb.append(name).append(newLine);
sb.append(" ").append("iterations : ").append(iterations).append(newLine);
sb.append(" ").append("total time : ").append(totalTimeMSecs).append(" ms").append(newLine);
sb.append(" ").append("avg time : ").append(avgTimeMsecs).append(" ms").append(newLine);
return sb.toString();
}
}
public static <T> Result executionTime(final String name, final long iterations, final long warmupIterations, final Callable<T> test) throws Exception {
// vars
@SuppressWarnings("unused")
T ret;
long startTime;
long endTime;
// warmup
for (long i = 0; i < warmupIterations; ++i)
ret = test.call();
// actual benchmark iterations
{
startTime = getNanoTime();
for (long i = 0; i < iterations; ++i)
ret = test.call();
endTime = getNanoTime();
}
// return result
return new Result(name, iterations, startTime, endTime);
}
/**
* Auto tuned execution time measurement for test callbacks with steady
* execution time
*
* @param name
* @param test
* @return
* @throws Exception
*/
public static <T> Result executionTimeAutotuned(final String name, final Callable<T> test) throws Exception {
final long autoTuningMinIterations = AUTOTUNING_MIN_ITERATIONS_DEFAULT;
final long autoTuningMinDuration = AUTOTUNING_MIN_DURATION_DEFAULT;
final long benchmarkTargetDuration = BENCHMARK_TARGET_DURATION_DEFAULT;
final long benchmarkMinIterations = BENCHMARK_MIN_ITERATIONS_DEFAULT;
final long benchmarkMaxIterations = BENCHMARK_MAX_ITERATIONS_DEFAULT;
// vars
@SuppressWarnings("unused")
T ret;
final int prevThreadPriority;
long warmupIterations = 0;
long autoTuningDuration = 0;
long iterations = benchmarkMinIterations;
long startTime;
long endTime;
// store current thread priority and set it to max
prevThreadPriority = Thread.currentThread().getPriority();
Thread.currentThread().setPriority(Thread.MAX_PRIORITY);
// warmup and iteration count tuning
{
final long autoTuningMinTimeNanos = autoTuningMinDuration * NANOS_PER_MSEC;
long autoTuningConsecutiveLoops = 1;
double avgExecutionTime = 0;
do {
{
startTime = getNanoTime();
for (long i = 0; i < autoTuningConsecutiveLoops; ++i, ++warmupIterations) {
ret = test.call();
}
endTime = getNanoTime();
autoTuningDuration += (endTime - startTime);
}
avgExecutionTime = ((double) autoTuningDuration) / ((double) (warmupIterations));
if ((autoTuningDuration >= autoTuningMinTimeNanos) && (warmupIterations >= autoTuningMinIterations)) {
break;
} else {
final double remainingAutotuningIterations = ((double) (autoTuningMinTimeNanos - autoTuningDuration)) / avgExecutionTime;
autoTuningConsecutiveLoops = Math.max(1, Math.min(Integer.MAX_VALUE, (long) Math.ceil(remainingAutotuningIterations)));
}
} while (warmupIterations < Integer.MAX_VALUE);
final double requiredIterations = ((double) benchmarkTargetDuration * NANOS_PER_MSEC) / avgExecutionTime;
iterations = Math.max(1, Math.min(benchmarkMaxIterations, (long) Math.ceil(requiredIterations)));
}
// actual benchmark iterations
{
startTime = getNanoTime();
for (long i = 0; i < iterations; ++i)
ret = test.call();
endTime = getNanoTime();
}
// restore previous thread priority
Thread.currentThread().setPriority(prevThreadPriority);
// return result
return new Result(name, iterations, startTime, endTime);
}
}
public static void executeBenchmark(int inputSize, ArrayList<Benchmark.Result> results) {
// final int[] inputArray = { 15, 8, 6, 3, 11, 1, 2, 0, 14, 13, 7, 9, 4,
// 10, 5, 12 };
final int[] inputArray = TestDataFactory.createIntArray(inputSize, TestDataFactory.ElementOrder.Random);
try {
// compare against Arrays.sort()
{
final int[] ref = inputArray.clone();
Arrays.sort(ref);
{
int[] temp = inputArray.clone();
BubbleSort.sort(temp);
if (!Arrays.equals(temp, ref))
throw new Exception("BubbleSort.sort() failed");
}
{
int[] temp = inputArray.clone();
OrbitSort.sort(temp);
if (!Arrays.equals(temp, ref))
throw new Exception("OrbitSort.sort() failed");
}
}
results.add(Benchmark.executionTimeAutotuned("Arrays.sort()", new Callable<Void>() {
@Override
public Void call() throws Exception {
int[] temp = Arrays.copyOf(inputArray, inputArray.length);
Arrays.sort(temp);
return null;
}
}));
results.add(Benchmark.executionTimeAutotuned("BubbleSort.sort()", new Callable<Void>() {
@Override
public Void call() throws Exception {
int[] temp = Arrays.copyOf(inputArray, inputArray.length);
BubbleSort.sort(temp);
return null;
}
}));
results.add(Benchmark.executionTimeAutotuned("OrbitSort.sort()", new Callable<Void>() {
@Override
public Void call() throws Exception {
int[] temp = Arrays.copyOf(inputArray, inputArray.length);
OrbitSort.sort(temp);
return null;
}
}));
} catch (Exception e) {
e.printStackTrace();
}
}
public static void main(String[] args) {
ArrayList<Benchmark.Result> results = new ArrayList<Benchmark.Result>();
for (int i = 16; i <= 16384; i <<= 1) {
results.clear();
executeBenchmark(i, results);
System.out.println("input size : " + i);
System.out.println("");
for (Benchmark.Result result : results) {
System.out.print(result.toString());
}
System.out.println("----------------------------------------------------");
}
}
}
类似资料：
-
本文向大家介绍详细总结各种排序算法(Java实现)，包括了详细总结各种排序算法(Java实现)的使用技巧和注意事项，需要的朋友参考一下 一、插入类排序 1.直接插入排序 思想：将第i个插入到前i-1个中的适当位置 时间复杂度：T(n) = O(n²)。 空间复杂度：S(n) = O(1)。 稳定性：稳定排序。 如果碰见一个和插入元素相等的，那么插入元素把想插入的元素放在相等元素的后面。 所以，相等
-
本文向大家介绍Python实现各种排序算法的代码示例总结，包括了Python实现各种排序算法的代码示例总结的使用技巧和注意事项，需要的朋友参考一下 在Python实践中，我们往往遇到排序问题，比如在对搜索结果打分的排序（没有排序就没有Google等搜索引擎的存在），当然，这样的例子数不胜数。《数据结构》也会花大量篇幅讲解排序。之前一段时间，由于需要，我复习了一下排序算法，并用Python实现了各种
-
本文向大家介绍js的各种排序算法实现(总结)，包括了js的各种排序算法实现(总结)的使用技巧和注意事项，需要的朋友参考一下 如下所示： 以上这篇js的各种排序算法实现(总结)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持呐喊教程。
-
本文向大家介绍Ruby实现的3种快速排序算法，包括了Ruby实现的3种快速排序算法的使用技巧和注意事项，需要的朋友参考一下 刚学Ruby，正巧算法老师鼓励用不熟悉的语言来写算法，我就用Ruby吧~~ 话说Ruby可真是超厉害，好多凭直觉的方法都可以用。。。。。无限膜拜中。。。。 期间我遇到了invalid multibyte char (US-ASCII)的错误，解决办法是在开头加一个#encod
-
我在上一门叫做算法的基础课。我们正在研究排序算法；我们得到了以下伪代码作为插入排序算法的示例。然而我认为这是错误的。 我理解第一行——它从2开始，因为第一张卡是“已经订购的”，因为它是迄今为止唯一的一张卡。 第二行是错误的吗？我们怎么能从i到2使用j呢？当然，这在未来不可能成立。另外，断裂处是否应该减少凹痕？所以只有一个标签而不是两个？ 编辑 Edit2所以在这里，我试着写我脑海中发生的事情，阅读
-
本文向大家介绍java实现折半排序算法，包括了java实现折半排序算法的使用技巧和注意事项，需要的朋友参考一下 折半插入排序（binary insertion sort）是对插入排序算法的一种改进，由于排序算法过程中，就是不断的依次将元素插入前面已排好序的序列中。由于前半部分为已排好序的数列，这样我们不用按顺序依次寻找插入点，可以采用折半查找的方法来加快寻找插入点的速度。 折半排序算法示意图： 以