快速稳定演示

Question

我理解快速排序确实是不稳定的(在原语的情况下)，因为分区工作/远程交换的方式。我试图理解如果用快速排序来用相同的键对复杂的对象进行排序，会发生什么。从本质上讲，为什么java Collections.sort不使用快速排序。

这是一个演示应用程序，我创建了帮助我的理解。根据这个应用程序，具有相同键的对象似乎保留了它们的输入顺序。我知道我在这里有一些理解上的差距。我确实在网上搜索过，但是大多数例子都是基于整数排序的。

请帮助我理解快速稳定问题。

演示

import java.util.*;

public class QuickSortStabilityDemo {

    static class Node implements Comparable<Node> {
        String name;
        int rank;

        public Node(String name, int rank) {
            this.name =  name;
            this.rank = rank;
        }

        @Override
        public int compareTo(Node o) {
            int result = this.name.compareTo(o.name);
            if(result == 0) {
                return this.rank == o.rank ? 0 : this.rank < o.rank ? -1: 1;
            }
            else {
                return result;
            }
        }

        @Override
        public String toString() {
            return "{" + this.name + "," + this.rank + "," + this.hashCode() + "}" ;
        }
    }

    //Fisher-Yates 
        public void shuffleArray(Node[] arr) {
            Random random = new Random();
            int n = arr.length;

            for(int i=n-1; i>=0; i--) {
                int j = random.nextInt(i+1);
                Node temp = arr[i];
                arr[i]= arr[j];
                arr[j]=temp;
            }

        }

        private void swap(Node[] arr, int i, int j) {
            Node temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }

        public void sort(Node[] arr, int start, int end) {  

            if(start >= end) {
                return;
            }



            Node pivot = arr[start];

            int lt = start;
            int gt = end;


            for(int current=start+1;current <= gt; ) {

                if(arr[current].compareTo(pivot) < 0) {
                    swap(arr,current,lt);  
                    current++; 
                    lt++; 
                }
                else if(arr[current].compareTo(pivot) > 0) {
                    swap(arr,current,gt); 
                    gt--; 
                }
                else {
                    current++;
                }

            }
            sort(arr,start,lt-1);
            sort(arr,gt+1,end);


        }

        public static void main(String[] args) {
            QuickSortStabilityDemo sort = new QuickSortStabilityDemo();
            String[] cities = {"New York","Jersey City","Pittsburgh"};

            List<Node> list = new ArrayList<>();

            for(int i=0;i <3;i++) {
                for(int j=1; j <=3; j++) {
                    list.add(new Node(cities[i],i));
                }
            }

            Node[] arr = list.toArray(new Node[list.size()]);

            System.out.println("Before sorting...");

            System.out.println(Arrays.toString(arr));

            sort.sort(arr,0,arr.length-1);

            System.out.println("After sorting...");


            System.out.println(Arrays.toString(arr));
        }

}

Answer 1

我找到了答案：

在我发布的原始演示中，数据有点人为的。每个集合中的对象的属性是相同的，并且是有目的的。我没有对数组进行洗牌；将支点设置为正在排序的数组部分的开始元素。

当我进一步调试我的演示时，虽然纽约和JC对象保留了原来的order Pgh对象，但事件确实改变了它们最初的插入顺序。因此，我确实看到了算法的不稳定性。

我使用这些元素的哈希代码来跟踪它们的原始插入顺序。

以下是运行的输出：

[{New York,0,1163157884}
, {New York,0,1956725890}
, {New York,0,356573597}
, {Jersey City,1,1735600054}
, {Jersey City,1,21685669}
, {Jersey City,1,2133927002}
, {Pittsburgh,2,1836019240}
, {Pittsburgh,2,325040804}
, {Pittsburgh,2,1173230247}
]
After sorting
[{Jersey City,1,1735600054}
, {Jersey City,1,21685669}
, {Jersey City,1,2133927002}
, {New York,0,1163157884}
, {New York,0,1956725890}
, {New York,0,356573597}
, {Pittsburgh,2,325040804}
, {Pittsburgh,2,1173230247}
, {Pittsburgh,2,1836019240}
]

