Java Arrays 快速排序算法的实现
我们知道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
intm = 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
}
intv = 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)*的结构：
ints, 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);
??? }
?
总结：
