1指定数组中的数，通过把指定的数放在该放的位置上。把数组中的数每个都指定一遍，就实现排好序了，怎么把指定的数放在该放的位置上。数的前面所有数应该比它小。数的后面所有数应该比它大。这就是他该放的位置（相等的情况随便你放哪边）。具体实现指定数组两端的索引，这里以升序为例，保存数组中第一个数的值(从后遍历赋给第一个值，第一个值会被覆盖掉，所以要保存)从后遍历比指定数小的数，如果遍历到了，则赋给数组中的第一个值，前索引++,这时从后遍历到的数需要被替换掉，所以从前遍历比指定数大的数，遍历到了就赋给需要被替换掉的数。后索引--。进行循环一直到前索引等于后索引为止。这代表指定数的位置已经确定了。注意如果指定的数不是数组中第一个的话，需要把第一个值和指定数替换掉。(因为是将第一个数作为区分点的。比他小的数在它前面，比它大的数在它后面)，再从指定的数分为两个区间(指定数可以被除外)，重复上述逻辑。
2第二条思路，将同样指定数组中的某个数，但不需要保存第一个数的位置，从前遍历到比指定数大的数，从后遍历到比指定数小的数，交换他们，进行循环到前索引等于后索引为止。然后从指定数分为两个区间(指定数不可以被除外，因为不知道指定数的位置)。重复上述逻辑。这个思路是将数组分为两个区间，大的一个区间，小的一个区间，大区间，小区间看做一个整体是排好序的。然后不断细分，细分到区间大小只为1的时候，个体也就排好了序。
下面给出两种实现思想的Java源代码,都是随机化指定数(减小最坏情况的出现概率(比如差不多已经排好序的数组))quicksort1为思想1，quicksort2为思想2.在两个方法里面进行了调用次数计数。
public static void main(String[]args) {
int []nums={3,0,4,7,1,4,8,9,3,2,6,2,3,4,5,1,2,23};
quicksort1(nums,0,nums.length-1);
System.out.println(auto);
for(int i=0;i<nums.length;i++)
{
System.out.print(nums[i]+",");
}
}
static int auto=0;
static Random r= new Random();
static void quicksort2(int nums[],int start,int end)
{
auto++;
if(start<end){
int left =start;
int right =end;
//交换第一个数和指定数
int index =r.nextInt(end-start)+start;
int q = nums[index];
nums[index]=nums[start];
nums[start]=q;
int middle = nums[start];
while(left<right)
{
while(nums[right]>=middle&&left<right)
{
right--;
}
//
while(nums[left]<middle&&left<right)
{
left++;
}
if(left<right)
{
//System.out.println(left);
int temp=nums[left];
nums[left]=nums[right];
nums[right]=temp;
//System.out.println("交换"+temp+"和"+nums[left]);
}
}
quicksort2(nums,start,left);
quicksort2(nums,left+1,end);
}
}
static void quicksort1(int nums[],int start,int end)
{
auto++;
if(start<end)
{
int left = start;
int right = end;
int index =r.nextInt(end-start)+start;
//交换第一个数和指定数
int q = nums[index];
nums[index]=nums[start];
nums[start]=q;
int middle = nums[start];
while(left<right)
{
while(left<right&&nums[right]>=middle)
{
right--;
}
if(left<right)
{
nums[left++]=nums[right];
}
while(left<right&&nums[left]<middle)
{
left++;
}
if(left<right)
{
nums[right--]=nums[left];
}
}
nums[left]=middle;
quicksort1(nums,start,left-1);
quicksort1(nums,left+1,end);
}
}
21
0,1,1,2,2,2,3,3,3,4,4,4,5,6,7,8,9,23,
35
0,1,1,2,2,2,3,3,3,4,4,4,5,6,7,8,9,23,
明显第一种调用次数更少，所以推荐用第一种方法，网上写的也大多数是第一种。除了这基础的快排，还有其他种类的快排为了应付排序数组中的不同情况。这里不深究了，感兴趣的可以自行百度下。
