内容简介：深入浅出排序算法(3)-快速排序
概述
快速排序 与 归并排序 一样也是基于分治算法的 排序 算法.所以它的实现方法也与其他的分治算法一样,需要进行分解子任务,处理子任务,归并子任务这些步骤.
但 快速排序 与 归并排序 不同,它是一种 原地排序 算法(不需要额外的辅助数组),且 快速排序 不使用中间值来分解任务,而是使用 划分函数 .
算法过程
-
从数组中挑选出一个值,作为
基准值 k. -
重新排序序列, 将所有小于
k的值放到k前面,所有大于k的值放到k后面 (也可以理解为将数组a切分为两个子数组a[begin...k-1],a[k+1...end],其中前一个子数组都小于k,后一个子数组都大于k). -
递归地将两个子数组进行快速排序(递归到最底部时,子数组的大小是零或一,也就是已经排序好了.).
划分函数
划分函数 就是上述步骤中的第二步,它将数组根据 基准值 进行重排序.根据 基准值 选择的位置不同, 划分函数 也有不同的实现方法,不过其根本思想都是将小于 基准值 的值放到前面,大于 基准值 的值放到后面.
使用末尾元素作为基准值
// 使用末尾元素作为基准值来进行切分
private static int partitionUseEnd(Comparable[] a, int begin, int end) {
Comparable pivot = a[end]; // 基准值,切分后的数组应满足左边都小于基准,右边都大于基准
int i = begin - 1;
for (int j = begin; j < end; j++) {
// 如果j小于基准值则与i交换
if (less(a[j], pivot)) {
i++;
swap(a, i, j);
}
}
// 将基准值交换到正确的位置上
int pivotLocation = i + 1;
swap(a, pivotLocation, end);
return pivotLocation;
}
使用首元素作为基准值
// 使用首元素作为基准值来进行切分
private static int partitionUseBegin(Comparable[] a, int begin, int end) {
Comparable pivot = a[begin];
int i = begin;
int j = end + 1;
while (true) {
// 从左向右扫描,直到找出一个大于等于基准的值
while (less(a[++i], pivot)) {
if (i >= end)
break;
}
// 从右向左扫描,直到找出一个小于等于基准的值
while (less(pivot, a[--j])) {
if (j <= begin)
break;
}
// 如果指针i与j发生碰撞则结束循环
if (i >= j)
break;
// 将左边大于小于基准的值与右边小于等于基准的值进行交换
swap(a, i, j);
}
// 将基准值交换到正确的位置上
swap(a, begin, j);
return j;
}
代码实现
了解了 划分函数 的实现,剩下就只需要递归地调用 快速排序 不断地分解子任务即可.
注意, 快速排序 与 归并排序 不同,它不需要进行 归并 (划分后就已经是有序的了),并且是先进行 划分函数 ,再分解任务.
public static void sort(Comparable[] a) {
sort(a, 0, a.length - 1);
}
private static void sort(Comparable[] a, int begin, int end) {
if (begin >= end)
return;
int k = partitionUseEnd(a, begin, end);
sort(a, begin, k - 1);
sort(a, k + 1, end);
}
本文作者为 SylvanasSun(sylvanassun_xtz@163.com) ,转载请务必指明原文链接.
以上所述就是小编给大家介绍的《深入浅出排序算法(3)-快速排序》，希望对大家有所帮助，如果大家有任何疑问请给我留言，小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持！
猜你喜欢:
- 算法之常见排序算法-冒泡排序、归并排序、快速排序
- 排序算法之冒泡排序改进算法
- 快速排序算法，C语言快速排序算法深入剖析
- 排序算法下——桶排序、计数排序和基数排序
- 数据结构和算法面试题系列—排序算法之快速排序
- 数据结构和算法面试题系列—排序算法之基础排序
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
