狠狠撸

Arrays 的 sort 算法分析

Zianed Hou
zianed@live.cn

1、Arrays.sort方法概述

2、分析int[]的排序实现

3、对象实现了可比较接口Comparable 进行比较

4、对象没有可比较性，进行比较时需要靠比较器进行

5、以上排序算法是qsort和合并排序算法的实现

Zianed Version 1.0 1

1、Arrays.sort方法概述
Arrays 提供了对基本类型 byte、char、double、float、int、long 型数组的排
序实现。
Arrays 提供了对对象类型数组的比较。
实现可比较接口的，可以直接进行比较：
public static void sort(Object[] a)进行比较
没有实现比较接口的，须有一个比较器，而且这个比较器可以进行对该种对象类型的比较：
public static <T> void sort(T[] a,Comparator<? super T> c)

而且以上的排序算法都提供了有区间的数据排序,formIndex 和 toIndex 进行。

2、分析int[]的排序实现
基本类型同 int[]相似
查看 API 可以发现 sort 整数数组提供以下两种方法实现：
//不带范围的
public static void sort(int[] a) {
sort1(a, 0, a.length);
}
//带范围的排序
public static void sort(int[] a, int fromIndex, int toIndex) {
rangeCheck(a.length, fromIndex, toIndex);//进行了范围检查
sort1(a, fromIndex, toIndex-fromIndex);
}

通过代码可以看出都是调用了以下函数进行了排序：
private static void sort1(int x[], int off, int len)

对于相关调用函数的说明
1)对输入参数进行了校验，保证入参的有效性；
##这样做的好处是，由于我们的计算机都是堆栈计算机，在传入参数时检验有效
##性，可以避免数据压入栈的过程中的时间、空间消耗。应该是一种编程推荐的
##做法。
private static void rangeCheck(int arrayLen, int fromIndex, int toIndex)
{


if (fromIndex > toIndex)
throw new IllegalArgumentException("fromIndex(" + fromIndex +
") > toIndex(" + toIndex+")");
if (fromIndex < 0)
throw new ArrayIndexOutOfBoundsException(fromIndex);
if (toIndex > arrayLen)
throw new ArrayIndexOutOfBoundsException(toIndex);
}

2)交换数组的两个元素,采用普通的中间变量交换方法
##空间数据交换是一种普遍使用的方法；虽然可以使用时间换空间的方法，但一
##般只是在空间资源紧缺的情况下使用。一般认为都是时间紧缺，占主导地位。
private static void swap(int x[], int a, int b)
{
int t = x[a];
x[a] = x[b];
x[b] = t;
}

3)交换数组中的连续的一组元素
##将下标 a 开始的 n 个元素与从下标 b 开始的 n 个元素,依次交换，调用 swap
##方法进行实际的数据交换。
private static void vecswap(int x[], int a, int b, int n)
{
for (int i = 0; i < n; i++, a++, b++)
swap(x, a, b);
}

4)返回下标关联的三个元素中的占中间的元素的位置。
##采用三目运算符进行数据的比较
##返回数值占中间元素的位置
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));
}

核心函数分析
传入参数的说明：
X[]:要排序的数组
Int off:排序元素的起始位置
Int len:要排序元素的个数
private static void sort1(int x[], int off, int len)
{


// 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;
}

// Choose a partition element, v
##选择分割元素v

##找到位置在中间的元素
int m = off + (len >> 1); // Small arrays, middle element

##要排序元素个数大于7时的情况
##相对于else就只有等于7的情况
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];

// Establish Invariant: v* (<v)* (>v)* v*
int a = off, b = a, c = off + len - 1, d = c;
##a为起始元素位置,b跟a相同,d为结束元素位置;c同d
##a,d是固定不变量,作为界定元素;b,c是自变量

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--);
}

// Swap partition elements back to middle
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);

// Recursively sort non-partition-elements
##排序a-b之间的元素
if ((s = b - a) > 1)
sort1(x, off, s);
##排序c到d之间的元素
if ((s = d - c) > 1)
sort1(x, n - s, s);
}

核心的本质使用的是采用的对快速排序的一种改进，分段进行操作。
找到一个模拟的中间值(数值意义上的)，按照中间值分段进行排序。
最后分成的小段使用的是快速排序


3、对象实现了可比较接口Comparable 进
行比较
INSERTIONSORT_THRESHOLD 表示插入排序的起始点,当长度小于此临界值时，
进行插入排序。
整体采用的是 2—路归并排序。
对前一半和后一半分别使其有序，然后进行合并。
此算法是稳定的，O（ nlog2(n)）的效率

/**
* used in preference to mergesort or quicksort.
*/
private static final int INSERTIONSORT_THRESHOLD = 7;

