使用Java进行快速排序练习

问题描述 投票：0回答：4

这是我第一次尝试使用 Java 进行快速排序，我也在寻找一些有用的批评，以了解如何使我的代码更好地显示 Hoare 的列表。我需要添加一些特定内容才能显示结果吗？

import java.util.ArrayList;

public class Quicksort<E extends Comparable<E>> {
    
    // Quicksort using Hoare's partition
    public static <E extends Comparable<E>> void quicksortHoare(ArrayList<E> list, int l, int r) {
        // Sorting the given ArrayList (of generic type E) in descending order      
        if (l < r) {
            int pivot = partitionHoare(list, l, r);
            quicksortHoare(list, l, pivot);
            quicksortHoare(list, pivot + 1, r);
        }                   
    }   
    
    // Hoare's partition (always select the first element as the pivot)
    public static <E extends Comparable<E>> int partitionHoare(ArrayList<E> list, int l, int r) {
        E pivot = list.get(l);
        int i = l - 1;
        int j = r + 1;

        while (true) {
            do {
                i++;
            } while (list.get(i).compareTo(pivot) > 0);

            do {
                j--;
            } while (list.get(j).compareTo(pivot) < 0);

            if (i >= j) {
                return j;
            }

            E temp = list.get(i);
            list.set(i, list.get(j));
            list.set(j, temp);
        }
                                
    }

    
    public static void main(String[] args) {
        int[] test1 = {3, 5, 2, 4, 1, 8, 7, 6, 9};  

        //  Printed the list
        ArrayList<Integer> list1 = new ArrayList<>();
        for (int num : test1) {
            list1.add(num);
        }
        System.out.println("*** Test 1 ***");
        System.out.println("Original list: " + list1);
        System.out.println("Hoare's quicksort: " + test1);
        
    }
}
java quicksort
4个回答
0
投票

要将数组打印为可读文本，您可以使用 Arrays.toString 方法。

System.out.println("Hoare's quicksort: " + Arrays.toString(test1));
0
投票

您使用 Hoare 分区方案实现的 QuickSort 算法看起来不错。但是，为了使用 Hoare 的快速排序显示排序列表，您需要使用适当的参数实际调用 

quicksortHoare()
方法，然后打印排序列表。

这是代码的更新版本，进行了必要的更改。 在此更新的代码中，我们调用 

quicksortHoare()
方法，传递 
list1
、起始索引 
0
和结束索引 
list1.size() - 1
。对列表进行排序后，我们使用以下命令打印排序后的列表：
System.out.println("Hoare's quicksort: " + list1);

现在，当您运行程序时，它将显示原始列表和使用霍尔快速排序算法排序的列表。

这是上述解释的代码版本：

import java.util.ArrayList;

public class Quicksort<E extends Comparable<E>> {

    public static <E extends Comparable<E>> void quicksortHoare(ArrayList<E> list, int l, int r) {
        if (l < r) {
            int pivot = partitionHoare(list, l, r);
            quicksortHoare(list, l, pivot);
            quicksortHoare(list, pivot + 1, r);
        }
    }

    // Hoare's partition (always select the first element as the pivot)
    public static <E extends Comparable<E>> int partitionHoare(ArrayList<E> list, int l, int r) {
        E pivot = list.get(l);
        int i = l - 1;
        int j = r + 1;

        while (true) {
            do {
                i++;
            } while (list.get(i).compareTo(pivot) < 0);

            do {
                j--;
            } while (list.get(j).compareTo(pivot) > 0);

            if (i >= j) {
                return j;
            }

            E temp = list.get(i);
            list.set(i, list.get(j));
            list.set(j, temp);
        }
    }

    public static void main(String[] args) {
        int[] test1 = {3, 5, 2, 4, 1, 8, 7, 6, 9};

        // Convert the array to ArrayList
        ArrayList<Integer> list1 = new ArrayList<>();
        for (int num : test1) {
            list1.add(num);
        }

        System.out.println("*** Test 1 ***");
        System.out.println("Original list: " + list1);

        // Sort the list using Hoare's quicksort
        quicksortHoare(list1, 0, list1.size() - 1);

        System.out.println("Hoare's quicksort: " + list1);
    }
}
0
投票

除非您需要使用数组，否则使用 

List
会稍微简化代码，这也更容易显示。

  • 使用 
    List.of()
    创建不可变的项目列表。
  • 然后将其作为参数传递给 
    new ArrayList<>()
    以创建用于排序的可变列表。
public static void main(String[] args) {
        List<Integer> list1 = new ArrayList<>(List.of(3, 5, 2, 4, 1, 8, 7, 6, 9));
        System.out.println("*** Test 1 ***");
        System.out.println("Original list: " + list1);
        quicksortHoare(list1, list1.size() - 1);
        System.out.println("Hoare's quicksort: " + list1);
    }

请注意，在您的主例程中，将实现的接口传递给其接口类型被认为是最佳实践。因此，对于 

quicksortHoare
和 
partitionHoare
的第一个参数，使用 
List<E> list
而不是 
ArrayList<E> list
。这将允许您的方法接受实现 
List
接口的任何类型的列表。

由于您的方法是静态的，因此无需将主类声明为通用类。只需使用 

<E extends Comparable<? super E>>
作为每个方法上接受的类型。无需在这里解释该声明的目的，只需查看 stackoverflow 上的这个问题即可。

最后，你的

do/while loops
没有任何问题。但您也可以仅使用 
while loops
，如下所示。请注意使用索引的 
prefix increment/decrement
before。

 while (list.get(++i).compareTo(pivot) < 0);
 while (list.get(--j).compareTo(pivot) > 0);
0
投票
public class QuickLomuto{
public void quickSort(int a[], int p, int r) {

    /*
    p -> low
    r -> high
    q -> pivot
    */
    if(p < r) {
        int q = partition(a, p, r);
        quickSort(a, p, q-1);
        quickSort(a, q+1, r);
    }
}

public int partition(int a[], int p, int r) {

    /*
    p -> low
    r -> high
    x -> pivot
    */
    int x= a[r];  //(1) ...pivot = a[high]
    int i= p-1;   //(2) ...range  i -> a[i] < x

    for(int j=p; j<r; j++) {

        if(a[j] <= x) {
            i++;
            swap(a, i, j);  //...since (2) ...j should be in range(i, p)
        }
    }
    
    // swap (a[i+1], a[r])   
    //... put x i.e. 'pivot' in the correct position  ... since (1)
    
    swap(a, (i+1), r);  //(3) ... (i+1) -> pivot's correct place
    return i+1;
}

public int[] swap(int[] array, int x, int  y){
    int temp = array[x];
    array[x] = array[y];
    array[y] = temp;
    return array;
}

public static void main(String[] args) {

    int a[] = {100, 10, 5, 20, 80, 30, 70, 50, 15, 90, 40, 60, 9};
    
    int n = a.length;
    int low = 0;
    int high = n - 1;

    QuickLomuto lomuto = new QuickLomuto();
    lomuto.quickSort(a, low, high);

    System.out.println("quick sort with Lomuto partitioning");

    for(int x : a){
        System.out.println(x);
    }
}
}
最新问题
© www.soinside.com 2019 - 2024. All rights reserved.