如果对输入阵列进行洗牌，则算法的不稳定性更加明显。

下面是运行的输出(和混合输入)：

Original order
[{New York,0,1163157884}
, {New York,0,1956725890}
, {New York,0,356573597}
, {Jersey City,1,1735600054}
, {Jersey City,1,21685669}
, {Jersey City,1,2133927002}
, {Pittsburgh,2,1836019240}
, {Pittsburgh,2,325040804}
, {Pittsburgh,2,1173230247}
]
After shuffling
[{New York,0,1163157884}
, {New York,0,1956725890}
, {Pittsburgh,2,325040804}
, {Jersey City,1,2133927002}
, {New York,0,356573597}
, {Jersey City,1,1735600054}
, {Pittsburgh,2,1836019240}
, {Pittsburgh,2,1173230247}
, {Jersey City,1,21685669}
]
After sorting
[{Jersey City,1,21685669}
, {Jersey City,1,2133927002}
, {Jersey City,1,1735600054}
, {New York,0,1956725890}
, {New York,0,356573597}
, {New York,0,1163157884}
, {Pittsburgh,2,1173230247}
, {Pittsburgh,2,1836019240}
, {Pittsburgh,2,325040804}
]

如果对这个答案有什么建议，请告诉我。

Answer 2

如果您希望看到不稳定的结果，则不应该比较rank。

如果您同时比较名称和排名，那么项目之间就会有严格的顺序，那么结果是稳定的。

只有当两个项目相等时，才会出现不稳定的结果。

这是我的版本：

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

public class QuickSortStabilityDemo {

    static class Node implements Comparable<Node> {
        String name;
        int rank;

        public Node(String name, int rank) {
            this.name = name;
            this.rank = rank;
        }

        @Override
        public int compareTo(Node o) {
            return this.name.compareTo(o.name);
        }

        @Override
        public String toString() {
            return "{" + this.name + "," + this.rank + "}";
        }
    }

    private void swap(Node[] arr, int i, int j) {
        Node temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public void sort(Node[] arr, int start, int end) {
        if (start >= end) {
            return;
        }
        Node pivot = arr[start];

        int lt = start;
        int gt = end;
        for (int current = start + 1; current <= gt; ) {
            if (arr[current].compareTo(pivot) < 0) {
                swap(arr, current, lt);
                current++;
                lt++;
            } else if (arr[current].compareTo(pivot) > 0) {
                swap(arr, current, gt);
                gt--;
            } else {
                current++;
            }

        }
        sort(arr, start, lt - 1);
        sort(arr, gt + 1, end);
    }

    public static void main(String[] args) {
        QuickSortStabilityDemo sort = new QuickSortStabilityDemo();

        String[] cities = {"New York", "Jersey City", "Pittsburgh"};

        List<Node> list = new ArrayList<>();

        for (int i = 1; i <= 3; i++) {
            for (int j = 0; j < 3; j++) {
                list.add(new Node(cities[j], i));
            }
        }

        Node[] arr = list.toArray(new Node[list.size()]);
        System.out.println("Before sorting...");
        System.out.println(Arrays.toString(arr));
        sort.sort(arr, 0, arr.length - 1);
        System.out.println("After sorting...");
        System.out.println(Arrays.toString(arr));
    }

}

输出：

Before sorting...
[{New York,1}, {Jersey City,1}, {Pittsburgh,1}, {New York,2}, {Jersey City,2}, {Pittsburgh,2}, {New York,3}, {Jersey City,3}, {Pittsburgh,3}]
After sorting...
[{Jersey City,1}, {Jersey City,3}, {Jersey City,2}, {New York,2}, {New York,1}, {New York,3}, {Pittsburgh,2}, {Pittsburgh,3}, {Pittsburgh,1}]

您可以看到，在排序之前，{Jersey City,2}是在{Jersey City,3}之前。

但在排序之后，{Jersey City,2}就是{Jersey City,3}。

这是不稳定的结果。

PS:如果您使用其他稳定的算法，结果必须是{J,1},{J,2},{J,3},{N,1},{N,2},{N,3},{P,1},{P,2},{P,3}。