我们知道Java在排序上分别使用了快速排序和合并排序。下面我们就研究一下这两种排序。
本节先分析快速排序,我们以Int数组的排序为例。
Java的排序算法是这样子的:
方法声明如下:
sort1(int x[], int off, int len)
对于数组个数小于7的情况下,使用插入排序:
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); //交换 x[j]和x[j-1]
return;
}
如果大于7的话,则使用快速排序。在教科书上,快速排序一般使用的是最后一个元素作为分割元素。
而Java的 实现上,在寻找分割值时,则使用的下面的算法:
//
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];
如果长度小于等于40的话,去 最左边,最右边和中间的元素的中间数作为分割元素;
如果大于40的话,分割元素,则去9个元素的中间数。
找到中间元素后,将数组分成:v*
(<v)* (>v)* v*这样的形式。
int a = off, b = a, c = off + len - 1, d
= c;
//a 起始位置,c结束位置
//b 起始位置变量,d结束位置变量
while(true)
{
while (b <= c && x[b] <= v) {
if
(x[b] == v)
swap(x, a++, b);
b++;
}
while (c >= b && x[c] >= v) {
if
(x[c] == v)
swap(x, c, d--);
c--;
}
if (b > c)
break;
swap(x, b++, c--);
}
上述的算法和教科书的快速排序算法是一样的。分别从两端大于v的数,和小于v的数。如果找到,交换一下,例如[1239----------3987]的数组,如果分割元素是4,则会变成[1233-----9887]。如果数等于分割元素,则会放到开头或者结尾,最终形成v* (<v)*
(>v)* v* 的数据形式。
接下来则是对数据进行调换,形成(<v)*v*(>v)*的结构:
int
s, n = off + len;
s
= Math.min(a-off, b-a ); vecswap(x, off, b-s, s);
s
= Math.min(d-c, n-d-1); vecswap(x, b, n-s, s);
b是中间位置。vecswap是对象量进行的调换。a-off边是等于v的元素个数。b-a表示<v的个数。s表示要交换的个数。然后交换一下即可。
接下来递归调用快排算法:
如上,b-a表示<v的个数,现在小于v的数都已经挪到了左侧,只需调用一下排序,对前b-a的数据进行排序和后d-c的数据进行排序即可。
if
((s = b-a) > 1)
sort1(x, off, s);
if
((s = d-c) > 1)
sort1(x, n-s, s);
}
总结:
-
对于小于7的元素使用插入排序;
- 选择中间元素有学问;
-
对等于v的数据进行的特殊处理。
分享到:
相关推荐
### Java实现快速排序算法知识点详解 #### 一、快速排序的基本概念 快速排序是一种非常高效且广泛应用的排序算法,最早由C.A.R. Hoare在1960年提出。其核心思想是采用分治法策略,通过一次排序操作将待排序的数据...
在Java中实现这些排序算法,通常会用到`Arrays`类中的`sort()`方法,以及自定义的比较器`Comparator`。通过编写不同的比较逻辑,可以实现各种排序需求。此外,理解这些算法的工作原理,有助于在实际开发中选择最合适...
在Java中,这些排序算法都可以用代码实现,可以通过`java.util.Arrays.sort()`方法使用内置的快速排序或归并排序,也可以自定义排序逻辑。在`AllSort`这个压缩包中,可能包含了这八种排序算法的Java实现代码,通过...
基准关键字的选取是决定快速排序算法的关键,常用的基准关键字的选取方式包括: * 三者取中:将序列首、尾和中间位置上的记录进行比较,选择三者中值作为基准关键字。 * 取left和right之间的一个随机数,用n[m]作为...
总的来说,Java中的直接插入排序算法是一个直观易懂的排序方法,虽然在效率上不敌更高级的排序算法,但它在理解和实现上相对简单,对于初学者来说是很好的学习材料。通过阅读和实践这个源代码,你可以深入理解排序...
本篇文章将深入探讨八大常见的排序算法,并提供它们在Java语言中的具体实现。这八大排序算法包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序以及计数排序。 1. 冒泡排序(Bubble Sort):...
在`springboot-quick`这个压缩包文件中,可能包含了一个使用SpringBoot构建的示例项目,演示了如何在实际应用中集成和使用快速排序算法。这个项目可以作为一个学习和实践快速排序的好资源,同时展示了如何将算法应用...
了解和掌握这些排序算法的原理和实现方式,不仅有助于编写高效的排序代码,还能帮助我们在面对实际问题时选择最合适的解决方案。在学习过程中,可以结合实际例子,通过编写代码来加深理解,同时通过分析时间复杂度和...
这里我们将深入探讨几种常见的Java排序算法,包括冒泡排序、堆排序、插入排序、合并排序、快速排序以及选择排序和希尔排序。 1. **冒泡排序**:冒泡排序是最基础的排序算法之一,它通过重复遍历待排序数组,比较...
Java提供了`java.util.Arrays.sort()`方法,内部实现了TimSort,这是一种混合排序算法,结合了插入排序和归并排序的优点,能在很多情况下提供良好的性能。 总的来说,理解并熟练掌握不同的排序算法对于提升程序的...
Java排序算法实现主要涉及到两种经典的算法:冒泡排序和选择排序。这两种算法都是基于比较的排序方法,适用于小规模或教学目的的数据排序。 **冒泡排序(Bubble Sort)** 是一种简单直观的排序算法,其核心思想是...
例如,在有大量元素需要排序的情况下,可以使用高效的快速排序算法;在需要稳定的排序结果时,可以使用归并排序或插入排序等稳定排序算法。 在上述代码中,使用了 ServerInfoComparator 类来实现自定义的比较器,该...
- Java排序算法包可能包含了上述的多种排序算法实现,用户可以根据数据规模、数据特点以及性能要求选择合适的算法。 - 如果需要排序的对象有复杂的比较规则,自定义`Comparator`是一个很好的解决方案。 总的来说...
在Java编程语言中,排序算法是数据结构与算法...在实际编程中,Java集合框架中的`Collections.sort()`和`Arrays.sort()`方法已经为我们提供了排序功能,但了解底层的排序算法原理,有助于我们更好地理解和优化代码。
在编程领域,排序算法是计算机科学中的核心概念,特别是在数据结构和算法分析中。...在实际开发中,还可以考虑结合Java的内置排序函数`Arrays.sort()`,它使用了一种高效的混合排序算法,可以处理各种数据类型。
它可以让我们深刻理解为什么我们需要高效的排序算法,比如快速排序、归并排序、堆排序等,它们在时间复杂度上有着显著的优势。同时,BozoSort也提醒我们,在编程实践中,应优先考虑算法的效率,尤其是在处理大数据时...
同时,现代Java库(如`Arrays.sort()`方法)通常使用更高级的排序算法,如TimSort,它结合了稳定的排序和插入排序的特性,能在大多数情况下提供良好的性能。 总的来说,理解和掌握这些基础排序算法是每个Java程序员...
在Java中,我们可以使用ArrayUtils、Collections等工具类进行排序,例如`Arrays.sort()`和`Collections.sort()`,它们内部使用了高效的排序算法,如TimSort,是混合排序算法,结合了插入排序和归并排序的优点,对小...
### 常用排序算法分析与实现(Java版) #### 插入排序 **1. 直接插入排序** 直接插入排序是一种简单的排序方法,它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并...
在Java中实现这些排序算法时,通常会使用数组作为数据结构,通过定义辅助方法如`swap()`来进行元素交换,`printArray()`用于输出排序结果。例如,`bubbleSort()`函数展示了冒泡排序的具体实现,根据参数`sortType`...