Quicksort Algorithm Implementation in Java – 在Java中实现quicksort算法

最后修改: 2018年 10月 2日

中文/混合/英文(键盘快捷键：t)

1. Overview

1.概述

In this tutorial, we’ll explore the QuickSort algorithm in detail, focusing on its Java implementation.

在本教程中，我们将详细探讨QuickSort算法，重点介绍其Java实现。

We’ll also discuss its advantages and disadvantages and then analyze its time complexity.

我们还将讨论其优点和缺点，然后分析其时间的复杂性。

2. QuickSort Algorithm

2.快速排序算法

Quicksort is a sorting algorithm, which is leveraging the divide-and-conquer principle. It has an average O(n log n) complexity and it’s one of the most used sorting algorithms, especially for big data volumes.

Quicksort是一种排序算法，它利用了divid-and-conquer原则。它的平均复杂度为O(n log n)，它是最常用的排序算法之一，尤其是对于大数据量而言。

It’s important to remember that Quicksort isn’t a stable algorithm. A stable sorting algorithm is an algorithm where the elements with the same values appear in the same order in the sorted output as they appear in the input list.

重要的是要记住，Quicksort 并不是一种稳定的算法。稳定的排序算法是一种算法，具有相同值的元素在排序后的输出中出现的顺序与它们在输入列表中出现的顺序相同。

The input list is divided into two sub-lists by an element called pivot; one sub-list with elements less than the pivot and another one with elements greater than the pivot. This process repeats for each sub-list.

输入的列表被一个叫做pivot的元素分成两个子列表；一个子列表的元素小于pivot，另一个子列表的元素大于pivot。这个过程对每个子列表重复进行。

Finally, all sorted sub-lists merge to form the final output.

最后，所有排序的子列表合并形成最终输出。

2.1. Algorithm Steps

2.1.算法步骤

  1. We choose an element from the list, called the pivot. We’ll use it to divide the list into two sub-lists.
  2. We reorder all the elements around the pivot – the ones with smaller value are placed before it, and all the elements greater than the pivot after it. After this step, the pivot is in its final position. This is the important partition step.
  3. We apply the above steps recursively to both sub-lists on the left and right of the pivot.

As we can see, quicksort is naturally a recursive algorithm, like every divide and conquer approach.

正如我们所看到的，quicksort自然是一种递归算法，就像每一种划分和征服方法一样。

Let’s take a simple example in order to better understand this algorithm.

让我们举一个简单的例子，以便更好地理解这个算法。

Arr[] = {5, 9, 4, 6, 5, 3}
  1. Let’s suppose we pick 5 as the pivot for simplicity
  2. We’ll first put all elements less than 5 in the first position of the array: {3, 4, 5, 6, 5, 9}
  3. We’ll then repeat it for the left sub-array {3,4}, taking 3 as the pivot
  4. There are no elements less than 3
  5. We apply quicksort on the sub-array in the right of the pivot, i.e. {4}
  6. This sub-array consists of only one sorted element
  7. We continue with the right part of the original array, {6, 5, 9} until we get the final ordered array

2.2. Choosing the Optimal Pivot

2.2.选择最佳支点

The crucial point in QuickSort is to choose the best pivot. The middle element is, of course, the best, as it would divide the list into two equal sub-lists.

在QuickSort中，最关键的一点是要选择最佳的支点。当然，中间的元素是最好的，因为它将把列表分成两个相等的子列表。

But finding the middle element from an unordered list is difficult and time-consuming, that is why we take as pivot the first element, the last element, the median or any other random element.

但是从一个无序列表中找到中间元素是很困难的，也很耗时，这就是为什么我们把第一个元素、最后一个元素、中位数或任何其他随机元素作为支点。

3. Implementation in Java

3.用Java实现

The first method is quickSort() which takes as parameters the array to be sorted, the first and the last index. First, we check the indices and continue only if there are still elements to be sorted.

第一个方法是quickSort()，它把要排序的数组、第一个和最后一个索引作为参数。首先，我们检查索引，只有在仍有元素需要排序的情况下才继续。

We get the index of the sorted pivot and use it to recursively call partition() method with the same parameters as the quickSort() method, but with different indices:

