修改冒泡排序算法的问题

Question

好的，我正在尝试编写一个对数组进行排序的算法，在本例中是一个随机整数数组。我知道 QuickSort 或类似算法显然会更有效率，但对于这项任务，我基本上必须对低效的冒泡排序算法进行修改。

这个想法是在一个间隙中比较整数。每次通过后，间隙应该减半。如果左边的值大于右边的值，则交换它们。执行应该一直持续到没有交换发生或间隙为 1 为止。我通常在这类事情上表现不佳，但似乎我遗漏了一些东西。由于某种原因，该算法没有对我的数组进行排序。

这是我的代码。也许有人可以看到我遗漏了什么：

public class ShellArray
{
    private int capacity;
    private int [] randArray;
    private static final int RANGE = 200;               //Range set to 200 for possible integers.

    public ShellArray(int capacity)
    {
        this.capacity = capacity;
        randArray = new int[capacity];
        populate(randArray, RANGE, capacity);
    }

    /**************************************************************************************************************************************************
    //
    //Populates array with random integers within given range.
    //
    ***************************************************************************************************************************************************/

    private static void populate(int [] myArray, int numRange, int extent)
    {
        Random r = new Random();

        for (int i = 0; i < extent; i++)
            myArray[i] = (r.nextInt(numRange)+1);
    }

    /**************************************************************************************************************************************************
    //
    //The first version of shellSort calls the second version with min value as 0 and max as length of randArray-1. Takes no parameters.
    //
    ***************************************************************************************************************************************************/
    public void shellSort()
    {
        shellSort(0, randArray.length-1);
    }

    /**************************************************************************************************************************************************
    //
    // shellSort which takes min and max parameters. Calculates gap at center, across which values are compared. Passes continue until gap size is 1
    // and array is sorted.
    // Uses boolean sorted to indicate when array is sorted so passes don't continue needelessly after array is sorted. Essentially, if no values
    // are swapped after a pass, we know array is sorted and sorted is not set to false.
    //
    // Outer for loop controls position of final value. Since largest value is bubbled to end, position decreases by 1 after each pass.
    // After each pass, size of gap is cut in half, as long as gap is 2 or greater. Otherwise gap would become too small.
    // Inner for loop controls the index values to be compared.
    // Uses swap method to swap values which are not in the correct order.
    // Array is printed after each pass.
    //
    ***************************************************************************************************************************************************/

    public void shellSort(int min, int max)
    {
        String result;
        int gap;
        int j = 0;
        int size = randArray.length-1;
        boolean swapped;

        for(gap = size/2; gap <= 0; gap = gap/2)
        {
            swapped = true;

            while (swapped)
            {   
                swapped = false;
                int comp;

                for(comp = 0; comp+gap <= size; comp++)
                {
                    if (randArray[comp] > randArray[comp+gap])
                    {
                        swap(comp, comp+gap);
                        swapped = true;        //swapped set to true if any element is swapped with another.
                    }
                    else
                        swapped = false;
                }
            }

            result = "";
            for(int y = 0; y < randArray.length; y++)
            {
                result += randArray[y] + " ";
                j++;
            }

            System.out.println("Pass " +j+": " +result+"\n");
         }
    }

    /**************************************************************************************************************************************************
    //
    // Swaps two values in the array.
    //
    ***************************************************************************************************************************************************/

    private void swap(int index1, int index2)
    {
        int temp = randArray[index1];
        randArray[index1] = randArray[index2];
        randArray[index2] = temp;
    }

    public String toString()
    {
        String result = "";

        for(int y = 0; y < randArray.length; y++)
            result += randArray[y] +" ";

        return result;
    }

}

Answer 1

您没有提供作业的详细信息，但按照这些思路进行排序的想法是，最后阶段（即 gap == 1）是 善意的 标准排序本身——在这种情况下，我猜是冒泡排序——并且前面的阶段对输入进行预处理，以便最终排序的效率比随机输入好得多。至少 gap == 1，然后，您必须重复排序循环，直到没有交换。

此处可能有两种主要变体，但您尚未向我们提供您想要哪种变体的信息：

第一个变体在排序循环的每次迭代后缩小间隙，直到达到 1，然后重复该间隙，直到没有更多交换。
第二种变体以相同的间隙重复排序循环，直到没有交换，然后缩小间隙并重复。

我的猜测是您想要第二个，因为它实际上属于 shell 类型（具有不寻常的风味）。尽管它听起来可能比另一个效率低，但它很有可能更有效，因为当差距很大时投入少量额外的努力可以实现更大的元素运动步数更少。

修改冒泡排序算法的问题

Issue with Modified Bubble Sort Algorithm

java

arrays

sorting

integer