当前位置：首页 > article >正文

究极短的快排代码【QuickSort】

article 2025/3/10 3:49:36

快排 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);
}