java - 对冒泡排序程序进行 2 次修改

Question

我必须对一个简单的冒泡排序程序进行以下 2 处修改:

1. 第一遍后，最大数保证在数组中编号最高的元素中；第二遍后，最高的两个数字“到位”；等等。不是每次通过都进行九次比较，而是修改冒泡排序以在第二遍进行八次比较，第三次进行七次比较，依此类推。

2. 数组中的数据可能已经按正确的顺序排列或接近正确的顺序，那么如果更少的遍数就足够了，为什么要进行九遍呢？修改排序以在每次传递结束时检查是否进行了任何交换。如果没有生成，则数据必须已经按正确的顺序排列，因此程序应该终止。如果已进行交换，则至少需要再通过一次。”

对于我应该如何处理这些问题的任何帮助，将不胜感激!

//sort elements of array with bubble sort
public static void bubbleSort (int array2[])
{

    //loop to control number of passes
    for (int pass = 1; pass < array2.length; pass++)
    {

        //loop to control number of comparisons
        for (int element = 0; element < array2.length - 1; element++)
        {

            //compare side-by-side elements and swap them if 
            //first element is greater than second element
            if (array2[element] > array2[element + 1]){

                swap (array2, element, element + 1);

            }
        }
    }
}
//swap two elements of an array
public static void swap (int array3[], int first, int second)
{
    //temporary holding area for swap
    int hold;
    hold = array3[first];
    array3[first] = array3[second];
    array3[second] = hold;

}

Answer 1

我想这对你有用。添加一个 boolean 值以进行检查，并从每次运行的 input.length 中减去运行 (​​j)。

public static int[] bubbleSort(int input[])
{
    int i, j, tmp;
    bool changed;
    for (j = 0; j < input.length; j++)
    {
        changed = false;
        for (i = 1; i < input.length - j; i++)
        {
            if (tmp[i-1] > input[i])
            {
                tmp= input[i];
                input[i] = input[i-1];
                input[i-1] = tmp;
                changed = true;
            }
        }
        if (!changed) return input;
    }
    return input;
}