1 排序原理

quickSort(int[] arr, int left, int right) 參數(shù)描述

• arr: 待排序的數(shù)組
• left: 排序的左邊位置
• right: 排序的右邊位置

排序步驟:

1. 先選取左邊節(jié)點(diǎn)的數(shù)據(jù)作為 pivot
2. 從右邊開始, 向左遍歷節(jié)點(diǎn)數(shù)據(jù), 在滿足right > left 條件前提下:

如果節(jié)點(diǎn)數(shù)據(jù) > pivot 繼續(xù)向左移動(dòng)
如果節(jié)點(diǎn)數(shù)據(jù) <= pivot 則把當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)賦值到 left 節(jié)點(diǎn), 然后停止右邊遍歷, 開始左邊遍歷

3. 從左邊開始, 向右遍歷節(jié)點(diǎn)數(shù)據(jù), 在滿足left > right 條件前提下:

如果節(jié)點(diǎn)數(shù)據(jù) < pivot 繼續(xù)向右移動(dòng)
如果節(jié)點(diǎn)數(shù)據(jù) >= pivot 則把當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)賦值到 right 節(jié)點(diǎn), 然后停止左邊遍歷, 開始右邊遍歷

4. 當(dāng) left 和 right 重合后, 此次遍歷結(jié)束, 把 pivot 賦值到重合節(jié)點(diǎn), pivot節(jié)點(diǎn)左邊為左數(shù)組, 右邊的為右數(shù)組

對(duì)左數(shù)組遞歸調(diào)用執(zhí)行 1,2,3 步驟
對(duì)右數(shù)組遞歸調(diào)用執(zhí)行 1,2,3 步驟

5. 完成快速排序

2 代碼實(shí)現(xiàn)

public static void main(String[] args) {  int[] arr = {5, 3, 8, 5, 4, 2};  quickSort(arr, 0, arr.length - 1);  System.out.println("排序后的數(shù)組:" + Arrays.toString(arr));  
}  public static void quickSort(int[] arr, int left, int right) {  if (left >= right) {  return;  }  // 選取最左邊的元素作為樞軸  int pivot = arr[left];  int i = left;  int j = right;  while (i < j) {  // 先從右邊開始找小于樞軸的元素  while (i < j && arr[j] >= pivot) {  // 如果沒有找到, 就繼續(xù)往左邊找  j--;  }  // 在右邊找到小于樞軸的元素后, 將其賦值給左邊位置的元素  arr[i] = arr[j];  // 然后從左邊開始找大于樞軸的元素  while (i < j && arr[i] <= pivot) {  // 如果沒有找到, 就繼續(xù)往右邊找  i++;  }  // 在左邊找到大于樞軸的元素后, 將其賦值給右邊位置的元素  arr[j] = arr[i];  }  // 當(dāng) left == right 時(shí), 把 pivot 賦值給 arr[i]    arr[i] = pivot;  // 遞歸調(diào)用  // 對(duì) pivot 位置左邊進(jìn)行快速排序  quickSort(arr, left, i - 1);  // 對(duì) pivot 位置右邊進(jìn)行快速排序  quickSort(arr, i + 1, right);  
}