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

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

    }

 

总结：

1.  对于小于7的元素使用插入排序；
2. 选择中间元素有学问；
3. 对等于v的数据进行的特殊处理。