1. 快排算法思路
基本思想：通过一趟快速排序将待排数组分割成独立的两份部分; 其中一部分数组的值均比另一部分数组的值小，则可分别对着两部分数组继续进行排序，以达到整个序列有序。
快排的平均时间复杂度为n*log（n），最坏的时间复杂度为 n^2。
一趟快速排序：首先先选一个值（通常选择数组第一个值）作为枢轴，然后按下述原则重新排列其余的值，将数组中所有小于枢轴的值放在枢轴前面，数组中所有大于枢轴的值放在枢轴后面。将枢纽最后的位置作为分界线，将数组分成两部分（两部分均不包含枢轴），这个过程称作一趟快速排序。
一趟快速排序的具体做法：
1. 设两个指针 low 和 high ， 他们的初始值分别为数组开始的下标 start，数组结束的下标end
2. 枢轴值为 pivotKey
3. 则首先从 high 所指位置向前搜索，搜索到第一个小于 pivotKey 的 值，然后将这个值和 pivotKey 互相交换。
4. 从 low 所指位置向后搜索，搜索到第一个大于 pivotKey 的 值，然后将这个值和 pivotKey 互相交换。
5. 重复前两步操作（3，4），直至 low == high 。
2. Java 代码实现
完全按照上面的思路的 Java 代码如下：
package sort;
/**
* 快速排序(Quick Sort) Java代码实现
* 快排时间复杂度：n*log(n)
*/
public class MySort {
public static void main(String args[]) {
int[] arr = new int[]{49, 38, 65, 97, 76, 13, 27};
MySort mySort = new MySort();
System.out.print("排序前的数组： ");
PrintArray(arr, 0, arr.length-1);
mySort.quickSort(arr, 0, arr.length-1);
System.out.print("排序后的结果： ");
PrintArray(arr, 0, arr.length-1);
}
/**
* 对数组 arr 下标从 start 到 end 的内容进行排序
* @param arr：待排序数组
* @param start：开始的下标
* @param end：结束的下标
*/
public static void quickSort(int[] arr, int start, int end) {
if(start >= end) {
return;
}
// 1. 设两个指针 low 和 high ，他们的初始值分别为数组开始的下标 start，数组结束的下标end
int low = start;
int high = end;
// 2. 枢轴值为 pivotKey
int pivotKey = arr[start];
// 5. 重复前两步操作（3，4），直至 low == high
while (low<high) {
// 3. 首先从 high 所指位置向前搜索，搜索到第一个小于 pivotKey 的 值，然后将这个值和 pivotKey 互相交换
while (low<high && arr[high]>=pivotKey) {
--high;
}
int temp1 = arr[low];
arr[low] = arr[high];
arr[high] = temp1;
// 4. 从 low 所指位置向后搜索，搜索到第一个大于 pivotKey 的 值，然后将这个值和 pivotKey 互相交换。
while (low<high && arr[low]<=pivotKey) {
++low;
}
temp1 = arr[low];
arr[low] = arr[high];
arr[high] = temp1;
}
// 对 小于枢轴值的那部分数组值 进行快排
quickSort(arr, start, low-1);
// 对 大于枢轴值的那部分数组值 进行快排
quickSort(arr, low+1, end);
}
/**
*输出数组中的值
* @param arr：数组
* @param start：数组开始的下标
* @param end：数组结束的下标
*/
public static void PrintArray(int[] arr, int start, int end) {
for (int i=start; i<=end; i++) {
System.out.print(arr[i] + " ");
}
System.out.println("");
}
}运行可得 ：
3. 简单的优化
进行一次数值交换，如 ：temp1 = arr[low]; arr[low] = arr[high]; arr[high] = temp1，需要三次赋值，temp1 = arr[low]; arr[high] = temp1 这两次赋值其实是多余的，因为 当 low == high ， 也就是最终的位置 low ，就是枢轴值的位置，我们只需要在一次快排结束后将枢轴值放到 low 位置就可以了。Java源码如下。
package sort;
/**
* 快速排序(Quick Sort) Java代码实现
* 快排时间复杂度：n*log(n)
*/
public class MySort {
public static void main(String args[]) {
int[] arr = new int[]{49, 38, 65, 97, 76, 13, 27};
MySort mySort = new MySort();
System.out.print("排序前的数组： ");
PrintArray(arr, 0, arr.length-1);
mySort.quickSort(arr, 0, arr.length-1);
System.out.print("排序后的结果： ");
PrintArray(arr, 0, arr.length-1);
}
/**
* 对数组 arr 下标从 start 到 end 的内容进行排序
* @param arr：待排序数组
* @param start：开始的下标
* @param end：结束的下标
*/
public static void quickSort(int[] arr, int start, int end) {
if(start >= end) {
return;
}
// 1. 设两个指针 low 和 high ，他们的初始值分别为数组开始的下标 start，数组结束的下标end
int low = start;
int high = end;
// 2. 枢轴值为 pivotKey
int pivotKey = arr[start];
// 5. 重复前两步操作（3，4），直至 low == high
while (low<high) {
// 3. 首先从 high 所指位置向前搜索，搜索到第一个小于 pivotKey 的 值，然后将这个值和 pivotKey 互相交换
while (low<high && arr[high]>=pivotKey) {
--high;
}
arr[low] = arr[high];
// 4. 从 low 所指位置向后搜索，搜索到第一个大于 pivotKey 的 值，然后将这个值和 pivotKey 互相交换。
while (low<high && arr[low]<=pivotKey) {
++low;
}
arr[high] = arr[low];
}
// 一次快排结束后将枢轴值放到 low 位置
arr[low] = pivotKey;
// 对 小于枢轴值的那部分数组值 进行快排
quickSort(arr, start, low-1);
// 对 大于枢轴值的那部分数组值 进行快排
quickSort(arr, low+1, end);
}
/**
*输出数组中的值
* @param arr：数组
* @param start：数组开始的下标
* @param end：数组结束的下标
*/
public static void PrintArray(int[] arr, int start, int end) {
for (int i=start; i<=end; i++) {
System.out.print(arr[i] + " ");
}
System.out.println("");
}
}运行截图 ：
4. 优化措施
优化最坏的情况：在选择枢轴，取数组的第一个元素、中间的那个元素、最后一个元素的中位数作为枢轴。
优化最好的情况：添加两个 布尔类型 变量，如果 指针low 从低端向中间的移动过程中没有交换记录，则不需要对枢轴左部分的元素排序；如果 指针high 从高端向中间的移动过程中没有交换记录，则不需要对枢轴右部分的元素排序，这样就可能达到n的时间复杂度。
5. 参考文献
数据结构 - 严蔚敏、吴伟民 - 清华大学出版社