通过改变节点将快速排序算法应用于双向链表 [英] Apply Quick sort algorithm to Doubly linked list by changing nodes

问题描述

我需要使用快速排序算法对双向链表进行排序.使用递归进行排序.我的分区函数与我们在数组中使用的分区函数相同.但是我在跟踪每个列表中的当前头节点和尾节点时遇到了困难.

I need to sort the doubly linked list by using quicksort algorithm. Used recursion for sorting. And my partitioning function is same as the one we used in arrays. But I faced a hard time with tracking the current head node and tail node in each list.

public void sort() {
    Node la = getLast(head);
    last = la;
    quickSort(head, last);
}

public void quickSort(Node newhead, Node newlast) {

    if(newhead == null || newlast == null) {
        return;
    }
    if(newhead == newlast) {
        return;
    }
    Node parti = partition(newhead,newlast);

    if(parti != head)
        quickSort(newhead, parti.prev);
    if(parti != last)
        newlast = acualTail;
        quickSort(parti.next, newlast);


}

public Node partition(Node newHead, Node newLast) {

    //Node actHead = newHead;
    //Node acLast = newLast;
    Node current = newHead;
    Node p = newLast;

    while(current != p) {

        if(current.data > p.data) {
            Node next = current.next;
            current.next.prev = current.prev;
            if(current.prev != null)
                current.prev.next = current.next;
            current.next = newLast.next;
            current.prev = newLast; 
            newLast.next = current;

            //head = next;
            if(current == newHead)
                newHead = next;
            newLast = current;
            current = next;
        }
        else {
            current = current.next;

        }
    }


    head= newHead;
    last = newLast;
    return p;
}

推荐答案

我就是这样做的.

public Node getLast(Node head) {
    Node current = head;
    while(current.next != null) {
        current = current.next;
    }

    return current;
}

public void sort() {
    Node la = getLast(head);
    quickSort(head, la);
    head = actualHead;
}

public void quickSort(Node head, Node last) {

    if(head == last)
        return;
    if(head == null || last == null)
        return;
    if(last.next == head)
        return;

    Node partition = partition(head, last);

    Node newHead = this.head;
    Node newTail = this.last;


    quickSort(newHead, partition.prev);

    if(actualHead == null)
    {
        actualHead = newHead;
    }

    quickSort(partition.next, newTail);

}

public Node partition(Node head, Node last) {
    Node current = head;
    Node p = last;

    while(current != p) {

        if(current.data > p.data) {
            Node next = current.next;
            current.next.prev = current.prev;
            if(current.prev != null)
                current.prev.next = current.next;
            current.next = last.next;
            current.prev = last; 
            last.next = current;

            if(current == head)
                head = next;
            last = current;
            current = next;
        }
        else {
            current = current.next;

        }
    }
    this.head = head;
    this.last = last;
    return p;
}

这篇关于通过改变节点将快速排序算法应用于双向链表的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！