Posted on 2010-11-22 05:53
Ardor Leo 阅读(2287)
评论(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 = 0; k < pData.length; k++) {
System.out.print(pData[k] + " ");
}
System.out.println();
// 此种条件可以避免多余排序（每一趟最后两个相邻已比较后，就不用再递归了）
if (j - left > 1)
qSort1(pData, left, j);
if (length - i > 1)
qSort1(pData, i, length);
}
/**
* @author ardorleo 2010-11-21 快速排序的非递归实现
* @param pData
* 需要排序的数组
* @param left
* 左边的位置,初始值为0
* @param length
* 右边的位置,初始值为数组长度
*/
public static void qsort2(int[] pData, int orignal_start, int orignal_length) {
int temp;
int start = orignal_start;
int length = orignal_length;
int left = orignal_start;
int right = orignal_length;
int reference = pData[left];
Stack<Integer> intStack = new Stack<Integer>();
while (true) {
while (true) {
while ((++left) < length - 1 && pData[left] < reference)
;
while ((--right) > start && pData[right] > reference)
;
if (left >= right)
break;
temp = pData[left];
pData[left] = pData[right];
pData[right] = temp;
}
pData[start] = pData[right];
pData[right] = reference;
System.out.print("分界值:" + reference + " 下标:" + right+ " 当前顺序: ");
for (int k = 0; k < pData.length; k++) {
System.out.print(pData[k] + " ");
}
System.out.println();
//分值左边排序
if (right > start + 1) {
intStack.push(length);
length = right;
left = start;
}
//分值右边排序
while (length <= left + 1 && !intStack.empty()) {
int tempLength = intStack.pop();
left = length + 1;
length = tempLength;
}
if (length > left + 1) {
start = left;
right = length;
}
//结束条件
if (intStack.empty() && length <= left + 1)
break;
//left值有可能大于下标最大值
reference = pData[left];
}
}
public static void main(String[] args) {
int[] pData = new int[10];
for (int i = 0; i < 10; i++) {
pData[i] = (int) (Math.random() * 100);
}
System.out.print("数组原始序列:");
for (int i = 0; i < pData.length; i++)
System.out.print(pData[i] + " ");
System.out.println("\n***********************");
QSort.qsort2(Arrays.copyOf(pData, pData.length), 0, pData.length);
System.out.println("***********************");
QSort.qSort1(Arrays.copyOf(pData, pData.length), 0, pData.length);
System.out.println("***********************");
QSort.quickSort(Arrays.copyOf(pData, pData.length), 0, pData.length);
}
}