Java快速排序算法的实现

在本教程中，我们将详细探讨 QuickSort 算法，重点是它的 Java 实现。我们还将讨论它的优缺点，然后分析它的时间复杂度。

快速排序算法

快速排序是一种排序算法，它利用了分而治之的原则。 它的平均复杂度为O(n log n)，是最常用的排序算法之一，尤其是对于大数据量。

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

输入列表被称为枢轴的元素分为两个子列表;一个子列表的元素小于枢轴，另一个子列表的元素大于枢轴。这个过程对每个子列表重复。

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

1.算法步骤

我们从列表中选择一个元素，称为枢轴。我们将使用它将列表分成两个子列表。

我们对枢轴周围的所有元素重新排序——值较小的元素放在它之前，所有大于枢轴的元素放在它之后。在这一步之后，枢轴处于其最终位置。这是重要的分区步骤。

我们将上述步骤递归地应用于枢轴左侧和右侧的两个子列表。

正如我们所见，快速排序自然是一种递归算法，就像所有分而治之的方法一样。

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

Arr[] = {5, 9, 4, 6, 5, 3}

为简单起见，假设我们选择 5 作为支点

我们首先将所有小于 5 的元素放在数组的第一个位置：{3, 4, 5, 6, 5, 9}

然后我们将对左子数组 {3,4} 重复它，以 3 作为枢轴

没有小于3的元素

我们对枢轴右侧的子数组应用快速排序，即{4}

该子数组仅包含一个已排序元素

我们继续原始数组的右边部分，{6,5,9}，直到我们得到最终的有序数组

2.选择最佳枢轴

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

但是从无序列表中找到中间元素既困难又耗时，这就是为什么我们将第一个元素、最后一个元素、中值或任何其他随机元素作为枢轴。

Java实现

第一个方法是quickSort()，它将要排序的数组、第一个和最后一个索引作为参数。首先，我们检查索引并仅在仍有要排序的元素时继续。

我们得到排序后的枢轴的索引，并使用它递归调用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);
    }
}

让我们继续partition()方法。为简单起见，此函数将最后一个元素作为枢轴。然后，检查每个元素，如果它的值更小，则在枢轴之前交换它。

到分区结束时，所有小于枢轴的元素都在它的左侧，所有大于枢轴的元素都在它的右侧。枢轴位于其最终排序位置，函数返回此位置：

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

算法分析

1.时间复杂度

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

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

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

2.快速排序与合并排序

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

尽管 Quicksort 和 Mergesort 的平均时间复杂度为O(n log n)，但 Quicksort 是首选算法，因为它的空间复杂度为O(log(n)) 。另一方面，合并排序需要O(n)额外的存储空间，这使得数组非常昂贵。

快速排序的操作需要访问不同的索引，但是这种访问在链表中是不可能的，因为没有连续的块;因此，要访问一个元素，我们必须从链表的开头遍历每个节点。此外，Mergesort 的实现无需为LinkedLists 提供额外空间。

在这种情况下，通常首选快速排序和合并排序的开销增加。