"这段代码是Java实现的快速排序算法,包括了主函数、获取中间值函数、快速排序函数以及递归版本的快速排序函数。" 快速排序是一种高效的排序算法,由C.A.R. Hoare在1960年提出。它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,然后分别对这两部分记录继续进行排序,以达到整个序列有序。 在提供的代码中,`quickSort` 是主排序函数,它首先调用 `quick(a)` 对数组 `a` 进行排序,然后打印排序后的数组。`quick` 函数实际上是一个空壳函数,它检查数组长度是否大于0,如果是,则调用 `_quickSort(a2, 0, a2.length - 1)` 进行实际的快速排序。 `getMiddle` 函数用于找到数组中值位于 `low` 和 `high` 之间的中间位置,它使用了“三数取中”的方法来确定枢轴元素,以避免最坏情况的发生。这个函数首先将 `low` 位置的元素暂存到 `tmp` 变量中,然后通过两个 while 循环将小于 `tmp` 的元素移动到 `low` 位置的左侧,大于 `tmp` 的元素移动到 `high` 位置的右侧,最后将 `tmp` 放回正确的位置并返回这个位置。 `_quickSort` 是快速排序的递归实现,它接收三个参数:待排序的数组 `list`,起始索引 `low` 和结束索引 `high`。如果 `low` 小于 `high`,则找到中间位置 `middle`,并分别对左右两部分递归调用 `_quickSort`,实现分治策略。 在主函数 `main` 中,没有实际执行排序操作,因为它是一个示例代码,注释表示是自动生成的方法 stub。 快速排序的平均时间复杂度为 O(n log n),在最坏情况下(输入数组已排序或逆序)时间复杂度为 O(n^2)。由于快速排序是原地排序,不需要额外的存储空间,因此空间复杂度为 O(log n)。快速排序在实际应用中表现优秀,是许多编程语言内置排序函数的基础。
//快速排序
public class Six {
int a[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51};
public void quickSort(){
quick(a);
for(int i=0;i<a.length;i++)
System.out.println(a[i]);
}
public int getMiddle(int[] list, int low, int high) {
int tmp = list[low]; //数组的第一个作为中轴
while (low < high) {
while (low < high && list[high] >= tmp) {
high--;
}
list[low] = list[high]; //比中轴小的记录移到低端
while (low < high && list[low] <= tmp) {
low++;
}
list[high] = list[low]; //比中轴大的记录移到高端
}
list[low] = tmp; //中轴记录到尾
return low; //返回中轴的位置
}
public void _quickSort(int[] list, int low, int high) {
if (low < high) {
int middle = getMiddle(list, low, high); //将list数组进行一分为二
_quickSort(list, low, middle - 1); //对低字表进行递归排序
_quickSort(list, middle + 1, high); //对高字表进行递归排序
下载后可阅读完整内容,剩余1页未读,立即下载
- 粉丝: 1
- 资源: 30
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- 李兴华Java基础教程:从入门到精通
- U盘与硬盘启动安装教程:从菜鸟到专家
- C++面试宝典:动态内存管理与继承解析
- C++ STL源码深度解析:专家级剖析与关键技术
- C/C++调用DOS命令实战指南
- 神经网络补偿的多传感器航迹融合技术
- GIS中的大地坐标系与椭球体解析
- 海思Hi3515 H.264编解码处理器用户手册
- Oracle基础练习题与解答
- 谷歌地球3D建筑筛选新流程详解
- CFO与CIO携手:数据管理与企业增值的战略
- Eclipse IDE基础教程:从入门到精通
- Shell脚本专家宝典:全面学习与资源指南
- Tomcat安装指南:附带JDK配置步骤
- NA3003A电子水准仪数据格式解析与转换研究
- 自动化专业英语词汇精华:必备术语集锦