如何在 Java 中使用冒泡排序算法对手动链表进行排序

Java 3月前 11

冒泡排序是一种简单但效率较低的排序算法。它通过多次比较和交换相邻元素的方式将列表中的元素按照升序或降序排列。在 Java 中，我们可以使用冒泡排序算法对手动链表进行排序。本文将介绍如何使用冒泡排序算法对手动链表进行排序，并附带注意事项。

冒泡排序算法的实现步骤如下：

创建一个指向链表头部的指针。
使用两个嵌套的循环来遍历链表，并进行比较和交换操作。
外部循环控制需要进行比较和交换操作的轮数。
内部循环将当前节点与下一个节点进行比较，如果当前节点大于下一个节点，则交换它们。
循环结束后，最大（或最小）的元素将被移动到链表的尾部。
更新指向链表头部的指针，将其指向下一个节点。
重复步骤2-6，直到所有节点都按照升序或降序排列。

以下是一个使用冒泡排序算法对手动链表进行升序排列的示例代码：

class ListNode {
    int val;
    ListNode next;
  
    ListNode(int val) {
        this.val = val;
    }
}

public class BubbleSortLinkedList {
    public static ListNode bubbleSort(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        ListNode currentHead = head;
        boolean isSwapped;
        
        do {
            isSwapped = false;
            ListNode current = currentHead;
            ListNode previous = null;
            
            while (current.next != null) {
                if (current.val > current.next.val) {
                    ListNode nextNode = current.next;
                    
                    if (previous != null) {
                        previous.next = nextNode;
                    } else {
                        currentHead = nextNode;
                    }
                    
                    current.next = nextNode.next;
                    nextNode.next = current;
                    previous = nextNode;
                    isSwapped = true;
                } else {
                    previous = current;
                    current = current.next;
                }
            }
        } while (isSwapped);
        
        return currentHead;
    }
    
    public static void main(String[] args) {
        ListNode head = new ListNode(9);
        head.next = new ListNode(5);
        head.next.next = new ListNode(2);
        head.next.next.next = new ListNode(7);
        head.next.next.next.next = new ListNode(3);
        
        ListNode sortedHead = bubbleSort(head);
        
        while (sortedHead != null) {
            System.out.print(sortedHead.val + " ");
            sortedHead = sortedHead.next;
        }
    }
}

注意事项：