算法基础：快排优化：为什么qsort会这么快

Love The Way You Lie 2022-11-21 14:44 172阅读 0赞

这篇文章走马观花地学习一下qsort的源码，来看一下为何qsort比我们自己写的快排会快这么多。

### 目录 ###

*  快排与超时
 *  qsort的实现方式
 *   *  基准值的优化
     *  去除递归调用
     *  小的分区先入栈
     *  结合插入排序
 *  总结
 *  附录：qsort部分核心代码
 *  参考内容

--------------------

# 快排与超时 #

我家ACM金奖大神说，从来没有见过快排还不能AC的，正在与基础努力奋斗的小朋友和中老年人同时心里一凉，于是立马调出qsort和sort进行作弊，忧郁的心情顿时得到了缓解。

#include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <time.h>
    int compare(const void * a, const void * b) { 
        return *((const int *)a) - *((const int *)b);
    }
    int main() { 
        int n = 0;
        while (scanf("%d",&n) != EOF) { 
            int* array = (int *)malloc(sizeof(int)*n);
            memset(array,0,sizeof(int)*n);
            for (int i=0; i<n; i++) array[i]=i+1;
            time_t start_time, end_time;
            start_time=clock();
            qsort(array,n,sizeof(int),compare);
            end_time=clock();
            printf("Time Used: %fs\n",(double)(end_time-start_time)/CLOCKS_PER_SEC);
            free(array); array= NULL;
        }
    }

执行之后结果如下，效率比对照答案使用折半查找pivot还要快，确实效果非常之好。

100000
    Time Used: 0.000590s
    10000000
    Time Used: 0.061244s

--------------------

# qsort的实现方式 #

qsort是标准库中的实现，我们这里对照其中一种的具体实现方式（GLIBC），来看一下为什么会这么快，参考代码如下所示：

*  [https://elixir.bootlin.com/glibc/glibc-2.32/source/stdlib/qsort.c][https_elixir.bootlin.com_glibc_glibc-2.32_source_stdlib_qsort.c]

对于qsort的实现的核心代码进行分析可以发现如下特点

## 基准值的优化 ##

*  在前面的文章中我们使用了折半和随机方式的基准值方式，而qsort中所谓的三数中值分割法，查看此部分源码如下：

char *mid = lo + size * ((hi - lo) / size >> 1);

翻译一下：mid = low + (high - low)/2

> 通过翻译可以看到，这就是折半方式，在前面的文章中，我还一直认为随机方式效果更好一点，现在看一下qsort，它已经缺省认为折半效果更好，觉今是而昨非。

## 去除递归调用 ##

*  避免了传统快排中使用递归方式的调用引入的效率降低，使用栈的方式来解决问题，另外不惜引入goto语句来进行跳转以降低递归的效率的提升。

## 小的分区先入栈 ##

*  每次使用分割算法分割分区的时候，都取保小的分区先入栈。

## 结合插入排序 ##

*  对于整体已排序的大的数据序列，插入排序具有无可伦比的优势，这里也结合了插入排序，整体来说只对小范围进行快排，大量数据的排序结合插入排序保证效率。

# 总结 #

可以看到qsort为了快，弃用递归不惜使用goto，使用栈结构，结合插入排序提升整体效率等都是qsort为什么这么快的原因，值得我们进一步地学习。

# 附录：qsort部分核心代码 #

if (total_elems > MAX_THRESH)
        { 
          char *lo = base_ptr;
          char *hi = &lo[size * (total_elems - 1)];
          stack_node stack[STACK_SIZE];
          stack_node *top = stack;
    
          PUSH (NULL, NULL);
    
          while (STACK_NOT_EMPTY)
            { 
              char *left_ptr;
              char *right_ptr;
    
    	  /* Select median value from among LO, MID, and HI. Rearrange LO and HI so the three values are sorted. This lowers the probability of picking a pathological pivot value and skips a comparison for both the LEFT_PTR and RIGHT_PTR in the while loops. */
    
    	  char *mid = lo + size * ((hi - lo) / size >> 1);
    
    	  if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
    	    SWAP (mid, lo, size);
    	  if ((*cmp) ((void *) hi, (void *) mid, arg) < 0)
    	    SWAP (mid, hi, size);
    	  else
    	    goto jump_over;
    	  if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
    	    SWAP (mid, lo, size);
    	jump_over:;
    
    	  left_ptr  = lo + size;
    	  right_ptr = hi - size;
    
    	  /* Here's the famous ``collapse the walls'' section of quicksort. Gotta like those tight inner loops! They are the main reason that this algorithm runs much faster than others. */
    	  do
    	    { 
    	      while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0)
    		left_ptr += size;
    
    	      while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0)
    		right_ptr -= size;
    
    	      if (left_ptr < right_ptr)
    		{ 
    		  SWAP (left_ptr, right_ptr, size);
    		  if (mid == left_ptr)
    		    mid = right_ptr;
    		  else if (mid == right_ptr)
    		    mid = left_ptr;
    		  left_ptr += size;
    		  right_ptr -= size;
    		}
    	      else if (left_ptr == right_ptr)
    		{ 
    		  left_ptr += size;
    		  right_ptr -= size;
    		  break;
    		}
    	    }
    	  while (left_ptr <= right_ptr);
    
              /* Set up pointers for next iteration. First determine whether left and right partitions are below the threshold size. If so, ignore one or both. Otherwise, push the larger partition's bounds on the stack and continue sorting the smaller one. */
    
              if ((size_t) (right_ptr - lo) <= max_thresh)
                { 
                  if ((size_t) (hi - left_ptr) <= max_thresh)
    		/* Ignore both small partitions. */
                    POP (lo, hi);
                  else
    		/* Ignore small left partition. */
                    lo = left_ptr;
                }
              else if ((size_t) (hi - left_ptr) <= max_thresh)
    	    /* Ignore small right partition. */
                hi = right_ptr;
              else if ((right_ptr - lo) > (hi - left_ptr))
                { 
    	      /* Push larger left partition indices. */
                  PUSH (lo, right_ptr);
                  lo = left_ptr;
                }
              else
                { 
    	      /* Push larger right partition indices. */
                  PUSH (left_ptr, hi);
                  hi = right_ptr;
                }
            }
        }

# 参考内容 #

https://elixir.bootlin.com/glibc/glibc-2.32/source/stdlib/qsort.c

[https_elixir.bootlin.com_glibc_glibc-2.32_source_stdlib_qsort.c]: https://elixir.bootlin.com/glibc/glibc-2.32/source/stdlib/qsort.c