首页 > Java > java教程 > 了解快速排序算法(附Java示例)

了解快速排序算法(附Java示例)

Mary-Kate Olsen
发布: 2025-01-18 02:05:16
原创
448 人浏览过

QuickSort 算法详解:高效的排序利器

快速排序 (QuickSort) 是一种基于分治策略的高效排序算法。分治法将问题分解成更小的子问题,分别解决这些子问题,然后组合子问题的解得到最终解。在快速排序中,数组通过选择一个分区元素来划分,该元素决定数组的分割点。在划分之前,分区元素的位置会重新排列,使其位于大于它的元素之前,小于它的元素之后。左右子数组将以这种方式递归划分,直到每个子数组只包含一个元素,此时数组已排序。

快速排序工作原理

让我们以升序排序以下数组为例:

Understanding Quick Sort Algorithm (with Examples in Java)

步骤 1:选择枢轴元素

我们选择最后一个元素作为枢轴:

Understanding Quick Sort Algorithm (with Examples in Java)

步骤 2:重新排列枢轴元素

我们将枢轴元素放置在其大于它的元素之前,小于它的元素之后。为此,我们将遍历数组,并将枢轴与它之前的每个元素进行比较。如果找到一个大于枢轴的元素,我们为它创建一个第二个指针:

Understanding Quick Sort Algorithm (with Examples in Java)

如果找到一个小于枢轴的元素,我们将它与第二个指针交换:

Understanding Quick Sort Algorithm (with Examples in Java)

重复此过程,将下一个大于枢轴的元素设置为第二个指针,如果找到小于枢轴的元素则进行交换:

Understanding Quick Sort Algorithm (with Examples in Java)

继续此过程直到到达数组的末尾:

Understanding Quick Sort Algorithm (with Examples in Java)

完成元素比较后,小于枢轴的元素已移动到右侧,然后我们将枢轴与第二个指针交换:

Understanding Quick Sort Algorithm (with Examples in Java)

步骤 3:划分数组

根据分区索引划分数组。如果我们将数组表示为 arr[start..end],则通过分区划分数组,可以得到左子数组 arr[start..partitionIndex-1] 和右子数组 arr[partitionIndex 1..end]

Understanding Quick Sort Algorithm (with Examples in Java)

以这种方式继续划分子数组,直到每个子数组只包含一个元素:

Understanding Quick Sort Algorithm (with Examples in Java)

此时,数组已排序。

Understanding Quick Sort Algorithm (with Examples in Java)

快速排序代码实现

<code class="language-java">import java.util.Arrays;

public class QuickSortTest {
    public static void main(String[] args){
        int[] arr = {8, 6, 2, 3, 9, 4};
        System.out.println("未排序数组: " + Arrays.toString(arr));
        quickSort(arr, 0, arr.length-1);
        System.out.println("已排序数组: " + Arrays.toString(arr));
    }

    public static int partition(int[] arr, int start, int end){
        // 将最后一个元素设置为枢轴
        int pivot = arr[end];
        // 创建指向下一个较大元素的指针
        int secondPointer = start-1;

        // 将小于枢轴的元素移动到枢轴左侧
        for (int i = start; i < end; i++){
            if (arr[i] < pivot){
                secondPointer++;
                // 交换元素
                int temp = arr[secondPointer];
                arr[secondPointer] = arr[i];
                arr[i] = temp;
            }
        }
        // 将枢轴与第二个指针交换
        int temp = arr[secondPointer+1];
        arr[secondPointer+1] = arr[end];
        arr[end] = temp;
        // 返回分区索引
        return secondPointer+1;
    }

    public static void quickSort(int[] arr, int start, int end){
        if (start < end){
            // 找到分区索引
            int partitionIndex = partition(arr, start, end);
            // 递归调用快速排序
            quickSort(arr, start, partitionIndex-1);
            quickSort(arr, partitionIndex+1, end);
        }
    }
}</code>
登录后复制

代码解读

quickSort 方法:首先调用 partition 方法将数组分成两个子数组,然后递归调用 quickSort 对左右子数组进行排序。这个过程持续进行,直到所有子数组都只包含一个元素,此时数组已排序。

partition 方法:负责将数组分成两个子数组。它首先设置枢轴和下一个较大元素的指针,然后遍历数组,将小于枢轴的元素移动到左侧。之后,它将枢轴与第二个指针交换,并返回分区位置。

运行以上代码,控制台将输出以下内容:

未排序数组: [8, 6, 2, 3, 9, 4] 已排序数组: [2, 3, 4, 6, 8, 9]

时间复杂度

最佳情况 (O(n log n)):当枢轴每次都将数组分成两个几乎相等的部分时,就会出现最佳情况。

平均情况 (O(n log n)):在平均情况下,枢轴将数组分成两个不相等的部分,但递归深度和比较次数仍然与 n log n 成正比。

最坏情况 (O(n²)):当枢轴始终将数组分成非常不相等的部分(例如,一部分只有一个元素,另一部分有 n-1 个元素)时,就会出现最坏情况。例如,当排序一个逆序数组时,并且枢轴选择不佳时,就会发生这种情况。

空间复杂度 (O(log n)):快速排序通常就地实现,不需要额外的数组。

以上是了解快速排序算法(附Java示例)的详细内容。更多信息请关注PHP中文网其他相关文章!

来源:php.cn
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
作者最新文章
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板