通过递归算法对比基准值而进行快速的排序
快速排序利用分而治之的思想,它的最好和平均实际复杂度为O(nlogn),但是,如果选取基准的规则正好与实际数值分布相反,例如我们选取第一个数为基准,而原始序列是倒序的,那么每一轮循环,快排都只能把基准放到最右侧,故快排的最差时间复杂度为O(n2)。快排算法本身没有用到额外的空间,可以说需要的空间为O(1);对于递归实现,也可以说需要的空间是O(n),因为在递归调用时有栈的开销,当然最坏情况是O(n),平均情况是O(logn)。快速排序是不稳定的。
实现一 以左边第一个数为基准
public class QuickSort {
public static void main(String[] args) {
int[] arr={54,12,42,21,67,34,21};
quickSort(arr,0,arr.length-1);
}
//这个方法就是取找基准数的
private static void quickSort(int[] arr, int left, int right) {
// 递归需要出口
if(left > right){
return;
}
int i = left;
int j = right;
int baseNum = arr[left];
while( i != j){
while(arr[j] >= baseNum && j > i ){
j--;
}
while(arr[i] <= baseNum && i <j){
i++;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 相遇的基准数归位
arr[left] = arr[j];
arr[j] = baseNum;
quickSort(arr,left,i-1);
quickSort(arr,j+1,right );
}
}
实现二 取中间一个数为基准分界值
public class quickSort {
public static void main(String[] args) {
int[] arr={54,12,42,21,67,34,21};
System.out.println("排序前:"+ Arrays.toString(arr));
quickSort(arr,0,arr.length-1);
System.out.println("排序后:"+ Arrays.toString(arr));
}
public static void quickSort(int[] arr,int left,int right){
int ltemp=left,rtemp=right;
int temp,mid;
mid=arr[(left+right)/2]; //分界值
while(ltemp<rtemp){
while (arr[ltemp]<mid){
ltemp++;
}
while (arr[rtemp]>mid){
rtemp--;
}
if(ltemp<=rtemp){
temp=arr[ltemp];
arr[ltemp]=arr[rtemp];
arr[rtemp]=temp;
--rtemp;
++ltemp;
}
}
if(ltemp==rtemp){
ltemp++;
}
if(left<rtemp){
quickSort(arr,left,ltemp-1); //递归调用
}
if(ltemp<right){
quickSort(arr,rtemp+1,right); //递归调用
}
}
}
Post Views: 70