排序算法 #6 快速排序
16lz
2021-01-22
01
动画演示
定义变量b,指向数组中的第一个元素;定义变量e指向数组的末尾元素。
接着,定义变量i,指向变量b所指向的元素;定义变量j,指向变量b所指向元素的下一个元素。
我们将变量b所指向的元素4作为基准元素。
接着,我们将变量j所指向的元素值和变量b所指向的基准元素值进行比较,有三种情况:
变量j所指向的元素值大于基准元素的值;
变量j所指向的元素值小于基准元素的值;
- 变量j所指向的元素值等于基准元素的值。
在这里变量j指向的元素5,大于基准元素4,因此变量j向后移动一位,继续考察下一个元素。
此时,变量j所指向的元素3,小于基准元素4,因此,将变量i向后移动一位。
接着,交换变量i和变量j所指向的元素。
我们将变量j继续向后移动一位,考察下一个元素。此时,变量j所指向的元素4等于基准元素4,不做操作。
继续将变量j向后移动一位,考察下一个元素,同样这时变量j指向的元素7大于基准元素,不做操作。
在变量j指向数组的末尾时,接下来要做的就是将基准元素4和变量i所指向的元素3进行位置交换。
完成交换之后,变量i所指向的元素4前面的元素都是小于基准元素的,而其后面的元素都是大于等于基准元素的。
对于小于基准元素的部分和大于等于基准元素的部分,分别重复上述过程,直到每一部分为空或只包含一个元素时快速排序结束。
02代码实现
public static void sort(int[] arr) {
quickSort(arr, 0, arr.length - 1);
}
public static void quickSort(int[] arr, int b, int e) {
if (b >= e) {
return;
}
int p = partition(arr, b, e);
// 对基准元素的前面元素进行快排
quickSort(arr, 0, p - 1);
// 对基准元素的后面元素进行快排
quickSort(arr, p + 1, e);
}
private static int partition(int[] arr, int b, int e) {
// 基准元素
int basicValue = arr[b];
int i = b;
for(int j = b + 1; j <= e; j++) {
// 当前考察的元素小于基准元素
if (arr[j] - basicValue < 0) {
// 变量i先加1
i++;
// 变量i和变量j所指向的元素进行位置交换
swap(arr, i, j);
}
}
// 变量i所指向的元素和基准元素进行位置交换
swap(arr, b, i);
// 返回基准元素所在的位置
return i;
}
private static void swap(int[] arr, int m, int n) {
int temp = arr[m];
arr[m] = arr[n];
arr[n] = temp;
更多相关文章
- (美团)巧用数组下标,轻轻松松找出所有元素
- 超详细!详解一道高频算法题:数组中的第 K 个最大元素
- Ansible 之 外部变量文件调用
- 动画:面试必刷之二维数组中查找一个元素
- 前 K 个高频元素告诉你桶排序有啥用
- Python办公自动化|光速对比并提取两份Word/Excel中的不同元素
- 动画: 快速排序 | 如何求第 K 大元素?
- 动画:「变量提升」引发的一场"血"案 !
- PHP 超全局变量之$_FILES详解