1.概述

在本文中,我们将详细探讨快速排序(Quicksort)算法,当然,重点是Java实现。

我们还会讨论其优点和缺点,然后分析其时间复杂度。

2. 快速排序算法

快速排序是一种排序算法,它利用了分而治之的原理。

在平均状况下, 它的复杂度O(n log n),并且是最常用的排序算法之一,尤其是对于大数据量。

需要注意的是,快速排序算法是一种不稳定的算法。也就是不能保证具有相同值的元素在排序输出中的出现顺序与在输入列表中出现的顺序相同。

输入列表由一个称为基准值(pivot)的元素分为两个子列表。一个子列表的元素小于基准值,另一个子列表的元素大于基准值。对每个子列表重复此过程。

最后,将排排序好的子列表合并以形成最终输出。

2.1 算法步骤

  1. 我们从列表中选择一个称为基准值的元素。我们将使用它将列表分为两个子列表。

  2. 我们对基准值周围的所有元素进行重新排序, 值较小的元素将放置在其前面,而所有大于基准值的元素将放置在其后面。

  3. 我们将上述步骤递归应用于数基准值左侧和右侧的两个子列表。

快速排序自然是一种递归算法,和每种分而治之的方法一样。

我们这里举一个简单的例子。下面是文字说明,喜欢看动画的同学可以参考这里

比如我们有一个数组。

Arr[] = {5, 9, 4, 6, 5, 3}
  1. 假设我们选择5作为基准值
  2. 我们首先将所有小于5的元素放在数组的第一位置:{3,4,5,6,5,9}
  3. 然后,我们以3作为基准值,对左侧的子数组{3,4}重复此操作
  4. 没有少于3个元素
  5. 我们将快速排序应用于基准值(这里是3)右侧的子数组,即{4}
  6. 该子数组仅包含一个已排序元素
  7. 我们继续处理第一次分割后右边部分的数组{6,5,9}的,直到获得最终的有序数组

2.2 选择基准值

快速排序中的关键点是选择最佳基准值。当然,中间元素是最好的,因为它将把列表分为两个相等的子列表。

但是从无序列表中找到中间元素既困难又费时,这就是为什么我们将第一个元素,最后一个元素,中位数或任何其他随机元素作为基准值的原因。

3. Java实现

我们这里通过两个方法来实现。

第一个方法是quickSort(),它将需要要排序的数组,第一个和最后一个索引作为参数。

首先,我们检查索引判断是否需要排序。

我们获取排序后的基准值的索引,并使用它以与partition()方法相同的参数递归调用quickSort()方法,但具体的索引是不同的:

public static void quickSort(int arr[], int begin, int end) {
    if (begin < end) {
        int partitionIndex = partition(arr, begin, end);
 
        quickSort(arr, begin, partitionIndex-1);
        quickSort(arr, partitionIndex+1, end);
    }
}

让我们来看一下partition()方法,为简单起见,此函数将最后一个元素作为基准值。

然后,检查每个元素,如果其值较小,就交换到基准值的前面。

分区结束后,所有小于基准值的元素都位于其左侧,而所有大于基准值的元素都位于其右侧。基准值位于其最终排序的位置,并且函数返回该位置索引。

private static int partition(int arr[], int begin, int end) {
    int pivot = arr[end];
    int i = (begin-1);
 
    for (int j = begin; j < end; j++) {
        if (arr[j] <= pivot) {
            i++;
 
            int swapTemp = arr[i];
            arr[i] = arr[j];
            arr[j] = swapTemp;
        }
    }
 
    int swapTemp = arr[i+1];
    arr[i+1] = arr[end];
    arr[end] = swapTemp;
 
    return i+1;
}

我们来测试一下:

@Test
public void test_QuickSort() {
  int[] actual = { 5, 1, 6, 3, 2, 4 };
  int[] expected = { 1, 2, 3, 4, 5, 6 };
  Quicksort.quickSort(actual, 0, actual.length - 1);
  assertArrayEquals(expected, actual);
}

4.算法分析

4.1 时间复杂度

在最佳情况下,该算法会将列表分为两个相等大小的子列表。

因此,n个元素的列表的第一次迭代需要O(n)。用n / 2个元素对其余两个子列表进行排序,每个子列表需要2 * O(n / 2)。因此,快速排序算法的复杂度为O(n log n)

在最坏的情况下,该算法在每次迭代中只会选择一个元素,因此,O(n)+ O(n-1)+…+ O(1)等于O(n2)是平方)。

快速排序的平均复杂度为O(n log n),因此比较适合大数据量的排序。

4.2 快速排序 VS 归并排序

让我们讨论一下在哪种情况下我们应该选择快速排序,那种情况下选择归并排序(MergeSort)。

尽管快速排序和归并排序的平均时间复杂度都为O(n log n),但快速排序是首选算法,因为它的空间复杂度是O(log(n))。而 归并排序的空间复杂度O(n)所以推荐使用快速排序算法

但是,快速排序需要访问操作的不同索引,如果需要排序的是链表的话 ,由于不是连续的,无法直接通过索引访问,要访问元素,我们必须从链表的开头开始遍历每个节点。

而,对于归并排序来说,因为是连续的访问,因此对于排序的是链表的时候,推荐使用归并排序。

5.总结

快速排序是一种优雅的排序算法,在大多数情况下非常有用。

还有一点,,Java的Arrays.sort()也是使用快速排序对数组进行排序的,不过使用了两个基准值,比我们上面的演示代性能要好的多,所以,一般情况下,最好使用Java的类库方法。

与往常一样,可以在GitHub上获得代码示例。