1. 遞歸方式
public class JavaTest1 {
public static void main(String[] args) {
int[] ints = {43, 0, -1, 56, 100, -245};
System.out.println(Arrays.toString(ints));
quickSort(ints, 0, ints.length - 1);
System.out.println(Arrays.toString(ints));
}
private static void swap(int[] arr, int aIndex, int bIndex) {
int temp = arr[aIndex];
arr[aIndex] = arr[bIndex];
arr[bIndex] = temp;
}
public static void quickSort(int[] arr, int left, int right) {
if (left > right) {
return;
}
// 獲取一個(gè)參考值的索引(這里選擇數(shù)組中間位置的元素作為參考值,也可以隨機(jī)選擇一個(gè))
int mid = left + (right - left) / 2;
// 將參考值交換到數(shù)組的最左側(cè)
swap(arr, left, mid);
// 用于記錄有多少個(gè)值比參考值小
int j = left;
// 開始處理數(shù)組, 比參考值小的 將其移動(dòng)到數(shù)組的左側(cè)
for (int i = left + 1; i <= right; i++) {
// 將數(shù)組值依次與數(shù)組[最左側(cè)]的參考值進(jìn)行比較
if (arr[i] < arr[left]) {
j++;
// 將比參考值小的元素交換到數(shù)組的左側(cè)來
swap(arr, i, j);
}
}
// 最后將數(shù)組最左側(cè)的參考值交換到他最終排序好的位置去
System.out.println("數(shù)組元素值為 " + arr[left] + " 的值最終排序好的位置是 " + j);
swap(arr, left, j);
// 然后將參考值左側(cè)的數(shù)組和參考值右側(cè)的數(shù)組繼續(xù)進(jìn)行上述操作
quickSort(arr, left, j - 1);
quickSort(arr, j + 1, right);
}
}
2. 循環(huán)方式
public class JavaTest2 {
public static void main(String[] args) {
int[] ints = {43, 0, -1, 56, 100, -245};
System.out.println(Arrays.toString(ints));
quickSort(ints);
System.out.println(Arrays.toString(ints));
}
private static void swap(int[] arr, int aIndex, int bIndex) {
int temp = arr[aIndex];
arr[aIndex] = arr[bIndex];
arr[bIndex] = temp;
}
public static void quickSort(int[] arr) {
if (arr.length <= 1) {
return;
}
Stack<Integer> st = new Stack<>();
st.push(0);
st.push(arr.length - 1);
while (!st.isEmpty()) {
// 因?yàn)闂Ｊ窍冗M(jìn)后出,先推入的是左側(cè)的下標(biāo)
// 所以推出的時(shí)候就先是右側(cè)的下標(biāo)
int right = st.pop();
int left = st.pop();
// 獲取一個(gè)參考值的索引(這里選擇數(shù)組中間位置的元素作為參考值,也可以隨機(jī)選擇一個(gè))
int mid = left + (right - left) / 2;
// 將參考值交換到數(shù)組的最左側(cè)
swap(arr, left, mid);
// 用于記錄有多少個(gè)值比參考值小
int j = left;
// 開始處理數(shù)組, 比參考值小的 將其移動(dòng)到數(shù)組的左側(cè)
for (int i = left + 1; i <= right; i++) {
// 將數(shù)組值依次與數(shù)組[最左側(cè)]的參考值進(jìn)行比較
if (arr[i] < arr[left]) {
j++;
// 將比參考值小的元素交換到數(shù)組的左側(cè)來
swap(arr, i, j);
}
}
// 最后將數(shù)組最左側(cè)的參考值交換到他最終排序好的位置去
swap(arr, left, j);
// 然后將參考值左側(cè)的數(shù)組和參考值右側(cè)的數(shù)組繼續(xù)進(jìn)行上述操作
if (left < j - 1) {
st.push(left);
st.push(j - 1);
}
if (right > j + 1) {
st.push(j + 1);
st.push(right);
}
}
}
}
3. 運(yùn)行結(jié)果
[ 43, 0, -1, 56, 100, -245 ]
[ -245, -1, 0, 43, 56, 100 ]
