Java 快速排序

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

一、快速排序的原理

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

  1. 选取一个基准元素,将待排序数组划分为左右两个子数组;

  2. 将比基准元素小的数都移到左子数组中,将比基准元素大的数都移到右子数组中;

  3. 对左右两个子数组递归执行上述操作,直到每个子数组只剩下一个元素为止。

具体来说,快速排序的过程如下:

  1. 首先选取待排序数组中一个元素作为基准元素,通常选择第一个元素或最后一个元素作为基准元素。

  2. 遍历数组,将小于基准元素的元素放到左边,大于等于基准元素的元素放到右边,此时数组被划分成了两个部分。

  3. 对左半部分和右半部分分别递归执行上述操作,直到排序完成。

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

二、快速排序的实现

在 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() 方法中,返回的是基准元素的位置,这个位置将用于快速排序算法的递归操作。

三、快速排序的时间复杂度

快速排序算法的时间复杂度主要取决于对数组进行划分的过程。在最坏情况下,如果每次划分都只能规模减少 1,那么快速排序的时间复杂度为 O(n^2),这种情况发生在数组已经排好序或基本排好序的情况下。

在平均情况下,假设每次划分可以将数组分成大小分别为 k 和 (n-k-1) 的两个子数组,那么快速排序的时间复杂度为 O(nlogn)。这是因为快速排序算法的递归深度为 logn,每一层的比较次数为 n,因此总体比较次数为 nlogn。

需要注意的是,快速排序算法的时间复杂度并不稳定,因为基准元素的选择对算法的效率有很大的影响。如果每次都选取最大或最小的元素作为基准元素,那么算法的时间复杂度将退化到 O(n^2)。因此,在实际应用中,我们通常会采用一些优化技巧来提高快速排序算法的效率,如随机选择基准元素、三数取中法等。

本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
THE END
分享
二维码
< <上一篇
下一篇>>