java - 摇床排序或双向冒泡排序

Question

我目前正在学习数据结构和算法类(class)，其中一部分练习是使用 3 个 for 循环实现摇床排序算法。在代码片段中包含一些错误，我修复了这些错误，但是有一件事我不确定为什么会得到这个:当我初始化一个大小为 12 的数组时，我的第一个索引值没有排序，我不明白为什么。 这是我的代码:

// Method which will sort an array by using the shakersort algorithm
public void shakerSort(int[] array)
{      

    for (int p = 1; p < array.length-1; p++)
    {

        for (int i = p-1; i < array.length-2; i++)
        {                
            if (array[i] > array[i+1])
            {
                super.swap(array, i, i+1);
            }            
        }

        for (int i = array.length-p-1; i > 0; i--)
        {
            if (array[i] > array[i+1])
            {
                super.swap(array, i, i+1);
            }
        }

    }

我的结果是这样的:

• 元素 0:53
• 元素 1:27
• 元素 2:28
• 元素 3:53
• 元素 4:90
• 元素 5:72
• 元素 6:80
• 元素 7:67
• 元素 8:2
• 元素 9:33
• 元素 10:45
• 元素 11:91
• 排序后...
• 元素 0:27
• 元素 1:2
• 元素 2:28
• 元素 3:33
• 元素 4:45
• 元素 5:53
• 元素 6:53
• 元素 7:67
• 元素 8:72
• 元素 9:80
• 元素 10:90
• 元素 11:91

感谢您的时间和帮助

-丹尼尔

Answer 1

在我看来，您的代码根本没有使用 array[0]。

在最后一个循环中，您可能想要交换 i 和 i-1，而不是 i+1。

另外，AFAIK，这不是摇床也不是冒泡排序:你需要做的是一个主循环，里面有 2 个嵌套循环，一个从 0 到 size-1，另一个从 size-1 到 0，在循环之间，测试你是否必须交换，如果不是，那么你的数组已排序。

Take a look here for a clean implementation