Posted on 2010-11-22 05:53
Ardor Leo 閱讀(2293)
評論(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);
}
}