快速排序是一种常用的排序算法，最好的情况下时间复杂度为 O(nlogn)。快速排序采用分治法的思想，具体过程如下：
1.选定一个基准元素，通常选择第一个或最后一个元素；
2.设置两个指针，一个指向起始位置，一个指向终止位置；
3.从后往前查找，找到第一个小于基准元素的位置并记录下来；
4.从前往后查找，找到第一个大于基准元素的位置并记录下来；
5.交换这两个位置上的元素；
6.继续向后查找并交换元素，直到左右指针相遇；
7.经过以上步骤后，所有小于基准元素的元素都在左侧，大于基准元素的元素都在右侧；
8.递归地对左右两侧进行快速排序。
public static void quickSort(int[] arr, int left, int right){
if(left >= right){
return;
}
int index = partition(arr, left, right);
quickSort(arr, left, index-1);
quickSort(arr, index+1, right);
}
public static int partition(int[] arr, int left, int right){
int pivot = arr[left];
int i = left + 1;
int j = right;
while(i <= j){
while(i <= j && arr[i] < pivot){
i++;
}
while(i <= j && arr[j] > pivot){
j--;
}
if(i <= j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
arr[left] = arr[j];
arr[j] = pivot;
return j;
}
假设现在有一个无序数组 {6, 2, 9, 3, 7}，进行快速排序的过程如下：
1.首先选定基准元素为6，即数组的第一个元素；
2.设置左指针l为2，右指针r为7；
3.从后往前查找，找到第一个小于6的元素，即3，将3与6交换位置；此时数组变为{3, 2, 9, 6, 7}；
4.从前往后查找，找到第一个大于6的元素，即9，将9与6交换位置；此时数组变为{3, 2, 6, 9, 7}；
5.左指针l=2，右指针r=8，继续步骤3，找到第一个小于6的元素2，将2与6交换位置；此时数组变为{3, 2, 6, 9, 7}；
6.左指针l=3，右指针r=6，左右指针相遇，一轮排序完毕；
7.递归地对左侧数组{3, 2}和右侧数组{9, 7}重复以上步骤，直到数组有序。
此时数组变为 {2, 3, 6, 7, 9}。
在实现过程中，还需要考虑一些细节问题，例如如何选择基准元素，以及如何处理重复元素等，但基本的思想和实现方法和上面介绍的是一样的。
本文链接：http://task.lmcjl.com/news/13243.html