快速排序模板1
//最后j会在i的前面或者和i相遇
public void quickSort(int[]q,int l,int r){
if(l>=r) return;
int i = l-1,j=r+1,x = q[l];
while(i<j){
while(q[i++]<x);
while(q[j--]>x);
if(i<j){
int temp = q[i];
q[i] = q[j];
q[j] = temp;
}
}
quickSort(q,l,j);
quickSort(q,j+1,r);
}
快速排序模板2
public void quickSort(int[]q,int l,int r){
if(l>=r) return;
int i = l, j = r, x = q[l];
while(i < j){
while(i<j&&x<=q[j]){
j--;
}
q[i] = q[j];
while(i<j&&x>q[i]){
i++;
}
q[j] = q[i];
}
q[j] = x;
quickSort(q,l,i);
quickSort(q,i+1,j);
}
对快速排序算法的主要总结
时间复杂度:
最好情况:O(nlogn)
最坏情况:O(n2)
平均情况:O(nlogn)
空间: O(logn)~O(n)
稳定性：是基于交换的,不稳定
