十大经典排序算法之快速排序
2024-06-16 本文已影响0人
趣丸技术
快速排序(Quick Sort)采用的是分治思想，即在一个无序的序列中选取一个任意的基准元素pivot，利用pivot将待排序的序列分成两部分，前面部分元素均小于或等于基准元素，后面部分均大于或等于基准元素，然后采用递归的方法分别对前后两部分重复上述操作，直到将无序序列排列成有序序列。
算法特性
- 稳定性
快速排序是一种不稳定的排序算法。
- 时间复杂度
快速排序的时间复杂度在最坏情况下是O(n^2)，平均的时间复杂度是O(N*logN)。
- 空间复杂度
快速排序是一种原地排序算法，不需要额外的空间进行排序。因此，快速排序的空间复杂度为O(1)。
算法步骤
快速排序算法通过多次比较和交换来实现排序，其流程如下：
1、首先设定一个基准值，通过该基准值将数组分成左右两部分。
2、将大于或等于基准值的数据集中到数组右边，小于基准值的数据集中到数组的左边。此时，左边部分中各元素都小于基准值，而右边部分中各元素都大于或等于基准值。
3、然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个基准值，将该部分数据分成左右两部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。
4、重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当左、右两个部分各数据排序完成后，整个数组的排序也就完成了。
动画演示
快速排序.gif
代码实现
Java代码:
private static int[] quickSort(int[] array, int left, int right) {
if (left < right) {
int partitionIndex = partition(array, left, right);
quickSort(array, left, partitionIndex - 1);
quickSort(array, partitionIndex + 1, right);
}
return array;
}
private static int partition(int[] array, int left, int right) {
// 设定基准值
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (array[i] < array[pivot]) {
swap(array, i, index);
index ++;
}
}
swap(array, pivot, index - 1);
return index - 1;
}
private static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
推荐阅读
•【技术教程】JRebel激活指南：让你的Java开发更高效！
