10

我知道这可能是一个愚蠢的问题，也许是今天最愚蠢的问题，但我不得不问它：我发明了这个排序算法吗？

昨天，我对基于交换的排序算法有了一点启发。今天，我实现了它，它奏效了。

它可能已经存在，因为那里有许多不太流行的排序算法，它们的信息很少或根本没有，而且几乎不存在它们的实现。

描述：基本上，这个算法需要一个项目，他们一对，然后再一个项目......直到列表的末尾。对于每个项目/对，比较距对空间或项目相同半径距离的每两个项目，直到到达数组的边界，然后在需要时交换这些项目。对列表中的每一对/项目重复此操作。

基于英文的伪代码：

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) 中运行，但我不确定。

所以你怎么看？它已经存在了吗？

4

2 回答 2

7

对我来说，它看起来像是一种修改后的冒泡排序算法，对于某些输入元素的排列可能会表现得更好。尽管不一定公平，但我使用您的输入数组对预热周期进行了基准测试，以比较：

  • java.util.Arrays.sort()，这是一个合并快速排序实现
  • BubbleSort.sort()，一个冒泡排序算法的java实现
  • OrbitSort.sort()，你的算法

结果：

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("----------------------------------------------------");
        }

    }
}
于 2013-01-05T18:35:34.063 回答
2

它是 O(n^2) （假设它有效，我不确定），因为它已经存在 - 也许 - 它不是真正的原创，因为它可以被认为是一个简单的排序实现的变体，但我怀疑如果有任何已发布的算法与该算法完全相同，特别是具有两个连续内循环的算法。

我并不是说它没有优点，可能有一个用例，它的行为是独特有效的（也许读取比写入快得多，缓存行为有利于它的访问模式）。

要了解为什么它是 O(n^2)，请考虑前 n/6 次外循环迭代，内循环运行 O(n) 长度 O(n) 次。

于 2013-01-05T17:23:57.227 回答