```快速排序 Quicksort 是对冒泡排序的一种改进

int[] arr = { 3, 2, 1, 9, 4, 8, 7, 5, 6 };
left=0,right=8,partitionIndex=2
1 2 3 9 4 8 7 5 6
left=0,right=1,partitionIndex=0
1 2 3 9 4 8 7 5 6
left=3,right=8,partitionIndex=8
1 2 3 6 4 8 7 5 9
left=3,right=7,partitionIndex=5
1 2 3 5 4 6 7 8 9
left=3,right=4,partitionIndex=4
1 2 3 4 5 6 7 8 9
left=6,right=7,partitionIndex=6
1 2 3 4 5 6 7 8 9

public class QuickSort {
public static void main(String[] args) throws Exception {
int[] arr = { 3, 2, 1, 9, 4, 8, 7, 5, 6 };
quickSort(arr);
System.out.println();
printArr(arr);
System.out.println();

int[] arr2 = { 3 };
quickSort(arr2);
System.out.println();

int[] arr3 = { 3, 2 };
quickSort(arr3);
System.out.println();
}

private static void quickSort(int[] arr) {
final int N = arr.length - 1;
quickSort(arr, 0, N);
}

private static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
// for debug
System.out.println("left=" + left + ",right=" + right + ",partitionIndex=" + partitionIndex);
printArr(arr);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, right);
}
}

private static int partition(int[] arr, int left, int right) {
// 设定基准值 pivot
int pivot = left;
int index = pivot + 1;
for (int i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
}

private static void printArr(int[] arr) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < arr.length; i++) {
sb.append(arr[i]).append(" ");
}
System.out.println(sb.toString());
}

private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}

https://gitee.com/dyyx/hellocode/blob/master/src/algo/sort/QuickSort.java

归并排序与快速排序
```

Java assert

Linux dd 命令