private int[] data;
QuickSort(int[] data) {
this.data = data;
}
public void quickSort() {
recQuickSort(data, 0, data.length - 1);
}
private void recQuickSort(int[] data, int low, int high) {
// 設置兩個滑標
int lowCursor = low + 1;
int highCursor = high;
// 交換時的臨時變量
int temp = 0;
// 比較樞值,設為數組的第壹個值
int medi = data[low];
while (true) {
// 從低端開始查找,確定大於數 data[low] 所在的位置
while (lowCursor < high && data[lowCursor] < medi) {
lowCursor++;
}
// 從高端開始查找,確定小於數 data[low] 所在的位置。這裏要使用 >= 判斷確定小於值
while (highCursor > low && data[highCursor] >= medi) {
highCursor--;
}
// 兩遊標位置出現越界,退出循環
if (lowCursor >= highCursor) {
break;
}
// 交換 data[highCursor] 和 data[lowCursor] 位置數據
temp = data[highCursor];
data[highCursor] = data[lowCursor];
data[lowCursor] = temp;
}
// 由 while 循環退出條件可知:lowCursor > highCursor
// 當前 lowCursor 指向右側大於 data[low]的第壹個位置;
// 而 highCursor 指向左側小於 data[low]的第壹個位置,所以需要交換 data[low] 和
// data[highCursor]的值
data[low] = data[highCursor];
data[highCursor] = medi;
// 遞歸運算左半部分
if (low < highCursor) {
recQuickSort(data, low, highCursor);
}
// 遞歸運算右半部分
if (lowCursor < high) {
recQuickSort(data, lowCursor, high);
}
}
//打印數組
public void display() {
for (int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
//產生壹個包含size個隨機數的數組
public static int[] getData(int size){
int data[]=new int[size];
for (int i = 0; i < data.length; i++) {
data[i]=(int)(1+Math.random()*54);//產生壹個1-54的隨機數,Math.random()是產生0-1的數.
}
return data;
}
//測試
public static void main(String[] args) {
int data[]=getData(10);
QuickSort sort = new QuickSort(data);
sort.display();
sort.quickSort();
sort.display();
}
}