(java) 快速排序，先按数字对数字-字符对进行排序，然后按字符排序

Question

我修改了此处找到的算法：http://www.algolist.net/Algorithms/Sorting/Quicksort

与我一起工作 Node class:

public class Node
{
    public int frequency;
    public char value;
}

基本上应该先按频率排序，如果频率相同，再看char值。

这是我的代码：

public static int partition(Node arr[], int left, int right)
{
      int i = left, j = right;
      Node tmp;
      int pivot = (left + right) / 2;

      while (i <= j) {
            while (arr[i].frequency < arr[pivot].frequency)
                  i++;
            while (arr[j].frequency > arr[pivot].frequency)
                  j--;
            if (i <= j) {

                if (arr[i].frequency == arr[j].frequency)
                {
                    if (arr[i].value > arr[j].value)
                    {
                        tmp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = tmp;                           
                    }
                }
                else //(arr[i].frequency > arr[j].frequency)
                {
                    tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;                           
                }

                i++;
                j--;
            }
      };

      return i;
}

public static void quickSort(Node arr[], int left, int right) {
      int index = partition(arr, left, right);
      if (left < index - 1)
            quickSort(arr, left, index - 1);
      if (index < right)
            quickSort(arr, index, right);
}

目前它确实可以工作，但它时不时会漏掉一个字母。只是想让它正常工作。

感谢任何帮助！

谢谢。

编辑：感谢所有回答的人！我最终使用了 Comparable 建议。现在排序很好。

Answer 1

这里的评论不正确：

            else //(arr[i].frequency > arr[j].frequency)

if 分支检查频率是否相同，因此在 else 中，您仍然必须在交换它们之前检查它们的顺序是否正确。

我建议编写一个单独的函数来比较节点。

Answer 2

我建议您将比较 2 个 Node 对象移动到不同的方法，或者使 Node 具有可比性。我将在这里演示第二个选项。

public class Node implements Comparable<Node> {
    public int frequency;
    public char value;

    @Override
    public int compareTo(Node o) {
        if(this.frequency < o.frequency)
            return -1;
        else if(this.frequency > o.frequency)
            return 1;
        else {
            if(this.value < o.value)
                return -1;
            else if(this.value > o.value)
                return 1;
            return 0;
        }
    }
}

