java - 快速排序稳定性演示

Question

我知道快速排序确实不稳定(在原语的情况下)，因为分区的工作方式/长距离交换。我试图了解如果使用快速排序对具有相等键的复杂对象进行排序会发生什么。本质上为什么 java Collections.sort 不使用快速排序。

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

请帮助我理解快速排序的稳定性问题。

DEMO

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

如果你想看到不稳定的结果，你不应该比较rank。

如果同时比较name和rank，那么item之间有严格的顺序，那么结果是稳定的。

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

这是我的版本:

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} 在排序之前是 BEFORE {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}.