1

这真的可能吗？我在维基百科中找到了它，但我还不能完美地可视化这个过程，所以我不知道我必须改变什么才能使其稳定。

4

2 回答 2

3

任何基于比较的排序算法都可以变得稳定。只需更改比较函数，如果两个元素相等，它就会比较它们的原始索引。由于 stooge 排序是基于比较的排序，因此也可以在此处应用。

于 2012-05-13T20:41:32.333 回答
0

首先，请注意， Stooge Sort只有一个步骤实际上改变了元素的顺序：第一步。剩下的步骤都是递归步骤。更改任何递归步骤都会改变算法的基本特征，因此如果我们不以这种方式递归，它将不再是走狗（三个递归调用似乎是典型的“走狗”。）

第一步也很简单，改变它似乎也改变了算法的特性。但是我们可以对其进行调整：如果初始元素大于最终元素，则将与最终元素相等的第一个元素A与A之前的最后一个元素与初始元素相等，我们可以通过 a 找到单程。令人惊讶的是，即使内部循环现在是 O( n ) 而不是 O(1)，Master 定理告诉我们复杂度在 O( n ^2.71)处保持不变。同样，如果所有元素都是唯一的，则将发生与原始 Stooge Sort 相同的交换序列，这使该版本成为近亲。

为了快速概述为什么这个版本是稳定的，考虑重新排序两个相等的元素是一个“坏交换”。我们声称使用上述方法没有坏掉期。原因是对于任何交换，我们知道两个元素之间没有一个元素等于任何一个元素。由于相等的元素保持相同的顺序，算法是稳定的。

该算法正确的证明类似于原始 Stooge Sort 的正确性证明。这是一个常见的家庭作业问题，所以我不想放弃它，但它来自归纳假设。

如果调整的描述有点简洁，Java 实现如下。

import java.util.Arrays;
import java.util.Random;

public class StableStooge {
    public static class FooBar implements Comparable<FooBar> {
        public final int foo;
        public final int bar;

        public FooBar(int foo, int bar) {
            this.foo = foo;
            this.bar = bar;
        }

        @Override
        public int compareTo(FooBar arg0) {
            return foo - arg0.foo;
        }

        public String toString() {
            return foo +":"+bar;
        }
    }

    private static void sort(Comparable[] c, int start, int end) {
        if (start >= end) return;
        if (c[start].compareTo(c[end]) > 0) {
            // Find the first thing X equal to end and the last thing Y which is before X and equal to start
            int lastindex = end;
            int firstindex = start;
            for (int i = start + 1; i < end; i++) {
                if (c[end].compareTo(c[i]) == 0) {
                    lastindex = i;
                    break;
                } else if (c[start].compareTo(c[i]) == 0) {
                    firstindex = i;
                }
            }
            Comparable tmp = c[firstindex];
            c[firstindex] = c[lastindex];
            c[lastindex] = tmp;
        }
        // Recurse
        if (end - start + 1 >= 3) { 
            int third = (end - start + 1) / 3;
            sort(c, start, end-third);
            sort(c, start+third, end);
            sort(c, start, end-third);
        }
    }

    public static void sort(Comparable[] c) {
        sort(c, 0, c.length-1);
    }

    public static void main(String[] args) {
        FooBar[] test = new FooBar[100];
        FooBar[] testsav = new FooBar[100];
        Random r = new Random();
        for (int i = 0; i < 1000; i++) {
            for (int j = 0; j < test.length; j++) {
                test[j] = new FooBar(r.nextInt(10), j);
                testsav[j] = test[j];
            }
            sort(test);
            // verify
            for (int j = 1; j < test.length; j++) {
                if (test[j].foo < test[j-1].foo) {
                    throw new RuntimeException("Bad sort");
                }
                if (test[j].foo == test[j-1].foo && test[j].bar <= test[j-1].bar) {
                    throw new RuntimeException("Unstable sort: "+Arrays.toString(testsav)+" sorted improperly to "+Arrays.toString(test));
                }
            }
        }
    }
}
于 2012-05-14T07:29:56.153 回答