快速排序模板1

//最后j會(huì)在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);
}

對(duì)快速排序算法的主要總結(jié)

時(shí)間復(fù)雜度:
最好情況:O(nlogn)
最壞情況:O(n2)
平均情況:O(nlogn)
空間: O(logn)~O(n)
穩(wěn)定性：是基于交換的,不穩(wěn)定