高效的快速排序分治算法

JavaJavaBeginner
立即练习

💡 本教程由 AI 辅助翻译自英文原版。如需查看原文,您可以 切换至英文原版

简介

QuickSort 是一种分治(Divide-and-Conquer)排序算法。它的工作原理是从数组中选择一个「基准」(pivot)元素,然后将其他元素根据是否小于或大于基准元素划分为两个子数组。接着,递归地对子数组进行排序。QuickSort 的平均时间复杂度为 O(n log n)。需要注意的是,QuickSort 不是一种稳定的排序算法,也就是说,相等元素的相对位置可能不会保持不变。


Skills Graph

%%%%{init: {'theme':'neutral'}}%%%% flowchart RL java(("`Java`")) -.-> java/BasicSyntaxGroup(["`Basic Syntax`"]) java(("`Java`")) -.-> java/DataStructuresGroup(["`Data Structures`"]) java(("`Java`")) -.-> java/ProgrammingTechniquesGroup(["`Programming Techniques`"]) java(("`Java`")) -.-> java/ObjectOrientedandAdvancedConceptsGroup(["`Object-Oriented and Advanced Concepts`"]) java(("`Java`")) -.-> java/SystemandDataProcessingGroup(["`System and Data Processing`"]) java/BasicSyntaxGroup -.-> java/operators("`Operators`") java/BasicSyntaxGroup -.-> java/variables("`Variables`") java/DataStructuresGroup -.-> java/arrays("`Arrays`") java/DataStructuresGroup -.-> java/arrays_methods("`Arrays Methods`") java/DataStructuresGroup -.-> java/sorting("`Sorting`") java/ProgrammingTechniquesGroup -.-> java/recursion("`Recursion`") java/ObjectOrientedandAdvancedConceptsGroup -.-> java/packages_api("`Packages / API`") java/SystemandDataProcessingGroup -.-> java/math_methods("`Math Methods`") subgraph Lab Skills java/operators -.-> lab-117980{{"`高效的快速排序分治算法`"}} java/variables -.-> lab-117980{{"`高效的快速排序分治算法`"}} java/arrays -.-> lab-117980{{"`高效的快速排序分治算法`"}} java/arrays_methods -.-> lab-117980{{"`高效的快速排序分治算法`"}} java/sorting -.-> lab-117980{{"`高效的快速排序分治算法`"}} java/recursion -.-> lab-117980{{"`高效的快速排序分治算法`"}} java/packages_api -.-> lab-117980{{"`高效的快速排序分治算法`"}} java/math_methods -.-> lab-117980{{"`高效的快速排序分治算法`"}} end

导入 Arrays 类

在这一步中,你需要导入 java.util.Arrays 类。这个类包含了一些用于操作数组的方法,这些方法将用于将 int 数组转换为 String

import java.util.Arrays;

定义 partition() 方法

定义一个名为 partition() 的辅助方法。partition() 方法将接收一个数组 arr、一个起始索引 low 和一个结束索引 high 作为输入。partition() 方法会选择一个元素作为基准(pivot),并将数组中的元素进行划分,使得所有小于基准元素的元素位于基准的左侧,所有大于基准元素的元素位于基准的右侧。基准元素将被放置在其正确的位置。

partition() 方法将返回划分后的元素的索引。划分后的元素是基准元素被放置的位置。

public static int partition(int[] arr, int low, int high) {
    // 选择基准元素
    int pivot = arr[high];
    int i = (low - 1); // 较小元素的索引,表示当前找到的基准的正确位置

    for (int j = low; j <= high - 1; j++) {
        // 如果当前元素小于或等于基准
        if (arr[j] <= pivot) {
            i++; // 增加较小元素的索引
            // 交换 arr[i] 和 arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // 交换 arr[i + 1] 和 arr[high]
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

    return i + 1; // 返回划分索引
}

定义 quicksort() 方法

定义一个名为 quicksort() 的排序方法。quicksort() 方法将接收一个数组 arr、一个起始索引 low 和一个结束索引 high 作为输入。quicksort() 方法会递归地对 arr[] 数组进行排序。

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        // pi 是划分索引,arr[p] 现在位于正确的位置
        int pi = partition(arr, low, high);

        // 递归地对划分前后的元素进行排序
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

创建并分配整数数组

创建并分配需要排序的整数数组到 arr 字段。

int[] arr = {7, 9, 1, 2, 10, 15, 6};

实现快速排序

调用 quickSort() 方法,将 arr 字段作为输入,同时传入数组的起始索引和结束索引。使用 Arrays.toString(arr) 方法对数组进行排序并显示结果。

quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr));

使用多个数组进行测试

使用具有不同特征的数组测试你的快速排序实现。

int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
int[] arr3 = {1};
int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};

quickSort(arr1, 0, arr1.length-1);
quickSort(arr2, 0, arr2.length-1);
quickSort(arr3, 0, arr3.length-1);
quickSort(arr4, 0, arr4.length-1);

