`
robertliudeqiang
  • 浏览: 123311 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

java源码中的数据结构 - 插入排序,快速排序 (附可供调试的源码)

阅读更多
java源码是学习数据结构的好材料,研究这些代码,能够更好的理解算法。

准备工作
java.util.Arrays是一个典型的工具类(构造函数修饰符为private),该类提供了一组sort1()方法,分别用来可以比较的基本类型进行排序。
private static void sort1(int x[], int off, int len)
private static void sort1(long x[], int off, int len)
private static void sort1(byte x[], int off, int len)
private static void sort1(float x[], int off, int len)
...

仔细比较发现,这组方法除了传入数组的参数类型不同,方法内的代码几乎完全相同,产生这个问题的主要原因是jdk没有为基本类型提供泛型支持,考虑到效率问题,装箱在这里显然是不合适的。

在Arrays类中包含大量重复代码的方法不只sort1,还有swap,binarySearch等,不过这里确实也没有别的好方法,只能希望以后的版本编译器能够提供支持。

另外,这里还有一个需要说明的地方是double和float的比较,为了处理类似NaN, 0.0这样的情况,正确的比较方法应该是:
Double.compare(double1, doble2);
Float.compare(float1, float2);


而在Arrays类中,为了保证sort1的一致性,对double和float类型数组,先使用sort2方法把NaN, 0.0这样的数移到数组最后,再使用sort1方法对剩余部分排序,这部分功能可以参考sort2方法的源码。
private static void sort2(double a[], int fromIndex, int toIndex)
private static void sort2(float a[], int fromIndex, int toIndex)


算法分析
准备工作做完了,现在开始对算法本身进行分析,简便起见,只分析下面这个方法:
private static void sort1(int x[], int off, int len)


1 数组长度小于7时,使用插入排序
	// The part of code in sort1 method
	// Insertion sort on smallest arrays
	if (len < 7) {
		for (int i = off; i < len + off; i++)
			for (int j = i; j > off && x[j - 1] > x[j]; j--)
				swap(x, j, j - 1);
		return;
	}
说明:
印象中有本书说len<20时插入排序比较快,jdk选择的是len<7。
swap()方法用来交换数组中的两个变量。

2 数组长度大于等于7时,使用快速排序
快速排序的原理是首先选取一个元素v,然后把比v大和比v小的元素分别移到v的两边,最后再对v两边的数组分别进行排序。
这里使用的是平衡快排,即选择合适的v,使v尽量位于数组中间值,看看jdk怎么做的:
	// The part of code in sort1 method
	// Choose a partition element, v
	int m = off + (len >> 1); // Small arrays, middle element
	if (len > 7) {
		int l = off;
		int n = off + len - 1;
		if (len > 40) { // Big arrays, pseudomedian of 9
			int s = len / 8;
			l = med3(x, l, l + s, l + 2 * s);
			m = med3(x, m - s, m, m + s);
			n = med3(x, n - 2 * s, n - s, n);
		}
		m = med3(x, l, m, n); // Mid-size, med of 3
	}
	int v = x[m];

从代码可以看出,jdk分了三种情况:
2.1 len = 7
v取的是数组中间元素(x[3])

2.2 len > 7 && len <= 40
看看med3方法:
   
private static int med3(int x[], int a, int b, int c) {
	return (x[a] < x[b] ? (x[b] < x[c] ? b : x[a] < x[c] ? c : a) :
		(x[b] > x[c] ? b : x[a] > x[c] ? c : a));
}

也就是取数组中三个位置值中处于中间的值。
所以这种情况v的取值是: 首,尾,中间元素中处于中间的值。

2.3 len > 40
仔细分析代码,可以发现,jdk取数组0, n/8, n/4, 3n/8, n/2, 5n/8, 3n/4, 7n/8, n位置的元素值进行运算,这个算法设计的非常巧妙  ,首先步长s=len/8,向右移三位就行了,速度快;其次,通过步长从数组中得到9个点,每3个为一组进行med3元素,产生的3个点再进行一次med3运算,就得到了v值,这样保证v的值尽可能的处于中间的值。

总结:
jdk中sort1排序使用了两种排序算法,并且根据数组的长度做了相应的优化,这是一个工程中比较实用的算法(看注释可以找到算法来源)。另外,附件是从jdk源码中拷贝出来的相关源码,有兴趣的可以自己研究。
0
0
分享到:
评论
3 楼 coffeesweet 2010-03-17  
thank you
2 楼 robertliudeqiang 2010-03-15  
off你可以理解为:

输入一个数组,并不是对整个数组排序,而是从第off位开始,len长度个元素。
1 楼 coffeesweet 2010-03-15  
能问下sort1里的变量off是干什么的吗?

相关推荐

    java源码包---java 源码 大量 实例

    像坐标控制、旋转矩阵、定时器、生成图像、数据初始化、矩阵乘法、坐标旋转、判断是否是顺时针方向排列、鼠标按下、放开时的动作等,都可在本源码中得以体现。 Java编写的显示器显示模式检测程序 2个目标文件 内容...

    Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法

    Java代码-排序-直接插入排序、希尔排序、直接选择排序、冒泡排序、堆排序、快速排序、归并排序中部分排序以及算法-贪心法,大家可以将源码下载下来进行学习,附带着注释和解释,有不理解的可以找博主一起探讨,共同...

    数据结构-基于Java的算法和数据结构源码.zip

    数据结构-基于Java的算法和数据结构源码.zip数据结构-基于Java的算法和数据结构源码.zip数据结构-基于Java的算法和数据结构源码.zip

    数据结构 折半插入排序

    数据结构 c语言 折半插入排序 源码

    java数据结构源码

    下面将详细介绍这些数据结构及其在Java中的应用。 1. **数组**(Array):数组是最基础的数据结构,它是一个存储固定数量同类型元素的集合。在Java中,数组可以通过声明数组变量并初始化来创建。数组提供了随机访问...

    易语言数据的排序源码,易语言数据的排序2源码,易语言数据的排序1

    - 源码中的"数据的排序1.0"可能是指实现了某种特定排序算法的程序模块,如自定义的快速排序或者归并排序等。 - "记录显示"和"排序显示"通常指的是在排序完成后,将排序结果以可视化的形式展示出来,这可能涉及到...

    数据结构与算法(Java语言版)含有源码

    在Java中,这些数据结构可以通过内置类(如ArrayList、LinkedList)或自定义类来实现。理解数据结构可以帮助我们选择合适的方式来处理特定问题,例如,使用栈处理回溯问题,用哈希表实现快速查找。 2. 算法:算法是...

    java--JTable排序实例源码

    这个实例“java--JTable排序实例源码”提供了一个功能,允许用户通过点击表头对`JTable`中的数据进行排序。这种功能在处理大量数据时非常实用,使得用户能轻松地查看和理解数据。 首先,我们来深入了解一下`JTable`...

    mysql-connector-java-5.1.37jar包和源码

    在本案例中,"mysql-connector-java-5.1.37.jar" 是一个特定版本的MySQL JDBC驱动程序,发布于2016年,属于较旧但仍然广泛使用的版本。这个jar包是Java开发者用来连接到MySQL服务器的关键组件。 首先,我们需要了解...

    Java数据结构源码

    - **图**:用于表示节点之间的关系,Java中并没有内置的图数据结构,但可以通过自定义类实现。 2. **算法**: - **排序算法**:冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等,不同的排序算法有...

    数据结构8中算法排序,配源码和动画演示.rar

    4. 快速排序(Quick Sort):快速排序采用分治策略,选取一个“基准”值,将数组分为两部分,一部分小于基准,另一部分大于基准,然后对这两部分递归地进行快速排序。平均时间复杂度为O(n log n),最坏情况为O(n^2)...

    基于Java的实例源码-数据结构提取器.zip

    本实例源码“基于Java的实例源码-数据结构提取器”旨在帮助开发者理解如何在Java中处理和提取数据结构,这对于提升程序的效率和可维护性至关重要。 数据结构是计算机科学的基础,它定义了数据的组织方式,如数组、...

    java数据结构和算法(第二版)[含源码]

    5. **排序和搜索算法**:冒泡排序、插入排序、选择排序、快速排序、归并排序、堆排序等排序算法,以及线性搜索、二分搜索等搜索算法,都是编程面试和实际项目中常见的知识点。学习它们的原理和Java实现,可以提升...

    数据结构与算法分析C++描述(附源码)

    在C++中,常用算法包括排序(如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等)、搜索(如顺序搜索、二分搜索)、图算法(如最短路径算法Dijkstra、Floyd-Warshall、Bellman-Ford)和动态规划等。...

    java源码结构-ds-source-code-examples:Java中的数据结构和算法实现

    - **排序算法**:如冒泡排序、选择排序、插入排序、快速排序、归并排序和堆排序,用于对数据进行有序排列。 - **查找算法**:如顺序查找、二分查找、哈希查找,用于在数据集中寻找特定元素。 - **递归算法**:...

    小甲鱼数据结构与算法课件+源码.zip_-baijiahao_expresschs_once4l3_小甲鱼 ppt_小甲鱼数据结

    典型的算法有排序(冒泡排序、选择排序、插入排序、快速排序、归并排序等)、搜索(线性搜索、二分搜索)、图的遍历(深度优先搜索DFS和广度优先搜索BFS)等。理解算法的时间复杂度和空间复杂度对于优化代码性能至关...

    java数据结构第二版(附源码和applet演示)

    通过学习本书,读者不仅可以掌握Java中数据结构的实现,还能培养解决实际问题的能力,为后续的软件开发打下坚实的基础。无论是初学者还是经验丰富的开发者,都能从《Java数据结构第二版》中受益匪浅。

    java汉字笔画排序源码

    在Java中,可以使用`java.util.Comparator`接口自定义比较规则,根据笔画数对`List&lt;String&gt;`类型的汉字列表进行排序。此外,`java.text.Normalizer`类可以帮助处理Unicode编码,确保笔画计算的准确性。 总的来说,...

    数据结构JAVA版及源码

    Java中提供了多种内置排序方法,如Arrays.sort(),但也可以自定义排序算法,如冒泡排序、选择排序、插入排序、快速排序和归并排序等。 10. **搜索算法**:搜索算法用于在数据结构中查找特定元素。线性搜索是最基础...

    Java数据结构与算法书中源码

    3. **排序算法** - `Sort.java`可能包含了各种排序算法的实现,如冒泡排序、选择排序、插入排序、快速排序、归并排序、堆排序等。排序算法在处理大量数据时至关重要,能有效提高数据处理速度。 4. **二叉搜索树...

Global site tag (gtag.js) - Google Analytics