这是一种新的排序算法? [用Java和伪代码实现]

前端之家收集整理的这篇文章主要介绍了这是一种新的排序算法? [用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,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,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),但我不确定.

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

解决方法

对我来说,它看起来像是一个改进的气泡排序算法,对于输入元素的某些排列可能会更好.
不一定是公平的,我使用你的输入数组做了一个基准测试,用于比较:

> 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,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,R);

                    L--;
                    R++;
                }
            }
        }

        // Swap two items in array.
        public static void swap(int[] array,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,endTime);
        }
    }

    public static void executeBenchmark(int inputSize,ArrayList<Benchmark.Result> results) {
        // final int[] inputArray = { 15,// 10,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()",inputArray.length);
                    BubbleSort.sort(temp);
                    return null;
                }
            }));
            results.add(Benchmark.executionTimeAutotuned("OrbitSort.sort()",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("----------------------------------------------------");
        }

    }
}
原文链接:https://www.f2er.com/java/122593.html

猜你在找的Java相关文章