System.out.println(Arrays.toString(arr1));
System.out.println(Arrays.toString(arr2));
System.out.println(Arrays.toString(arr3));
System.out.println(Arrays.toString(arr4));

随机选择基准值

在这一步中,我们需要在每次迭代中随机选择基准值,以避免最坏情况的发生。为此,我们将更新 partition() 方法,并将以下代码行:

int pivot = arr[high];

替换为以下代码行:

int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
int pivot = arr[pivotIndex];
arr[pivotIndex] = arr[high];
arr[high] = pivot;

使用随机基准值进行测试

使用随机基准值测试你的快速排序实现。

int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};

quickSort(arr5, 0, arr5.length-1);
quickSort(arr6, 0, arr6.length-1);
quickSort(arr7, 0, arr7.length-1);
quickSort(arr8, 0, arr8.length-1);

System.out.println(Arrays.toString(arr5));
System.out.println(Arrays.toString(arr6));
System.out.println(Arrays.toString(arr7));
System.out.println(Arrays.toString(arr8));

处理边界情况

在这一步中,我们将覆盖快速排序可以处理的边界情况。将这些边界情况定义为整数数组。

int[] arr9 = {};
int[] arr10 = {1, 1, 1, 1};
int[] arr11 = {1};
quickSort(arr9, 0, arr9.length-1);
quickSort(arr10, 0, arr10.length-1);
quickSort(arr11, 0, arr11.length-1);

System.out.println(Arrays.toString(arr9));
System.out.println(Arrays.toString(arr10));
System.out.println(Arrays.toString(arr11));

完整代码

以下是 Java 实验中的快速排序完整代码。

import java.util.Arrays;

public class QuickSort {

    public static int partition(int[] arr, int low, int high) {
        int pivotIndex = low + (int)(Math.random() * ((high - low) + 1));
        int pivot = arr[pivotIndex];
        arr[pivotIndex] = arr[high];
        arr[high] = pivot;
        int i = low - 1;
        for (int j = low; j <= high - 1; ++j) {
            if (arr[j] <= pivot) {
                ++i;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
        int temp = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp;
        return i + 1;
    }

    public static void quickSort(int[] arr, int low, int high) {
        if (low >= high) {
            return;
        }
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }

    public static void main(String[] args) {
        System.out.println("Quick Sort Implementation in Java\n-----------------------");
        int[] arr = {7, 9, 1, 2, 10, 15, 6};
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));

        int[] arr1 = {7, 9, 1, 2, 10, 15, 6};
        int[] arr2 = {1, 2, 3, 4, 5, 6, 7, 8};
        int[] arr3 = {1};
        int[] arr4 = {-5, 2,-1, 0, 11, 20, -20};

        quickSort(arr1, 0, arr1.length-1);
        quickSort(arr2, 0, arr2.length-1);
        quickSort(arr3, 0, arr3.length-1);
        quickSort(arr4, 0, arr4.length-1);

        System.out.println(Arrays.toString(arr1));
        System.out.println(Arrays.toString(arr2));
        System.out.println(Arrays.toString(arr3));
        System.out.println(Arrays.toString(arr4));

        int[] arr5 = {7, 4, 6, 10, 8, 5, 1, 3, 2, 9};
        int[] arr6 = {4, 5, 10, 3, 8, 2, 1, 7, 6, 9};
        int[] arr7 = {100, 200, 33, 1, 3, 400, 45, 67, 80, 13};
        int[] arr8 = {12, 34, 32, 14, 55, 37, 23, 9};

        quickSort(arr5, 0, arr5.length-1);
        quickSort(arr6, 0, arr6.length-1);
        quickSort(arr7, 0, arr7.length-1);
        quickSort(arr8, 0, arr8.length-1);

        System.out.println(Arrays.toString(arr5));
        System.out.println(Arrays.toString(arr6));
        System.out.println(Arrays.toString(arr7));
        System.out.println(Arrays.toString(arr8));

        int[] arr9 = {};
        int[] arr10 = {1, 1, 1, 1};
        int[] arr11 = {1};
        quickSort(arr9, 0, arr9.length-1);
        quickSort(arr10, 0, arr10.length-1);
        quickSort(arr11, 0, arr11.length-1);

        System.out.println(Arrays.toString(arr9));
        System.out.println(Arrays.toString(arr10));
        System.out.println(Arrays.toString(arr11));
    }
}

总结

本实验提供了在 Java 中实现快速排序算法的分步指南。我们了解到,选择基准值是快速排序中的关键步骤,而不同的基准值选择技术会影响算法的性能。快速排序最适合用于排序大量数据。快速排序的最坏时间复杂度为 O(N^2),而其平均和最佳时间复杂度为 O(NLogN)。

您可能感兴趣的其他 Java 教程