文章目录
- Java实现快速排序
- 快速排序原理
- 快速排序一次划分图文演示过程
- 整个快速排序的过程
- 具体Java代码实现
- 简结快速排序的性能
Java实现快速排序
冲鸭,装上涡轮增鸭,开始学习快速排序算法吧!(快排也是一个递归过程噢)
快速排序原理
快速排序(Quick Sort)又被称为分区排序,它的基本思想是:在待排序文件中任选一个记录(称为基准记录),以它的排序码为基准值,将排序码比它小的记录都放到它的前面,排序码比它大的记录都放到它的后面,至此,该基准记录就找到了排序的最终位置,同时将文件划分成前、后两个区。在两个区上用同样的方法继续划分,直到每个区中最多只有一个记录,排序完成。在快速排序过程中,比较和交换是从数组的两端向中间进行的,使得排序码较小或较大的记录一次就能够交换到数组的前面或后面,记录的每一次移动距离都较远,因而使得总的比较和移动次数较小。快速排序是对起泡排序的一种改进,它是目前所有的内部排序方法中速度最快的一种。
快速排序一次划分图文演示过程
建立如下整z型数组:
int[] array = new int[]{46,36,96,26,86,16,76,-17};
- 设置两个数组索引,分别为低位索引 low 和高位索引 high,初始值分别为:low = 0 ;high = array.length-1;
- 选取array[low]作为第一次划分的基准元素;
- 若 low < high,从high位置开始向前搜索数组元素小于基准元素的数组元素索引,如果找到了,就将array[high]移动到array[low]的位置;然后从low的位置开始向后搜索数组元素大于基准元素的数组元素索引,如果找到了,就将array[low]移动到array[high]]的位置;重复上诉操作,直到低位索引和高位索引相遇,即low == high(即不满足条件low < high),此时就找到了基准元素的最终排序位置low,因为这个时候,low位置上的原值已经被移走,需要将基准放到该位置上,这个位置也是基准的最终排序位置。如此一次划分过程完毕。
接下来,脑海中想象这么一个事情(算是有点抽象吧):想象这样的一个坑位——“▢”,将坑位放在数组索引0的位置,这时候索引0位置的位置没有了元素,就是这样的一个"▢"(在代码中debug看值,实际上是有的,这里就想象没有)。你想象好了以后,它就长成下面表1那个样子。
接下来要开始啦!
坑位在array[0],如表1所示:
结合表1,从高位索引开始向前搜索比基准46小的元素,找到的元素是-17;将array[7]移动到array[0],坑位转到索引7,如表2所示:
结合表2,从低位索引开始向后搜索比基准46大的元素,找到的元素是96;将array[2]移动到array[7],坑位转到索引2,如表3所示:
结合表3,从高位索引开始向前搜索比基准46小的元素,找到的元素是16;将array[5]移动到array[2],坑位转到索引5,如表4所示:
结合表4,从低位索引开始向后搜索比基准46大的元素,找到的元素是86;将array[4]移动到array[5],坑位转到索引4,如表5所示:
结合表5,从高位索引开始向前搜索比基准46小的元素,但是没找到,两个索引相遇了,即是 low == high,如表6所示:
此时一次划分就此结束了,基准也应该到位了,low索引就是基准最终的排序位置,即array[4] = 46,与此同时,一个大的数据区间也划分成为了两个小的数据子区间,左边子区间的数都比基准小,右边子区间都比基准大,如表7所示:
注意:在方法体中需要返回基准的索引,即 low!
整个快速排序的过程
具体Java代码实现
QuickSort类:
public class QuickSort {
public static void sort(int[] array, int low, int high) {
if (low < high) {
int part = partition(array, low, high);
sort(array, low, part - 1);
sort(array, part + 1, high);
}
}
private static int partition(int[] array, int low, int high) {
int benchmark = array[low];
while (low < high) {
while ((low < high) && array[high] >= benchmark) {
high--;
}
if (low < high) {
array[low] = array[high];
}
while ((low < high) && (array[low] <= benchmark)) {
low++;
}
if (low < high) {
array[high] = array[low];
}
}
array[low] = benchmark;
return low;
}
}
TestMain类:
import java.util.Arrays;
public class TestMain {
public static void main(String[] args) {
int[] array = new int[]{46,36,96,26,86,16,76,-17};
int low = 0;
int high = array.length-1;
System.out.print("排序前:");
System.out.println(Arrays.toString(array));
QuickSort.sort(array,low,high);
System.out.print("排序后:");
System.out.println(Arrays.toString(array));
}
}
运行结果如下:
排序前:[46, 36, 96, 26, 86, 16, 76, -17]
排序后:[-17, 16, 26, 36, 46, 76, 86, 96]
简结快速排序的性能
- 时间效率:快速排序的平均时间复杂度是O(nlog2n),当n较大时,通常快速排序被认为在同数量级的排序方法中平均性能是最好的;
- 空间效率:快速排序是递归过程,每层递归调用时的指针和参数均要用栈来存放,递归调用的深度与对应的二叉树深度是一样的。因此最好的空间复杂度是O(nlog2n),最坏的空间复杂度是O(n),平均空间复杂度是O(nlog2n);
- 稳定性:快速排序是一个不稳定的排序方法。
关于快排的学习就到这里啦!大家可以多画画一次划分的过程便于理解快排的原理。
关于代码方面如果不是很好理解可以先去了解了解递归算法,同时结合着Debug,一步一步的执行代码,看看各个变量是如何变化的,就很容易理解快排啦!
~和ChenSeventeen一起记录学习、成长过程吧!
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)