簡單分析 C 語言的 qsort() 源碼

stdlib.h 是使用 C 語言需要引入的庫，在系統檔案下可以搜尋到這個檔案夾，在裡面可以看到有一個 qsort() 檔案用編譯器或者記事本打開就能看到裡面的源碼了。

單從檔案名看，qsort() 采用的是快速排序算法，算法的時間複雜度為 O(nlogn) ，通常在企業的實際應用中對于快排這種 nlogn 複雜度的算法應用較多，對于 O(n) 例如 ：桶排序。等線性排序方法會使用的較少。以桶排序為例，需要開辟額外的記憶體空間隻适用于資料量大且密集的資料排序，例如聯考全國考生的分數排序，近千萬考生成績都位于 0 - 750 分這個區間，采用桶排序就可以極大的提高排序的效率，因為「 桶 」之間有着自帶的排序。

qsort() 是否全是使用快速排序

源碼中以下幾句話，設立 8 為使用快速排序和插入排序的分界點，當要排序的數組長度大于 8 時适合使用「 快速排序 」下與 8 時更适合使用「 插入排序 」

// This macro defines the cutoff between using QuickSort and insertion sort for
// arrays; arrays with lengths shorter or equal to the below value use insertion
// sort.
#define CUTOFF 8 // Testing shows that this is a good value.
           

qsort() 如何優化時間複雜度

插入排序的算法複雜度取決于分區點，如果是選擇數組的頭元素或是尾元素，出現最差時間複雜度此時 O(nlogn) 複雜度就會變成 O(n2) 。從 qsort() 的源碼中我們可以看到，它選擇的是 三數中值法。

注 ：mid 為中值點、lo 為左起始點 width 為單個元素的大小，mid = lo + (size / 2) * width 是為了防止兩數直接相加時「 上溢出 」。

// First we pick a partitioning element.  The efficiency of the
        // algorithm demands that we find one that is approximately the median
        // of the values, but also that we select one fast.  We choose the
        // median of the first, middle, and last elements, to avoid bad
        // performance in the face of already sorted data, or data that is made
        // up of multiple sorted runs appended together.  Testing shows that a
        // median-of-three algorithm provides better performance than simply
        // picking the middle element for the latter case.

        // Find the middle element:
        char* mid = lo + (size / 2) * width;

        // Sort the first, middle, last elements into order:
        if (__COMPARE(context, lo, mid) > 0)
            swap(lo, mid, width);

        if (__COMPARE(context, lo, hi) > 0)
            swap(lo, hi, width);

        if (__COMPARE(context, mid, hi) > 0)
            swap(mid, hi, width);

           

因為源碼中用了一些 goto 語句以及不是很明白的變量名，就不做細緻分析了，可以參照這篇文章連結

具體代碼已上傳至碼雲 源碼連結

也可以參考我參照《 資料結構與算法分析 —— C 語言描述 》寫的 快速排序（三數中值法）