我们知道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.util.Arrays.sort(改进的快速排序方法) 1. 100000的随机数据集 ![](http://7xlkoc.com1.z0.glb.clouddn.com/sort1.jpg) 2. 200000的随机数据集 ![]...
含有冒泡、选择、插入、快速、arrays排序
现有股票数据XX条,无序...注意:实现排序算法可以使用冒泡排序,插入排序,堆排序,选择排序,快速排序等,任何的排序算法都是可以被接受的,但不能使用系统库中自带的排序函数,如List.sort() 或者 Arrays.sort()。
首先,我编写了一个经典的快速排序算法。这个算法通过计算样本的平均值来估计整个数组的中心点,然后用作初始枢轴。 我借鉴了一些Java的思路来适当改进我的快速排序,修改后的算法在对小数组进行排序的时候...
可视化三种不同排序算法的Java应用程序:冒泡排序,快速排序和数组排序,可以选择对排序时进行的每个比较播放不同的音调。 该应用程序包含4个控件和一个按钮,用于开始可视化。 排序方法ChoiceBox允许在不同的排序...
根据排序算法的特性,可以分为比较排序(例如冒泡、堆排序、插入排序、归并排序、快速排序、选择排序、希尔排序等)和非比较排序(例如计数排序、基数排序和桶排序) 不同的排序,对数据类型和幅值的要求不一,因此...
快速排序的改进型:对于从1到1千万中的1百万个随机整数排序,其结果如下:对比java自带的Arrays.sort()的速度还要提升3倍,其原因应该是在于多一个监
基本类型数据使用快速排序法,对象数组使用归并排序。 String,StringBuffer和StringBuilder的区别; 解答: Object的方法有哪些:比如有wait方法,为什么会有; 解答: wait和sleep的区别,必须理解!!! 解答: 强...
快速排序 Sort Colors Kth Largest Element in an Array 桶排序 First Missing Positive 计数排序 H-Index 基数排序 Maximum Gap 其他 Largest Number 小结 查找 Search for a Range Search Insert Position Search ...