我们得到排序枢轴的索引，并使用它来递归调用partition()方法，参数与quickSort()方法相同，但索引不同。

public 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);
    }
}

Let’s continue with the partition() method. For simplicity, this function takes the last element as the pivot. Then, checks each element and swaps it before the pivot if its value is smaller.

让我们继续讨论partition()方法。为了简单起见，这个函数将最后一个元素作为支点。然后，检查每个元素，如果它的值较小，就把它换到支点之前。

By the end of the partitioning, all elements less then the pivot are on the left of it and all elements greater then the pivot are on the right of it. The pivot is at its final sorted position and the function returns this position:

分区结束时，所有小于支点的元素都在它的左边，所有大于支点的元素都在它的右边。枢轴在其最终排序的位置，该函数返回这个位置。

private 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;
}

4. Algorithm Analysis

4.算法分析

4.1. Time Complexity

4.1.时间复杂度

In the best case, the algorithm will divide the list into two equal size sub-lists. So, the first iteration of the full n-sized list needs O(n). Sorting the remaining two sub-lists with n/2 elements takes 2*O(n/2) each. As a result, the QuickSort algorithm has the complexity of O(n log n).

在最好的情况下，该算法将把列表分成两个大小相等的子列表。因此，对完整的n大小的列表进行第一次迭代需要O(n)。对其余两个有n/2个元素的子列表进行排序需要2*O(n/2)个。因此，QuickSort算法的复杂度为O（n log n）。

In the worst case, the algorithm will select only one element in each iteration, so O(n) + O(n-1) + … + O(1), which is equal to O(n2).

在最坏的情况下，算法将在每次迭代中只选择一个元素，所以O(n)+O(n-1)+…+O(1)，等于O(n2)。

On the average QuickSort has O(n log n) complexity, making it suitable for big data volumes.

平均而言，QuickSort的复杂度O(n log n)，使其适用于大数据量。

4.2. QuickSort vs MergeSort

4.2.QuickSort vs MergeSort

Let’s discuss in which cases we should choose QuickSort over MergeSort.

让我们讨论一下在哪些情况下我们应该选择QuickSort而不是MergeSort。

Although both Quicksort and Mergesort have an average time complexity of O(n log n), Quicksort is the preferred algorithm, as it has an O(log(n)) space complexity. Mergesort, on the other hand, requires O(n) extra storage, which makes it quite expensive for arrays.

尽管Quicksort和Mergesort的平均时间复杂度都是O(n log n)，但Quicksort是首选算法，因为它的O(log(n))空间复杂性。另一方面，Mergesort需要O(n)额外的存储，这使得它对数组来说相当昂贵。

Quicksort requires to access different indices for its operations, but this access is not directly possible in linked lists, as there are no continuous blocks; therefore to access an element we have to iterate through each node from the beginning of the linked list. Also, Mergesort is implemented without extra space for LinkedLists.

Quicksort 要求为其操作访问不同的索引，但这种访问在链接列表中是不可能直接实现的，因为没有连续的块；因此要访问一个元素，我们必须从链接列表的开头遍历每个节点。另外，Mergesort的实现没有为LinkedLists.提供额外的空间。

In such case, overhead increases for Quicksort and Mergesort is generally preferred.

在这种情况下，一般倾向于选择增加开销的Quicksort和Mergesort。

5. Conclusion

5.结论

Quicksort is an elegant sorting algorithm that is very useful in most cases.

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

It’s generally an “in-place” algorithm, with the average time complexity of O(n log n).

它通常是一种 “就地 “算法，平均时间复杂度为O（n log n）。。

Another interesting point to mention is that Java’s Arrays.sort() method uses Quicksort for sorting arrays of primitives. The implementation uses two pivots and performs much better than our simple solution, that is why for production code it’s usually better to use library methods.

另一个值得一提的是，Java的Arrays.sort()方法使用Quicksort来对基元数组进行排序。该实现使用了两个枢轴，表现比我们的简单解决方案好得多，这就是为什么对于生产代码来说，通常使用库方法会更好。

As always, the code for the implementation of this algorithm can be found over on our GitHub repository.

一如既往，该算法的实现代码可以在我们的GitHub仓库上找到。