private static void mergeSort(Object[] src, Object[] dest,
int low, int high, int off) {
int length = high - low;
if (length < INSERTIONSORT_THRESHOLD) {
for (int i=low; i<high; i++)
for (int j=i; j>low &&
((Comparable) dest[j-1]).compareTo(dest[j])>0; j--)
swap(dest, j, j-1);
return;
}
// Recursively sort halves of dest into src
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >>> 1;
##递归对前一半和后一半进行归并排序
mergeSort(dest, src, low, mid, -off);
mergeSort(dest, src, mid, high, -off);

// If list is already sorted, just copy from src to dest. This is an
// optimization that results in faster sorts for nearly ordered lists.
#前一半和后一半分别有序，并且前一半的最大值小于等于后一半的最小值，那么直接进行合并
if (((Comparable)src[mid-1]).compareTo(src[mid]) <= 0) {
System.arraycopy(src, low, dest, destLow, length);
return;
}


// Merge sorted halves (now in src) into dest
#否则对该段进行比较的合并操作
#p 表示前一段的下标
#q 表示后一段的下标
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
#1、q>=high表示后一半数据已经全部排序完了，将前一半剩余的数据复制到目标中
#2、p<mid 表示前一段数据还有剩余，需要对跟后一段数据进行比较
# src[p]<= src[q] 说明前一段数据中的p小于等于q，那么复制前一段数据中的p到目标
if (q >= high || p < mid && ((Comparable)src[p]).compareTo(src[q])<=0)
dest[i] = src[p++];
#1、p>=mid前一半数据已经全部排序完了，将后一半剩余的数据复制到目标中
#2、p<mid 表示前一段数据还有剩余，需要对跟后一段数据进行比较
# src[p]> src[q] 说明前一段数据中的p大于q，那么复制后一段数据中的q到目标
else
dest[i] = src[q++];
}
}

/**
* Swaps x[a] with x[b].
*/
private static void swap(Object[] x, int a, int b) {
Object t = x[a];
x[a] = x[b];
x[b] = t;
}

4、对象没有可比较性，进行比较时需要靠
比较器进行
INSERTIONSORT_THRESHOLD 表示插入排序的起始点,当长度小于此临界值时，
进行插入排序。
整体采用的是 2—路归并排序。
对前一半和后一半分别使其有序，然后进行合并。
此算法是稳定的，O（ nlog2(n)）的效率.

此算法分析与前相同，仅仅是在比较的时间是采用的比较器，两个对象做参数

private static void mergeSort(Object[] src,
Object[] dest,
int low, int high, int off,


Comparator c) {
int length = high - low;

if (length < INSERTIONSORT_THRESHOLD) {
for (int i=low; i<high; i++)
for (int j=i; j>low && c.compare(dest[j-1], dest[j])>0; j--)
swap(dest, j, j-1);
return;
}

// Recursively sort halves of dest into src
int destLow = low;
int destHigh = high;
low += off;
high += off;
int mid = (low + high) >>> 1;
mergeSort(dest, src, low, mid, -off, c);
mergeSort(dest, src, mid, high, -off, c);

// If list is already sorted, just copy from src to dest. This is an
// optimization that results in faster sorts for nearly ordered lists.
if (c.compare(src[mid-1], src[mid]) <= 0) {
System.arraycopy(src, low, dest, destLow, length);
return;
}

// Merge sorted halves (now in src) into dest
for(int i = destLow, p = low, q = mid; i < destHigh; i++) {
if (q >= high || p < mid && c.compare(src[p], src[q]) <= 0)
dest[i] = src[p++];
else
dest[i] = src[q++];
}
}

5、以上排序算法是qsort和合并排序算法的
实现
快速排序是不稳定的。


合并排序是稳定的。

排序是一个常用的算法，尤其是在其他一些使用的过程中常常需要先进行此操作，例如查找
public static int binarySearch() 二分查找这个是基于排序的

基本型的排序算法是
是一个经过调优的快速排序法，改编自 Jon L. Bentley 和 M. Douglas McIlroy 合著的
Engineering a Sort Function", Software-Practice and Experience Vol. 23(11) P. 1249-1265
(November 1993)。此算法在许多数据集上提供 n*log(n) 性能，这导致其他快速排序会降低
二次型性能。
该算法原文如下
http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maran
get/421/09/bentley93engineering.pdf

分析该篇论文，可以看出排序算法的改进方向，进一步掌握如何获取改进算法的
一个思路。

References
http://www.docin.com/p-26519551.html
http://hi./helloyanwo/blog/item/bd39af6ce372a1f142169409.html
http://www.cuyoo.com/html/shenghuo/2009/0304/1015.html
http://nknucc.nknu.edu.tw/~jwu/datastr/datastr.htm
http://www.enseignement.polytechnique.fr/profs/informatique/Luc.Maranget/421/09
/bentley93engineering.pdf
http://cs.umaine.edu/~chaw/200801/capstone/n/enggsort.pdf


Zianed
Homepage：http://my.unix-center.net/~Zianed/
Mail： hxuanzhe86@sina.com
MSN：zianed@live.cn
QQ：1196123432
QQGroup： 50457022
Date：2009-10-24


狠狠撸

础谤谤补测蝉的厂辞谤迟算法分析

Recommended

More Related Content

What's hot (20)

Viewers also liked (7)

Similar to 础谤谤补测蝉的厂辞谤迟算法分析 (15)

础谤谤补测蝉的厂辞谤迟算法分析