究极短的快排代码【QuickSort】

快排 QuickSort

两边向中间扫描法：取一个基点值，从左往右扫描，基点值左边所有元素小于它，遇到大于基点值的则停下，开始从右往左扫描，右边所有元素大于他，遇到小于基点值则停下，如果这时左右指针不交叉（左指针在基点左边，右指针在基点右边），则交换两个指针当前值，在每一次交换后两个指针均向右向左移动。依次递归则完成排序。

取中间值为基点，如果递归调用时将j换成i，那么x取值时需要向上取整，否则会造成边界问题

建议读者用不同的数组根据代码逻辑模拟 方便理解

void QuickSort(int a[] , int l , int r){
    if ( l >= r ) return ;
    int i = l - 1, j = r + 1, x = a[l + r >> 1] ; //注意x的取值与下面的函数递归调用的参数有关
    while( i < j ){
        while( a[++i] < x );
        while( a[--j] > x );
        if( i < j ) swap(a[i] , a[j]);
    }
    QuickSort(a , l , j);
    QuickSort(a , j + 1 , r);
}

---

void QuickSort(int a[] , int l , int r){
    if ( l >= r ) return ;
    int i = l - 1, j = r + 1, x = a[l + r + 1 >> 1] ; //注意x的取值与下面的函数递归调用的参数有关
    while( i < j ){
        while( a[++i] < x );
        while( a[--j] > x );
        if( i < j ) swap(a[i] , a[j]);
    }
    QuickSort(a , l , i - 1);
    QuickSort(a , i , r);
}

当给的序列元素全都一样时以下两种写法时间复杂度会退化到O(n ²)

void QuickSort(int a[] , int l , int r){
    if ( l >= r ) return ;
    int i = l - 1, j = r + 1, x = a[r] ;
    while( i < j ){
        while( a[++i] < x );
        while( a[--j] > x );
        if( i < j ) swap(a[i] , a[j]);
    }
    QuickSort(a , l , i - 1);
    QuickSort(a , i , r);
}

void QuickSort(int a[] , int l , int r){
    if ( l >= r ) return ;
    int i = l - 1, j = r + 1, x = a[l] ;
    while( i < j ){
        while( a[++i] < x );
        while( a[--j] > x );
        if( i < j ) swap(a[i] , a[j]);
    }
    QuickSort(a , l , j);
    QuickSort(a , j+1 , r);
}

求第K小元素

int QuickSort(int a[] , int l , int r , int k)
{
    if(l == r) return a[l];
    int x = a[l];
    int i = l - 1 , j = r + 1;
    while(i < j){
        while( a[++i] < x );
        while( a[--j] > x );
        if(i < j) swap(a[i],a[j]);
    }
    int len = j - l + 1;
    if( k <= len) return QuickSort(a, l , j , k);
    return QuickSort(a, j+1 , r , k - len);
}

求第K大元素

int QuickSort(int a[] , int l , int r , int k)
{
    if(l == r) return a[r];
    int x = a[r];
    int i = l-1 , j = r + 1;
    while(i<j){
        while(a[++i] < x);
        while(a[--j] > x);
        if(i < j) swap(a[i],a[j]);
    }
    int len = r - i + 1;
    if( k >= len) return QuickSort(a, l , i - 1 , k - len);
    return QuickSort(a, i , r , k);
}