2016年7月3日 星期日

C語言標準函式庫下的排序函數qsort

用C寫程式時，有很多機會可以用到排序法，但全部自己實作，感覺起來真的太累了！...QAQ

在找尋偷懶方法前人智慧時，找到了在標準函數庫(stdlib.h)下的qsort函數，沒想到標準函數庫早已準備好現成的偷懶方法函數了！

qsort有什麼特點呢？

優點：
  1. 由於是標準，所以跨平台沒問題~
  2. 偽泛型，只要提供比較用的函數，可排序各種型別的陣列。
  3. 現成的排序法，懶人好物www
缺點：
  1. 只能對陣列使用，鏈結串列什麼的，通通不認識！
  2. 要知道函數指標，提供規定的比較函數，但這應該不是大問題XD
  3. 請瞭解指標~

函數解析

void qsort(
    void *base,
    size_t n,
    size_t size,
    int ((compare) (const void *, const void *)
)
  1. base：陣列的起始位址。
  2. n：陣列元素數量。
  3. size：陣列的型別大小，sizeof是您的好朋友。
  4. compare：比較函數的指針，回傳整數，輸入不能兩個更改目標資料的指針。
注：void類型的指針，可以指向任何類型，所以可以達成類似泛型的功能。

實彈操演

題目：有5位學生，須以總分排序、國文、英文、數學作順序排列。

#include <stdio.h>
#include <stdlib.h>

#define ARRAY_MAX 5

typedef struct _Classmate
{
           int chinese, english, math;
}Classmate;

/*
傳回-1代表 a < b
傳回 0代表 a = b
傳回 1代表 a > b
*/
int compare(const Classmate *a, const Classmate *b)
{
           /* 總分比較 */
           if (a->chinese + a->english + a->math !=
                     b->chinese + b->english + b->math)
                     return (a->chinese + a->english + a->math <
                                b->chinese + b->english + b->math) ? -1 : 1;

           /* 先比國文 */
           if (a->chinese != b->chinese)
                     return (a->chinese < b->chinese) ? -1 : 1;

           /* 在比英文 */
           if (a->english != b->english)
                     return (a->english < b->english) ? -1 : 1;

           /* 最後數學 */
           if (a->math != b->math)
                     return (a->math < b->math) ? -1 : 1;

           /* 全部相等 */
           return 0;
}

void printAll(Classmate *classmate)
{
           int i;
           for (i = 0; i < ARRAY_MAX; i++)
           {
                     printf("[%02d] %3d + %3d + %3d = %3d\n",
                                i + 1,
                                classmate[i].chinese,
                                classmate[i].english,
                                classmate[i].math,
                                classmate[i].chinese + classmate[i].english + classmate[i].math
                     );
           }
}

int main(int argc, char *argv[])
{
           Classmate classmate[ARRAY_MAX] = {
                     {  50,  75, 90 },
                     {  30,  46, 50 },
                     { 100,  80, 60 },
                     {  55,  55, 80 },
                     {  95, 100, 70 }
           };

           printf("====== 排序前 ======\n");
           printAll(classmate);

           qsort(
                     classmate,
                     ARRAY_MAX,
                     sizeof(Classmate),
                     compare
           );

           printf("\n====== 排序後 ======\n");
           printAll(classmate);

           return 0;
}

輸出

====== 排序前 ======
[01]  50 +  75 +  90 = 215
[02]  30 +  46 +  50 = 126
[03] 100 +  80 +  60 = 240
[04]  55 +  55 +  80 = 190
[05]  95 + 100 +  70 = 265

====== 排序後 ======
[01]  30 +  46 +  50 = 126
[02]  55 +  55 +  80 = 190
[03]  50 +  75 +  90 = 215
[04] 100 +  80 +  60 = 240
[05]  95 + 100 +  70 = 265

參考資料

張貼者： 於
標籤： , , , , ,

沒有留言:

張貼留言

訂閱： 張貼留言 (Atom)