采用分治的思想，首先选取一个基准值pivot，然后将小于基准值的数放到左边，大于基准值的数放到右边。而对于左边的部分和右边的部分同样的采用这种方法，这样递归下去，当所需要排序的子区间的数小于2时，递归结束，此时序列也拍好了。
待排序列： 55 26 90 8 72 82 9 13
假设对于整个代排序列选取55作为基准值（基准值理论上可以随机选取，但是这里为了方便，选择第一个值为基准值）。那么第一次将待排序列分解为两个部分后（基准值左边的待排序列和基准值后边的待排序列），实际上这一个过程对基准值的正确位置已经确定下来了。基准值左边的数都会比它，基准值右边的数都会比它更大。
第一次：（比55小的数） 55 （比55小的数）
由于有很多种方法来进行这一个过程，所以比55小的数和大的这两个待排子序列里面的数字在第一次排序后的相对位置是不固定的，但是无论哪种，基准值55肯定是在第5个位置（因为比55小的有4个）。
同样的方法递归的进行这一个过程到待排序列只有1个或0个的时候就结束。下面列举其中的一种可能情况。
第一次：13 9 8 55 72 82 90
第二次：8 9 13 55 72 82 90
第三次：8 9 13 55 72 82 90
由于算法将待排序列分为两个部分，所以算法的时间复杂度是T(N)=To(N/2)+确定基准值正确位置的算法时间复杂度
一种确定基准值的正确位置的做法：
选择待排序列的头部或者尾部的数作为基准值，然后设置两个指针i、j 。初始位置一个在头部，一个在尾部。如果是选择左边的作为基准值，那么首先从后边的指针所指的值进行比较，如果比基准值更大，那么将指针左移，然后继续比较下一个值和基准值的大小，同样的，如果更大，左移，这样可以保证指针j后边的值都是比基准值更大的。如果比较发现更小，交换i指针初始所指的基准值的位置和这个数的位置，此时i的位置的数变成了比基准值更小的数，j所指的数是基准值（也可以不用管，直接将那个更小的数放那）。然后将i指针右移，如果这个数小于j指针所指的基准值，继续右移，这样可以保证i指针左边的数都是小于基准值的数，如果是大于j指针所指的基准值，继续交换i和j所指位置的数，又从j位置继续扫描，直到两个指针交会，这样就说明整个这个待排的序列已经过了一遍了，而且是i左边的小于基准值，j右边的大于基准值。
这种是基准值跟着一起动的，还可以基准值不用跟着动，因为每次都是交换基准值的位置，基准值可以最后填入，填入的位置是i和j指针交会的位置。
这种方法的交换的次数，取决于基准值的选择，如果不考虑交换或者说复制开销，比较的开销是N-1,即所有的数都和基准值进行了比较。
所以T(N)=2T(N/2)+N=4T(N/4)+2N=2^n T(N/2^n)+nN
T(1)=0 令N=2^n T(N)=2^n 所以T(N)=NlogN
所以这种快速排序算法的时间复制度是nlog(n)。
java代码实现
public static void quick_sort(int [] arr,int i ,int j){
if(i<j){ //递归结束限制
int mid=partition(arr,i,j)//大的序列排序，获得基准值正确的位置
quick_sort(arr,i,mid-1);
quick_sort(arr,mid+1,j); //递归调用
}
}
public static int partition(int []arr,int low ,int high){ //排序的方法
int pivot=arr[low];设置基准值
int i=low;
int j=high;
while(i<j){ //待排的只有一个的情况不会进入这个循环
while(arr[j]>=pivot&&i<j)
j--;
a[i]=a[j];
while(arr[i]<=pivot&&i<j)
i++;
a[j]=a[i];
}
arr[i]=pivot;
return i;
}
网友评论