java - 如何保存算法对数组进行排序所需的步骤？

Question

我目前正在尝试用 Java 开发一个程序，该程序必须打印算法对数组中的元素进行排序所采取的步骤(每次更改时数组中的所有元素)，其中打印意味着在控制台中显示它，保存它作为文件或在 SwingComponent 中。

现在我正在使用 Arraylist< int[] > 来保存这些步骤，但它只允许我在抛出异常之前对少于 1k 的元素进行排序。

无论如何我可以节省更多元素的步骤吗？

代码

package tests;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class BubbleSort{

    public void sort( int[] array, List<int[]> process ){

        int len = array.length - 1;
        int i, j, tmp;

        process.add( array.clone() ); //Save original array
        for( i = 0; i < len; ++i ){
            for( j = 0; j < len - i; ++j ){
                if( array[ j ] > array[ j + 1 ] ){
                    tmp = array[ j ];
                    array[ j ] = array[ j + 1 ];
                    array[ j + 1 ] = tmp;
                    process.add( array.clone() ); //Array changed, save it
                }
            }
        }
    }

    //creates a random array
    public static int[] randomIntegerArray( int min, int max, int amount ){

        int[] array = new int[ amount ];
        int total = max - min;
        List< Integer > numbers = new ArrayList<>( total );
        int i = 0;

        for( i = min; i < max; ++i ){
            numbers.add( i );
        }

        Collections.shuffle( numbers );

        for( i = 0; i < amount; ++i ){

            array[ i ] = numbers.remove( 0 );
        }

        return array;
    }

    public static void main( String[] args ){
        BubbleSort bubbleSort = new BubbleSort();
        List<int[]> process = new ArrayList<>();
        int[] noError = randomIntegerArray( 0, 1000, 500 ); //Works up ~ 900
        int[] error = randomIntegerArray( 0, 1000, 1000 );

        bubbleSort.sort( noError, process);// Works
        //bubbleSort.sort( error, process);// throws java.lang.OutOfMemoryError: Java heap space in line 22

        //Print steps
        //for( int[] a : process ){ System.out.println( Arrays.toString( a ) ); }

    }

}

Answer 1

Is there anyway I can save the steps for more elements?

方法#1 - 增加堆大小。不幸的是，这无法扩展。

方法 #2 - 不是在每次交换后保存整个数组，而是只保存您交换的一对元素的详细信息。如有必要，您可以通过重放交换操作来重建数组……从初始数组状态向前或从最终状态向后。

方法 3 - 根本不保存步骤。只需在排序时将它们输出到控制台/文件/Swing 组件即可。

---

关于可扩展性。

• 您正在使用冒泡排序，这意味着一种 N 元素数组涉及 O(N^2) 个步骤。
• 如果在每一步都对整个数组进行快照，则需要 O(N^3) 内存来保存它们。对于大的 N，这就是很多的内存!!
• 如果您只存储交换的一对数组元素的详细信息，则内存需求减少到 O(N^2)。那仍然是很多内存。
• 如果您根本不存储详细信息(因为您是直接输出它们!)，则内存需求下降到 O(N) 以实现简单的实现。 (这是将数组状态格式化为字符串所需的内存量。如有必要，您可以将其实现为 O(1)。)

我正在使用的O(...) 东西叫做"Big O" notation .粗略地说，O(N) 表示与 N 成正比...因为 N 趋于无穷大。这方面的数学是基于极限。