算法（4）——快速排序算法
快速排序的原理：选择一个关键值作为基准值。比基准值小的都在左边序列（一般是无序的），比基准值大的都在右边（一般是无序的）。一般选择序列的第一个元素。一次循环：从后往前比较，用基准值和最后一个值比较，如果比基准值小的交换位置，如果没有继续比较下一个，直到找到第一个比基准值小的值才交换。找到这个值之后，又从前往后开始比较，如果有比基准值大的，交换位置，如果没有继续比较下一个，直到找到第一个比基准值大的值才交换。直到从前往后的比较索引>从后往前比较的索引，结束第一次循环，此时，对于基准值来说，左右两边就是有序的了。
public class 快排 {public static void quickSort(int[] arr, int startIndex, int endIndex) {// 递归结束条件：startIndex大等于endIndex的时候if (startIndex >= endIndex) {return;}// 得到基准元素位置int pivotIndex = partition(arr, startIndex, endIndex);// 用分治法递归数列的两部分quickSort(arr, startIndex, pivotIndex - 1);quickSort(arr, pivotIndex + 1, endIndex);}private static int partition(int[] arr, int startIndex, int endIndex) {// 取第一个位置的元素作为基准元素int pivot = arr[startIndex];int left = startIndex;int right = endIndex;// 坑的位置，初始等于pivot的位置int index = startIndex;//大循环在左右指针重合或者交错时结束while ( right >= left ){//right指针从右向左进行比较while ( right >= left ) {if (arr[right] < pivot) {arr[left] = arr[right];index = right;left++;break;}right--;}//left指针从左向右进行比较while ( right >= left ) {if (arr[left] > pivot) {arr[right] = arr[left];index = left;right--;break;}left++;}}arr[index] = pivot;return index;}}