快速排序算法模板

快速排序模板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)
稳定性：是基于交换的,不稳定