这个题目使用快排。

这里涉及如何实现快排的问题。在[1]当中有一个快排的实现例子。在这里我们关注与快排的实现而不是这个问题本身，因为快排的问题解决了，这个问题就解决了

快排的思想是选择一个元素，从两边进行遍历将遇到的第一对不满足序列关系的元素进行交换。

关键是这里如何实现这种兑换

1、可以在同时找到这两个元素的时候进行交换

2、交替进行替换的策略。

比如先将左边位置left空出，从右边进行遍历找第一个小于pivot的元素以及所以right，将right位置的元素放到left处，同时将right位置空出

在从左边找第一个大于pivot的元素，当然现在left位置处的元素是小于pivot的，所以会继续left加一，直至找到一个大于等于pivot的元素或者right=left。

========================================================================================

left=0,right=num.length-1;

pivot = num[left];

while(left<right){

　　while(left<right&&num[right]>=pivot) right--;

　　　　num[left]= num[right];

　　while(left<right&&num[left]<pivot)     left++;

　　　　num[right]=num[left];

}

num[left]=pivot;

========================================================================================

我们简单分析一下代码的执行边界：

1、进入外层while循环，则开始找第一个小于pivot的元素

（1）如果在left的右侧找到，则填充到left位置处；

（2）如果没有找到，也就是说当前的元素都是大于等于pivot的；则第二个内层while循环当中由于left等于right，所以进行了自我复制，最后跳出while循环，并且在left或者right处写入pivot

（3）如果第二个while循环没有找到，也就是此时left右侧到right之间的所有元素都是小鱼pivot的，那么这是实际上已经找到了pivot插入的位置，就在刚才等待插入的right 处，算法结束。

 

 对于quick sort本身是可以使用迭代和递归两种方式实现的，这里同样的道理。

1 public class Solution { 2     private int quick2(int []nums,int start,int end,int k){ 3         int L =start; 4         int R = end; 5         while(L
     
      =target) right--;12                 nums[left]=nums[right];13                 while(left
      
       
        =target) right--;33             nums[left]=nums[right];34             while(left
       
      
     

 

[1]