双链表快速排序

Question

我在使用快速排序程序中的交换方法时遇到问题。我正在通过对数组进行排序的 QuickSort 方法来实现它。在这里，我输入一个文件，每一行都有一个整数，它将数字放入一个双向链表中，然后对列表进行排序并输出到一个新文件。我需要有关交换方法的帮助，以及我需要添加或做些什么才能使其正常工作。任何建议都会有所帮助，例子是最好的。谢谢

    //swap A[pos1] and A[pos2]
   public static void swap(DList A, int pos1, int pos2){
      int temp = A.get(pos1); 
      A[pos1] = A[pos2]; 
      A[pos2] = temp; 
   }

我的整个快速排序程序如下所示：

import java.util.*;
import java.io.*;

public class Test_QuickSort{

   private static Scanner input = new Scanner(System.in); 
   private static DList list = new DList(); 

   public static void main(String[] args) throws FileNotFoundException
   {
      input = new Scanner(new File("data.txt"));

      while (input.hasNext())
      {
         String s = input.nextLine();
         DNode g = new DNode(Integer.parseInt(s));
         list.addLast(g);
      }
   //int[] A = {1,4,6,2};  

   QuickSort(list, 0, list.size()-1);

   //for(int i = 0; i < A.length; i++)
   //    System.out.print(A[i] + " ");

   }

   public static void QuickSort(DList A, int left, int right){
      if(left >= right)
         return; 

      int pivot_index = partition(A, left, right); 
      QuickSort(A, left, pivot_index - 1);
      QuickSort(A, pivot_index + 1, right);
   }

   public static int partition(DList A, int left, int right){
      int pivot = A.get(right); 
      int index = left; 

      for(int i = left; i < right; i++){
         if(A.get(i) <= pivot){
            swap(A, index, i);
            index ++; 
         }
      }
      swap(A, index, right);
      return index; 
   }


    //swap A[pos1] and A[pos2]
   public static void swap(DList A, int pos1, int pos2){
      int temp = A.get(pos1); 
      A[pos1] = A[pos2]; 
      A[pos2] = temp; 
   }

}

我的 DList 方法如下所示：

class DNode {
   protected int element;   // String element stored by a node
   protected DNode next, prev;  // Pointers to next and previous nodes

   public DNode(int e)
   {
      element = e;
      prev = null;
      next = null;
   }
   public DNode()
   {
      element = 0;
      next = null;
      prev = null;
   }
   public DNode(int e, DNode p, DNode n) {
      element = e;
      prev = p;
      next = n;
   }

   public int getElement() { 
      return element; }
   public DNode getPrev() { 
      return prev; }
   public DNode getNext() { 
      return next; }
   public void setElement(int newElem) { element = newElem; }
   public void setPrev(DNode newPrev) { prev = newPrev; }
   public void setNext(DNode newNext) { next = newNext; }
}

public class DList {
   protected int size;
   protected DNode header, trailer;
   public DList() { 
      size = 0;
      header = new DNode(0, null, null);    
      trailer = new DNode(0, header, null);
      header.setNext(trailer);
   }

   public int size() { 
      return size; }

   public boolean isEmpty() { 
      return (size == 0); }

   public DNode getFirst() throws IllegalStateException {
      if (isEmpty()) throw new IllegalStateException("List is empty");
      return header.getNext();
   }

   public DNode getLast() throws IllegalStateException {
      if (isEmpty()) throw new IllegalStateException("List is empty");
      return trailer.getPrev();
   }

   public DNode getPrev(DNode v) throws IllegalArgumentException {
      if (v == header) throw new IllegalArgumentException
            ("Cannot move back past the header of the list");
      return v.getPrev();
   }

   public int get(int pos)
   {
      DNode current = new DNode();
      for(int i = 0; i <= pos && current != null; i++)
      {
         if(pos == 0){
            current = header;
         }
         else{
            current = current.next;
            break;
         }
      }
      return current.element;
   }

   public DNode getNext(DNode v) throws IllegalArgumentException {
      if (v == trailer) throw new IllegalArgumentException
            ("Cannot move forward past the trailer of the list");
      return v.getNext();
   }

   public void addBefore(DNode v, DNode z) throws IllegalArgumentException {
      DNode u = getPrev(v); // may throw an IllegalArgumentException
      z.setPrev(u);
      z.setNext(v);
      v.setPrev(z);
      u.setNext(z);
      size++;
   }

   public void addAfter(DNode v, DNode z) {
      DNode w = getNext(v); // may throw an IllegalArgumentException
      z.setPrev(v);
      z.setNext(w);
      w.setPrev(z);
      v.setNext(z);
      size++;
   }

   public void addFirst(DNode v) {
      addAfter(header, v);
   }

   public void addLast(DNode v) {
      addBefore(trailer, v);
   }

   public boolean hasPrev(DNode v) { 
      return v != header; }

   public boolean hasNext(DNode v) { 
      return v != trailer; }

   public String toString() {
      String s = "[";
      DNode v = header.getNext();
      while (v != trailer) {
         s += v.getElement();
         v = v.getNext();
         if (v != trailer)
            s += ",";
      }
      s += "]";
      return s;
   }
}

Answer 1

您总是在 DList.get 中检索相同元素的原因是您在第一次迭代后停止循环。只需删除 break 语句，循环就会按预期工作。

public int get(int pos)
{
    DNode current = new DNode();
    for(int i = 0; i <= pos && current != null; i++)
    {
        if(pos == 0){
            current = header;
        }
        else{
            current = current.next;
            // break; <-- remove this
        }
    }
    return current.element;
}

旁注：如果将 current 初始化为 header，则可以去掉 if 语句：

public int get(int pos)
{
    DNode current = header;
    for(int i = 1; i <= pos && current != null; i++)
    {
        current = current.next;
    }
    return current.element;
}

现在关于您的 swap 方法：如前所述，您尝试通过使用方括号取消引用元素来将 DList 的实例视为数组。相反，您应该在 DList 中实现一个允许在特定位置设置元素的方法。例如：

public void setAt(int pos, int value){
    DNode current = header;
    for(int i = 1; i <= pos && current != null; i++){
        current = current.next;
    }
    if(current != null)
        current.setElement(value);
    else
        throw new IndexOutOfBoundsException();
}

现在您可以将 swap 方法更改为：

public static void swap(DList a, int pos1, int pos2){
    int temp = a.get(pos1);
    a.setAt(pos1, a.get(pos2)); 
    a.setAt(pos2, temp); 
}

双链表快速排序

QuickSort with Double Linked List

java

quicksort

doubly-linked-list