1. 概述
在本教程中，我们将详细探讨快速排序算法，重点介绍其Java实现。
我们还将讨论它的优点和缺点，然后分析它的时间复杂度。
2. 快速排序算法
快速排序是一种利用分治原理的排序算法，它的平均复杂度为O(n log n)，是最常用的排序算法之一，尤其适用于大数据量的情况。
重要的是要记住，快速排序不是一种稳定的算法，稳定排序算法是指具有相同值的元素在排序输出中的出现顺序与它们在输入列表中的出现顺序相同。
输入列表被一个称为“枢轴”的元素分成两个子列表；一个子列表的元素小于枢轴，另一个子列表的元素大于枢轴；对每个子列表重复此过程。
最后，所有排序的子列表合并形成最终的输出。
2.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.2 选择最佳枢轴
快速排序的关键点是选择最佳枢轴，中间元素当然是最佳的，因为它会将列表分成两个相等的子列表。
但是从无序列表中找出中间元素非常困难而且耗时，这就是为什么我们以第一个元素、最后一个元素、中位数或任何其他随机元素作为枢轴。
3. 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;
}
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 快速排序与归并排序
让我们讨论一下在什么情况下应该选择快速排序而不是归并排序。
尽管快速排序和归并排序的平均时间复杂度都是O(n log n)，但快速排序是首选算法，因为它的空间复杂度为O(log(n)) 。另一方面，归并排序需要O(n)的额外存储空间，这对于数组来说非常昂贵。
快速排序需要访问不同的索引才能进行操作，但在链表中无法直接进行这种访问，因为没有连续的块；因此，要访问元素，我们必须从链表的开头遍历每个节点。此外，归并排序的实现不需要像链表那样占用额外的空间。
在这种情况下，通常优先选择快速排序和归并排序来增加开销。
5. 总结
快速排序是一种优雅的排序算法，在大多数情况下非常有用。
它通常是一种“就地”算法，平均时间复杂度为O(n log n)。
另一个值得一提的有趣之处是，Java的Arrays.sort()方法使用快速排序对基本数组进行排序。该实现使用两个枢轴，性能比我们的简单解决方案好得多，这就是为什么对于生产代码，通常最好使用库方法。
Post Directory
