Java 递归快速排序中静态变量的陷阱与解决方案

static dlinkedList sortedList = new dlinkedList(); // 静态变量
public static dlinkedList quicksortPrice(dlinkedList list) {
    // ... 内部逻辑将元素添加到 sortedList ...
    // ... 递归调用 quicksortPrice(smaller); quicksortPrice(greater); ...
    return sortedList;
}

// 假设 quicksortPrice 仍然使用内部静态 sortedList
public class Operations {
    static dlinkedList sortedList = new dlinkedList(); // 仍然是静态的

    public static dlinkedList quicksortPrice(dlinkedList list) {
        // ... 原始的快速排序逻辑 ...
        return sortedList;
    }

    public static void main(String[] args) {
        dlinkedList dList = Operations.fillList(); // 假设 fillList 每次返回新的列表

        // 第一次排序
        dlinkedList list1 = dlinkedList.quicksortPrice(dList);
        dlinkedList.printAllElements(list1);
        System.out.println(" sorted once ");

        // 在第二次排序前，重置静态变量
        dlinkedList.sortedList = new dlinkedList(); // 关键步骤：重置为新的空列表
        dlinkedList list2 = dlinkedList.quicksortPrice(dList);
        dlinkedList.printAllElements(list2);
        System.out.println(" sorted twice ");
    }
}

public class dlinkedList {
    Node head;
    Node tail;
    int size; // 维护列表大小

    // 假设 Node 和 Item 类已定义
    static class Node {
        Item data;
        Node next;
        Node prev;

        public Node(Item data) {
            this.data = data;
            this.next = null;
            this.prev = null;
        }
    }

    static class Item {
        int id;
        double price;
        String name;
        String category;

        public Item(int id, double price, String name, String category) {
            this.id = id;
            this.price = price;
            this.name = name;
            this.category = category;
        }
    }

    public dlinkedList() {
        this.head = null;
        this.tail = null;
        this.size = 0;
    }

    public void addAtEndOfList(Item data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = newNode;
        }
        size++;
    }

    public boolean isEmpty() {
        return head == null;
    }

    // 辅助方法：连接两个链表
    public void concatenate(dlinkedList other) {
        if (other.isEmpty()) {
            return;
        }
        if (this.isEmpty()) {
            this.head = other.head;
            this.tail = other.tail;
        } else {
            this.tail.next = other.head;
            other.head.prev = this.tail;
            this.tail = other.tail;
        }
        this.size += other.size;
        // 清空other，防止引用混淆，或者直接让other被GC
        other.head = null;
        other.tail = null;
        other.size = 0;
    }

    // 核心快速排序方法：返回一个新的已排序链表
    public static dlinkedList quicksortPrice(dlinkedList list) {
        if (list == null || list.isEmpty() || list.size <= 1) {
            // 基线条件：空列表或单元素列表已排序
            dlinkedList result = new dlinkedList();
            if (list != null && !list.isEmpty()) {
                result.addAtEndOfList(list.head.data); // 复制唯一元素
            }
            return result;
        }

        // 选择基准：这里使用尾部元素作为基准
        Item pivot = list.tail.data;

        dlinkedList smaller = new dlinkedList();
        dlinkedList greater = new dlinkedList();
        dlinkedList equals = new dlinkedList(); // 处理等于基准的元素

        Node current = list.head;
        while (current != null) {
            if (current.data.price < pivot.price) {
                smaller.addAtEndOfList(current.data);
            } else if (current.data.price > pivot.price) {
                greater.addAtEndOfList(current.data);
            } else {
                equals.addAtEndOfList(current.data);
            }
            current = current.next;
        }

        // 递归排序子列表
        dlinkedList sortedSmaller = quicksortPrice(smaller);
        dlinkedList sortedGreater = quicksortPrice(greater);

        // 合并结果：sortedSmaller + equals + sortedGreater
        dlinkedList sortedResult = new dlinkedList();
        sortedResult.concatenate(sortedSmaller);
        sortedResult.concatenate(equals); // 将所有等于基准的元素放在中间
        sortedResult.concatenate(sortedGreater);

        return sortedResult;
    }

    public static void printAllElements(dlinkedList list) {
        if (list == null || list.isEmpty()) {
            System.out.println("List is empty.");
            return;
        }
        Node current = list.head;
        while (current != null) {
            System.out.printf("| Name: %s| Price: %.1f| Category: %s%n",
                    current.data.name, current.data.price, current.data.category);
            current = current.next;
        }
    }
}

public class Operations {
    // 假设 fillList 方法返回一个新的 dlinkedList 实例
    public static dlinkedList fillList() {
        dlinkedList list = new dlinkedList();
        list.addAtEndOfList(new dlinkedList.Item(234, 44.2, "wardrobe", "Example Wardrobe"));
        list.addAtEndOfList(new dlinkedList.Item(432, 87.2, "Chair", "Example Table"));
        list.addAtEndOfList(new dlinkedList.Item(007, 600.666, "Table", "Example Table"));
        list.addAtEndOfList(new dlinkedList.Item(02, 5.4, "Jar", "Example Jar"));
        return list;
    }

    public static void main(String[] args) {
        dlinkedList dList = Operations.fillList(); // 原始列表

        // 第一次排序
        dlinkedList list1 = dlinkedList.quicksortPrice(dList);
        dlinkedList.printAllElements(list1);
        System.out.println(" sorted once ");

        // 第二次排序：每次都会得到一个全新的、独立的排序结果
        dlinkedList list2 = dlinkedList.quicksortPrice(dList); // 仍然对原始 dList 进行排序
        dlinkedList.printAllElements(list2);
        System.out.println(" sorted twice ");
    }
}