位置：首页-资讯-后端开发

Java 快速排序

2023-09-06 18:20

短信预约 -IT技能 免费直播动态提醒

快速排序是一种常用的基于比较的排序算法，其时间复杂度为 O(nlogn)，并且具有稳定性和广泛的应用场景。本文将全面详细的讲解一下 Java 中快速排序算法的原理、实现以及时间复杂度等问题。

一、快速排序的原理

快速排序是一种分治思想的排序算法，其基本原理可以概括为以下三步：

选取一个基准元素，将待排序数组划分为左右两个子数组；
将比基准元素小的数都移到左子数组中，将比基准元素大的数都移到右子数组中；
对左右两个子数组递归执行上述操作，直到每个子数组只剩下一个元素为止。

具体来说，快速排序的过程如下：

首先选取待排序数组中一个元素作为基准元素，通常选择第一个元素或最后一个元素作为基准元素。
遍历数组，将小于基准元素的元素放到左边，大于等于基准元素的元素放到右边，此时数组被划分成了两个部分。
对左半部分和右半部分分别递归执行上述操作，直到排序完成。

需要注意的是，在遍历数组时，一般采用双指针法来实现。具体来说，我们使用一个左指针指向数组的第一个元素，用一个右指针指向数组的最后一个元素，然后从左到右依次遍历数组中的元素，如果当前元素小于基准元素，就将它和左指针所指的元素交换，然后将左指针向右移动一位；如果当前元素大于等于基准元素，就将它和右指针所指的元素交换，然后将右指针向左移动一位。重复上述操作直到左指针和右指针相遇为止。

二、快速排序的实现

在 Java 中，我们可以使用以下代码来实现快速排序算法：

public static void quickSort(int[] arr, int left, int right) {    if (left < right) { // 当数组只有一个元素时结束递归        int partitionIndex = partition(arr, left, right); // 对数组进行划分，获取基准元素位置        quickSort(arr, left, partitionIndex - 1); // 对左子数组递归执行快速排序        quickSort(arr, partitionIndex + 1, right); // 对右子数组递归执行快速排序    }}public static int partition(int[] arr, int left, int right) {    int pivot = arr[left]; // 将数组的第一个元素设置为基准元素    int i = left; // 初始化左指针    int j = right; // 初始化右指针    while (i < j) { // 当左指针和右指针没有相遇时循环        while (i < j && arr[j] >= pivot) { // 右指针从右向左遍历，找到第一个小于基准元素的元素            j--;        }        if (i < j) { // 如果左指针和右指针没有相遇，将右指针所指的元素赋值给左指针所指的位置            arr[i] = arr[j];            i++;        }        while (i < j && arr[i] < pivot) { // 左指针从左向右遍历，找到第一个大于等于基准元素的元素            i++;        }        if (i < j) { // 如果左指针和右指针没有相遇，将左指针所指的元素赋值给右指针所指的位置            arr[j] = arr[i];            j--;        }    }    arr[i] = pivot; // 将基准元素放到最终位置    return i; // 返回基准元素的位置}

在上述代码中，quickSort() 方法是快速排序算法的入口，它采用递归的方式对左右两个子数组进行排序。partition() 方法则是用来对数组进行划分的，它使用双指针法来实现。

具体来说，我们首先将数组的第一个元素作为基准元素 pivot，然后初始化左指针 i 和右指针 j。接着，我们先让右指针 j 从右向左遍历数组，找到第一个小于基准元素的元素，并将其赋值给左指针所指的位置；然后让左指针 i 从左向右遍历数组，找到第一个大于等于基准元素的元素，并将其赋值给右指针所指的位置。重复上述操作直到左指针和右指针相遇。

最后，将基准元素 pivot 放到最终位置，即左指针所指的位置，这样就完成了对数组的一次划分。在 partition() 方法中，返回的是基准元素的位置，这个位置将用于快速排序算法的递归操作。