Java快速排序算法分析 基本思想:通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分关键字小,则分别对这两部分继续进行排序,直到整个序列有序。
把整个序列看做一个数组,把第零个位置看做中轴,和最后一个比,如果比它小交换,比它大不做任何处理;交换了以后再和小的那端比,比它小不交换,比他大交换。这样循环往复,一趟排序完成,左边就是比中轴小的,右边就是比中轴大的,然后再用分治法,分别对这两个独立的数组进行排序。
public int getMiddle(Integer[] 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(Integer[] 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); //对高字表进行递归排序 } } public void quick(Integer[] str) { if (str.length > 0) { //查看数组是否为空 _quickSort(str, 0, str.length - 1); } } 编写测试方法: public class TestMain { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub Integer[] list={34,3,53,2,23,7,14,10}; QuicSort qs=new QuicSort(); qs.quick(list); for(int i=0;i<list.length;i++){ System.out.print(list[i]+" "); } System.out.println(); } }
相关推荐
用java对常用排序算法进行分析与实现.包含: 插入排序 直接插入排序、希尔排序 • 选择排序 简单选择排序、堆排序 • 交换排序 冒泡排序、快速排序 • 归并排序 • 基数排序
排序算法,JAVA中的快速排序,交换排序,冒泡排序,选择排序等算法的分析
(1)对起泡排序、直接排序、简单选择排序、快速排序、希尔排序、堆排序算法进行比较; (2)待排序表的表长不小于100,表中数据随机产生,至少用5组不同数据作比较,比较指标有:关键字参加比较次数和关键字的移动次数...
选择排序、冒泡排序、归并排序、快速排序、插入排序的算法原理。不同排序算法时间效率的经验分析方法,验证理论分析与经验分析的一致性。
此为一个利用Java语言编写的排序分析程序,程序中统计了各种排序算法(冒泡排序、选择排序、插入排序、希尔排序、快速排序、堆排序、归并排序、基数排序)的分析,ppt中包含各种排序算法的分析,附上动画演示(来自...
包括所有算法分析设计的实验(java快速排序。归并排序,分治算法,回溯算法,n后问题)
一个算法设计与分析的实验报告,比较归并排序与快速排序的时间差异,这里采用在一个java程序中对随机生成的任意个数分别进行两种方法的排序并记录各自的时间,最后得出结论。 本实验报告附代码以及详细解释
主要介绍了Java基于分治法实现的快速排序算法,结合实例形式分析了java基于分治法的快速排序相关实现技巧,代码中备有较为详细的注释说明便于理解,需要的朋友可以参考下
主要介绍了JAVA版排序算法之快速排序,结合实例形式分析了基于java版的遍历、递归实现快速排序功能的具体步骤与操作技巧,需要的朋友可以参考下
最省时间的是确定型算法,其次是随机基准快速排序算法,最后是随机化输入快速排序算法;后面两个算法较之确定型算法要费时的原因是:(1)随机选取基准花费了一些时间,(2)随机化输入是将原来数组打乱花费了一些时间。...
七大排序算法精彩讲解+详细代码+思路分析+最佳优化!七大排序算法精彩讲解+详细代码+思路分析+最佳优化!七大排序算法精彩讲解+详细代码+思路分析+最佳优化!七大排序算法精彩讲解+详细代码+思路分析+最佳优化!七大...
1. 算法思想 选取一个基准值,将待排序数据分为左(小于基准值)右(大于基准值)两个区间,然后对两个分区的数据进行同样的循环操作,最后便可得到一组有序数据。...因此快速排序的平均时间复杂度为$O(n^
Java语言的快速排序优化算法实现 算法思想: 通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程...
现有股票数据XX条,无序...注意:实现排序算法可以使用冒泡排序,插入排序,堆排序,选择排序,快速排序等,任何的排序算法都是可以被接受的,但不能使用系统库中自带的排序函数,如List.sort() 或者 Arrays.sort()。
排序7.1 预备知识7.2 插入排序7.2.1 算法7.2.2 插入排序的分析7.3 一些简单...快速排序的分析7.7.6 选择问题的线性期望时间算法7.8 排序算法的一般下界7.9 桶式排序7.10 外部排序7.10.1 为什么需要一些新的算法7.10.2 ...
快速排序、归并排序、希尔排序、冒泡排序、选择排序、插入排序等8中排序方式原理分析java实现
中文名: 数据结构与算法分析_Java语言描述(第2版) 作者: 韦斯 译者: 冯舜玺 图书分类: 软件 资源格式: PDF 版本: 扫描版 出版社: 机械工业出版社 书号: ISBN:9787111231837 发行时间: 2009年01月01日 地区: 大陆 ...
排序7.1 预备知识7.2 插入排序7.2.1 算法7.2.2 插入排序的分析7.3 一些简单...快速排序的分析7.7.6 选择问题的线性期望时间算法7.8 排序算法的一般下界7.9 桶式排序7.10 外部排序7.10.1 为什么需要一些新的算法7.10.2 ...
内容概要:这是本人在复习数据结构排序算法所写的markdown文档,对各个算法进行了比较,分析其稳定性。通过对六种排序算法的介绍,了解其中的核心原理,手写源码过程中对其代码进行注释讲解。 适用人群:本人文档是...
这是一些常用的排序算法思想的分析和JAVA实现,还有具体的图解实例,简单明了,一看就会!