Java 中的快速排序，用于大量元素

Question

我需要一些帮助。我已经在 Java 中实现了 QuickSort，现在我正在测试处理 50.000 到 15.000.000 个元素所需的时间。问题是它花了这么长时间。例如：

50.000 Elements, 38 seconds.
100.000 Elements, 230 seconds.
250.000 Elements, I'm still waiting (around 8 minutes)

这样可以吗？这是我的代码：

/* Clase que implementa el QuickSort */
public class QuickSort {
    private static final int corte = 3;
    private int i, j;

    public void ordenar(Comparable[] a, int izquierda, int derecha) {

        if (izquierda + corte <= derecha) {

            Comparable pivote = mediana(a, izquierda, derecha);

            i = izquierda;
            j = derecha - 1;

            for (;;) {
                while (a[++i].compareTo(pivote) < 0) {
                }
                while (a[--j].compareTo(pivote) > 0) {
                }
                if (i < j) {
                    intercambiar(a, i, j);
                } else {
                    break;
                }

                intercambiar(a, i, derecha - 1);
            }

            ordenar(a, izquierda, i - 1);
            ordenar(a, i + 1, derecha);

        } else {

            InsertSort(a);
        }
    }

    private static Comparable mediana(Comparable[] a, int izquierda, int derecha) {
        int centro = (izquierda + derecha) / 2;

        if (a[centro].compareTo(a[izquierda]) < 0) {
            intercambiar(a, izquierda, centro);
        }

        if (a[derecha].compareTo(a[izquierda]) < 0) {
            intercambiar(a, izquierda, derecha);
        }

        if (a[derecha].compareTo(a[centro]) < 0) {
            intercambiar(a, centro, derecha);
        }

        intercambiar(a, centro, derecha - 1);
        return a[derecha - 1];

    }

    private static void intercambiar(Comparable[] arreglo, int a, int b) {
        Comparable temporal;
        temporal = arreglo[a];
        arreglo[a] = arreglo[b];
        arreglo[b] = temporal;

    }

    private void InsertSort(Comparable[] lista) {

        for (int i = 1; i < lista.length; i++) {
            Comparable auxiliar = lista[i];
            int j = i - 1;

            while (j >= 0 && lista[j].compareTo(auxiliar) > 0) {

                lista[j + 1] = lista[j];
                j = j - 1;

            }

            lista[j + 1] = auxiliar;

        }
    }
}



public class Test {

    public static void main (String [] args) {
        long tInicial = 0;
        long tFinal = 0;
        long tRes = 0;
        int tam = 250000;

        Arreglo B = new Arreglo (tam);

        System.out.print("Prueba de Tiempo:");
        B.cargarArreglo();
        tInicial = System.currentTimeMillis();
        B.ordenarArreglo();
        tFinal = System.currentTimeMillis();

        tRes = tFinal - tInicial;
        System.out.println();
        System.out.println("Tiempo Transcurrido (ms): " + tRes + " para " + tam + " elementos.");
    }
}

Answer 1

快速排序的运行时间是（平均）O(n log n) 或（最坏情况）O(n^2)。这意味着 50.000 的运行时间为 50.000 * 10.819778284410283 ~ 540000。对于 250.000，运行时间为：250.000 * 12.429216196844383 ~ 3.100.000。因此，250.000 的运行时间约为 50.000 的运行时间的 6 倍。另一个因素是内存管理。从 50.000 到 250.000 个元素的因子实际上是：~12.63。考虑到 O(n^2) 的最坏情况，这仍然可以。

Java 中的快速排序，用于大量元素

QuickSort in Java, for high number of elements

java

eclipse

sorting

time

quicksort