现在，您不必在进行快速排序比较时同时检查两个字段，只需执行类似 if(arr[i].compareTo(arr[j]) < 0 的操作即可。让我知道这是否有帮助。如果没有，我可以帮助编写更多代码。

对于排序，我建议使用 Arrays.sort(arr)，现在您已经实现了 Comparable。编辑。对于 Java 中的基元数组，此函数使用双轴快速排序，这非常酷。对于对象数组，使用 TimSort。 [docs] [TimSort vs QuickSort]

Answer 3

这里有 5 种方法（您可以添加更多）：
作为这个 http://www.algolist.net/Algorithms/Sorting/Quicksort
说+你的代码有一些编辑：

package AR;

class Node {
    public int frequency;
    public char value;

    public Node(int frequency, char value) {
        this.frequency = frequency;
        this.value = value;
    }
}

final class Sort {

    int partition(Node arr[], int left, int right) {
        int i = left, j = right;
        Node tmp;
        Node pivot = arr[(left + right) / 2];

        while (i <= j) {
            while (i <= j && (arr[i].frequency < pivot.frequency || (arr[i].frequency == pivot.frequency && arr[i].value < pivot.value)))
                i++;
            while (i <= j && (arr[j].frequency > pivot.frequency || (arr[j].frequency == pivot.frequency && arr[j].value > pivot.value)))
                j--;
            if (i <= j) {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        return i;
    }

    public void quickSort(Node arr[], int left, int right) {
        if (left > right) return;
        int index = partition(arr, left, right);
        if (left < index - 1)
            quickSort(arr, left, index - 1);
        if (index < right)
            quickSort(arr, index, right);
    }
}

final class Main {
    public static void main(String[] args) {

        Node[] ns = new Node[]{new Node(10, 'a'), new Node(10, 'c'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(0, 'z'), new Node(1, 'z')};
        int n = ns.length;
        Sort cl = new Sort();
        cl.quickSort(ns, 0, n - 1);
        for (int i = 0; i < n; i++) {
            System.out.print("(" + ns[i].frequency + "," + ns[i].value + "), ");
            //(0,z), (1,b), (1,b), (1,b), (1,z), (8,a), (8,a), (8,a), (10,a), (10,a), (10,a), (10,b), (10,b), (10,c),
        }
    }
}

//@Debosmit Ray 方式：（只需将 int 更改为 T）在 Java::

中使用泛型

package AR;

class Node implements Comparable<Node> {
    public int frequency;
    public char value;

    public Node(int frequency, char value) {
        this.frequency = frequency;
        this.value = value;
    }

    @Override
    public int compareTo(Node o) {
        if (this.frequency > o.frequency) return 1;
        if (this.frequency < o.frequency) return -1;
        if (this.value > o.value) return 1;
        if (this.value < o.value) return -1;
        return 0;
    }
}

final class Sort<T extends Comparable<T>> {

    int partition(T arr[], int left, int right) {
        int i = left, j = right;
        T tmp;
        T pivot = arr[(left + right) / 2];

        while (i <= j) {
            while (i <= j && arr[i].compareTo(pivot) < 0)
                i++;
            while (i <= j && arr[j].compareTo(pivot) > 0)
                j--;
            if (i <= j) {
                tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
                j--;
            }
        }
        return i;
    }

    public void quickSort(T arr[], int left, int right) {
        if (left > right) return;
        int index = partition(arr, left, right);
        if (left < index - 1)
            quickSort(arr, left, index - 1);
        if (index < right)
            quickSort(arr, index, right);
    }
}

final class Main {
    public static void main(String[] args) {

        Node[] ns = new Node[]{new Node(10, 'a'), new Node(10, 'c'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(0, 'z'), new Node(1, 'z')};
        int n = ns.length;
        Sort cl = new Sort();
        cl.quickSort(ns, 0, n - 1);
        for (int i = 0; i < n; i++) {
            System.out.print("(" + ns[i].frequency + "," + ns[i].value + "), ");
            //(0,z), (1,b), (1,b), (1,b), (1,z), (8,a), (8,a), (8,a), (10,a), (10,a), (10,a), (10,b), (10,b), (10,c),
        }
    }
}

//将主元放在数组的左侧，并在一个循环中进行比较，如下所示：

package AR;

class Node {
    public int frequency;
    public char value;
    public Node(int frequency, char value) {
        this.frequency = frequency;
        this.value = value;
    }
}
final class Main {
    static int partition(Node[] arr, int left, int right) {
        int i = left+1, j = right;
        Node tmp;
        int pivot =  left  ;
        while (i <= j) {
            while (i <= j && (arr[i].frequency < arr[pivot].frequency || (arr[i].frequency == arr[pivot].frequency && arr[i].value <= arr[pivot].value)))
                i++;
            while (i <= j && (arr[j].frequency > arr[pivot].frequency || (arr[j].frequency == arr[pivot].frequency && arr[j].value > arr[pivot].value)))
                j--;
            if (i > j) break;
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
        }
        tmp = arr[pivot];
        arr[pivot] = arr[j];
        arr[j] = tmp;
        return j;
    }
    public static void quickSort(Node arr[], int left, int right) {
        if (left >= right) return;
        int i = partition(arr, left, right);
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
    public static void main(String[] args) {
        Node[] ns = new Node[]{new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(0, 'z'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(1, 'z')};
        int n = ns.length;
        quickSort(ns, 0, n - 1);
        for (int i = 0; i < n; i++) {
            System.out.print("(" + ns[i].frequency + "," + ns[i].value + "), ");
            //(0,z), (1,b), (1,b), (1,b), (1,z), (8,a), (8,a), (8,a), (10,a), (10,a), (10,a), (10,b), (10,b), (10,b),
        }
    }
}

//@Debosmit Ray 比较的方式非常好，它简化了代码：

package AR;
class Node implements Comparable<Node> {
    public int frequency;
    public char value;
    public Node(int frequency, char value) {
        this.frequency = frequency;
        this.value = value;
    }
    @Override
    public int compareTo(Node o) {
        if (this.frequency > o.frequency) return 1;
        if (this.frequency < o.frequency) return -1;
        if (this.value > o.value) return 1;
        if (this.value < o.value) return -1;
        return 0;
    }
}
final class Main {
    static void swap(Node[] arr, int i, int j) {
        Node temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    static int partition(Node[] arr, int left, int right) {
        int i = left;
        Node pivot = arr[left++];
        while (left <= right) {
            while (left <= right && arr[left].compareTo(pivot) <= 0) left++;
            while (left <= right && arr[right].compareTo(pivot) > 0) right--;
            if (left > right)break;
            swap(arr, left++, right--);
        }
        swap(arr, i, right);
        return right;
    }
    public static void quickSort(Node arr[], int left, int right) {
        if (left >= right) return;
        int i = partition(arr, left, right);
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }
    public static void main(String[] args) {

        Node[] ns = new Node[]{new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(0, 'z'), new Node(1, 'z')};
        int n = ns.length;
        quickSort(ns, 0, n - 1);
        for (int i = 0; i < n; i++) {
            System.out.print("(" + ns[i].frequency + "," + ns[i].value + "), ");
            //(0,z), (1,b), (1,b), (1,b), (1,z), (8,a), (8,a), (8,a), (10,a), (10,a), (10,a), (10,b), (10,b), (10,b), 
        }
    }
}

//在Java中使用泛型：

package AR;

class Node implements Comparable<Node> {
    public int frequency;
    public char value;

    public Node(int frequency, char value) {
        this.frequency = frequency;
        this.value = value;
    }

    @Override
    public int compareTo(Node o) {
        if (this.frequency > o.frequency) return 1;
        if (this.frequency < o.frequency) return -1;
        if (this.value > o.value) return 1;
        if (this.value < o.value) return -1;
        return 0;
    }
}

final class Sort<T extends Comparable<T>> {
    void swap(T[] arr, int i, int j) {
        T temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    int partition(T[] arr, int left, int right) {
        int i = left;
        T pivot = arr[left++];
        while (left <= right) {
            while (left <= right && arr[left].compareTo(pivot) <= 0) left++;
            while (left <= right && arr[right].compareTo(pivot) > 0) right--;
            if (left > right) break;
            swap(arr, left++, right--);
        }
        swap(arr, i, right);
        return right;
    }

    public void quickSort(T arr[], int left, int right) {
        if (left >= right) return;
        int i = partition(arr, left, right);
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }

}

final class Main {
    public static void main(String[] args) {

        Node[] ns = new Node[]{new Node(10, 'a'), new Node(10, 'c'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(10, 'a'), new Node(10, 'b'), new Node(8, 'a'), new Node(1, 'b'), new Node(0, 'z'), new Node(1, 'z')};
        int n = ns.length;
        Sort cl = new Sort();
        cl.quickSort(ns, 0, n - 1);
        for (int i = 0; i < n; i++) {
            System.out.print("(" + ns[i].frequency + "," + ns[i].value + "), ");
            //(0,z), (1,b), (1,b), (1,b), (1,z), (8,a), (8,a), (8,a), (10,a), (10,a), (10,a), (10,b), (10,b), (10,c),
        }
    }
}

(java) 快速排序，先按数字对数字-字符对进行排序，然后按字符排序

(java) Quick sort to sort a number-char pair by number first, then char

java

sorting

algorithm

quicksort