期望时间复杂度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
     
       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);       }    }