Posted on 2010-11-22 05:53
Ardor Leo 阅读(2339)
评论(0) 编辑 收藏 所属分类:
有点心得
最近从《
java中的快速排序算法》看到了一个快速排序的实现，实际上手测试了下。然后发现原算法有重复，便优化了一下。另外，自己实现了非递归的算法。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;
public class QSort {
/**
* @author WangYu 2008-05-29 初始
* @param pData
* 需要排序的数组
* @param left
* 左边的位置,初始值为0
* @param length
* 右边的位置,初始值为数组长度
*/
public static void quickSort(int[] pData, int left, int right) {
int i, j;
int middle, temp;
i = left;
j = right;
middle = pData[left];
while (true) {
while ((++i) < right - 1 && pData[i] < middle)
;
while ((--j) > left && pData[j] > middle)
;
if (i >= j)
break;
temp = pData[i];
pData[i] = pData[j];
pData[j] = temp;
}
pData[left] = pData[j];
pData[j] = middle;
System.out.print("分界值:" + middle + " 下标" + j + ": ");
for (int k = 0; k < pData.length; k++) {
System.out.print(pData[k] + " ");
}
System.out.println();
if (left < j)
quickSort(pData, left, j);
if (right > i)
quickSort(pData, i, right);
}
/**
* @author ardorleo 2010-11-21 快速排序优化后的递归实现
* @param pData
* 需要排序的数组
* @param left
* 左边的位置,初始值为0
* @param length
* 右边的位置,初始值为数组长度
*/
public static void qSort1(int[] pData, int left, int length) {
int i, j;
int middle, temp;
i = left;
j = length;
middle = pData[left];
while (true) {// 在循环体中，middle只用做比较，但值保持不变
while ((++i) < length - 1 && pData[i] < middle)
;
while ((--j) > left && pData[j] > middle)
;
if (i >= j)
break;
temp = pData[i];
pData[i] = pData[j];
pData[j] = temp;
}
// 较小的值在左，较大的值右
pData[left] = pData[j];
pData[j] = middle;
System.out.print("分界值:" + middle + " 下标" + j + ": ");
for (int k =