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,
明显第一种调用次数更少,所以推荐用第一种方法,网上写的也大多数是第一种。除了这基础的快排,还有其他种类的快排为了应付排序数组中的不同情况。这里不深究了,感兴趣的可以自行百度下。