qsort() 简介 qsort()是一个内建於<stdlib.h>的函数 他会利用快速排序法(Quick Sort)，帮你在O(nlgn)[代表计算次数跟nlgn成正比] 的时间内排序，既快速又正确(如果你写对了XD)。 qsort()定义 void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) ); qsort()要做的事情 基本上qsort()要做的事情可以视为在一段记忆体上，有num个各占size bytes记忆体的 东西(一个int，连续几个int，一个字串...)，你要依照comparator的规则，将他们排序。 qsort()需要的东西 1.void* base ==> 起始指标 这是要排序的那段记忆体的第一个位置的指标， 也可以视为第一个要排序的东西的指标。 这边需要特别注意，这边丢进去的，是一个指标，而不是一整个阵列喔！ 2.size_t num ==> 东西个数 这是代表你有num个东西要排序 3.size_t size ==> 每个东西所占用记忆体(以byte计) 现在qsort()知道了一开始的指标，以及你有多少个东西需要排序 但是他不知道每一个东西到底用了多少记忆体，如果你用的是一个int， 那就是4bytes，如果你用了三个int，那就是12bytes... 如此一来，qsort()就可以很清楚的知道，记忆体的某一段到某一段就是某一个元素的位置 ，也才有办法做出比较、排序的动作。 4.int ( *comparator ) ( const void*, const void* ) ==> 比较函数 这里是一个qsort()内的函数指标，也是排序中最核心的部分 在排序的过程中，qsort()会多次呼叫这个函数，每次会丢入两个东西的指标 而这个函数的任务就是判断这两个东西的优先顺位，假如说丢入两个东西a、b 如果a的顺位在b前面，就输出一个负数；如果b的顺位在前面，就输出一个正数 而顺位相同的情况则输出0。 5.呼叫 qsort() 这里有个需要注意的地方，比较函数的部分 不是qsort(...,...,...,(*comparator)(const void *,const void *)); 函数指标的栏位，必须要引入你自己写的比较函数，例如： qsort(... , ... , ... , cmp); 这指标... 对你没看错，这些指标的型态，都是void*的型态，为什麽不是int*呢？ 原来，qsort()不只能够排序int的东西，还有很多很多型态的东西，qsort()都能够将他们 排序，但是每种型态占用的记忆体都不一样呀，所以像int*的ptr+1与double*的ptr+1就会 指向不同的记忆体，所以qsort()为了避免这样的情况，在宣告的时候预设都为void* (void*每个1byte)，需要比较、计算时，再让使用者转型成正在使用的型态。 所以比较函数怎麽办... 按照qsort()函数指标，我会有需要写一个比较函数是长下面这样子的 int cmp(const void* a,const void* b){ ... } 啊哈!!那我只要依照a,b他们优先顺位来输出负数、零、正数就好了嘛!! 不过等等，a是void的指标...那*a不就是void吗?! 那我要怎麽去比较啊!! 所以这时候就要做另外一件事情：指标转型 把void的指标转型成int的指标(或是你想要的东西的指标) 这样，加*取值回来就会是你要的形态了！ 给个范例：由小到大排序 int cmp( const void* a, const void* a ){ int* A = (int*) a;//将原本为void*的a转型为int*并指定给A int* B = (int*) b; if( *A < *B ) return -1; //若*A比*B小，代表A的顺位比较前面 else if( *A == *B ) return 0; else return 1; return 0; } ... qsort( array, n, sizeof(int), cmp ); ... 差不多到这里，qsort()也介绍完了，接下来讲几个大家比较常遇到的问题： 1.东西的大小塞错 假如说要对座标int array[100000][3]作排序， 应该是要qsort( array, n ,sizeof(int)*3 ,cmp); 或是qsort( array, n ,sizeof(array[0]) ,cmp);才对。 2.到底比较函数丢进来的指标是指到哪里？ 如果函数的引数没有打错，丢进来的指标应该是指到某一个东西最前面的指标 假如说丢进来的a是目前在第k格的指标，那a应该就会指到array[k][0]的位置，也就是说 a+1就是array[k][1]的位置，a+2就是array[k][2]的位置，所以三种愿望，一个指标就 让你满足了。 3.真的呼叫完这个qsort()，他就排好了吗?! 真的！ 最後补个八卦 你开灯了对吧wwwww -- Google 时の音の精灵| ████████▕検索▏検索オプション | 表示设定 ▇▇ ￣￣￣￣￣￣￣ ￣￣￣￣ 搜寻： ⊙ウェブ全体から検索 ○日本语のページを検索 ○萝莉検索 --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 123.192.77.105 ※ 编辑: hallogameboy 来自: 140.112.4.234 (10/28 14:41)