期望时间复杂度o(nlogn) 最坏情况时间复杂度o(n^2);
无序数组{A1.........An} 先取一个基数K=A1,设置从后往前遍历的索引j(初始值为arrays.length-1)，从前往后遍历的索引i(初始值为0)。从后往前遍历时（j--）,找到第一个小于K的数，交换两个数的位置，记录index，然后从前往后遍历，找到第一个大于K的数，于索引index的数（K）交换位置，刷新index。然后从上次后往前停留的索引出开始往前找小于K的数........ 总的来说就是 重复从后往前找更小的交换位置 从前往后找更大的交换位置 直到i=j跳出循环
以上是一趟排序过程 结果就是K左边的数都比K小，K右边的数都比K大。
然后就对K左边的数组{a1......ak-1} K右边的数组{ak+1........an}进行递归（重复以上步骤）
java代码如下
/** * 快速排序 * @param beginIndex 对arrays中需要排序的数组 开始的索引 * @param endIndex 对arrays中需要排序的数组 结束的索引 * @param arrays 需要排序的整个数组 */ public static void sort(int beginIndex,int endIndex,int[] arrays){ if(arrays == null || arrays.length <= 1){ return; } int i = beginIndex,j=endIndex; //以array[0]为基准 int k = arrays[i]; int k_index = beginIndex;//记录K的index //j往前遍历比k小的数并且交换 i设置为该数的index //i往后遍历比k大的数并且交换 i设置为该数的index //一直到i=j while(i != j){ for(;j>=0;j--){ if(j==i) break; if(arrays[j] < k){ //交换位置 int temple = arrays[j]; arrays[j] = k; arrays[k_index] = temple; //记录index k_index = j; break; } } for(;i<arrays.length;i++){ if(j==i) break; if(arrays[i] > k){ //交换位置 int temple = arrays[i]; arrays[i] = k; arrays[k_index] = temple; //记录index k_index = i; break; } } } if(i>=2 && i <= arrays.length-2){ sort(0,i-1,arrays); sort(i+1,arrays.length-1,arrays); } }