Java快速排序QuickSort(实例)

快速排序

----------------------------------------------------------------------

思想

如上图：每趟快速排序开始时，设置一个key，key=array[low]，然后由high向左，找到小于key的值，复制到low位置，然后再由low向右找到大于key的值，复制到high位置，直到low=high结束，

将key的复制到low位置。

上图中第一轮划分后找到32的位置，然后递归的对32左边和右边的进行排序。

代码：

package Sort;
import java.util.Arrays;
public class QuickSort {

public static void main(String[] args) {
 int array[]={32, 12, 7, 78, 23, 45};
 quickSort(array,0,array.length-1);
 System.out.println(Arrays.toString(array));
}
public static void quickSort(int array[],int left,int right)
{
 if(left>=right)
 {
  return ;
 }
 int i=left;
 int j=right;
 int key=array[left];
 while(i<j)
 {
  while(i<j&&array[j]>key)
  {
   j--;
  }
  array[i]=array[j];
  //从后往前找到第一个比key小的数与array[i]交换；
  while(i<j&&array[i]<key)
  {
   i++;
  }
  array[j]=array[i];
  //从前往后找到第一个比key大的数与array[j]交换；
 }
 array[i]=key;
 //一趟快排之后已经将key的位置找到。
 quickSort(array,left,i-1);
 //对key左边的进行排序
 quickSort(array,i+1,right);
 //对key右边的进行排序
}
}

来源：http://blog.csdn.net/u013309870/article/details/68921848