C程序快速排序之qsort()函數

qsort包含在<stdlib.h>頭文件中，此函數根據你給的比較條件進行快速排序，通過指針移動實現排序。其排序是根據二分法寫的，其時間復雜度為n*log(n)。排序之後的結果仍然放在原數組中。使用qsort函數必須自己寫一個比較函數。
其實qsort的用法跟sort十分的相像。關於sort的用法見下一篇文章 http://www.linuxidc.com/Linux/2012-05/59453.htm 。

函數原型：

void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );

用法以及參數說明：

base：Pointer to the first element of the array to be sorted.(數組起始地址)
num：Number of elements in the array pointed by base.(數組元素個數)
size：Size in bytes of each element in the array.(每一個元素的大小)
comparator： Function that compares two elements.(函數指針，指向比較函數)
1、The function must accept two parameters that are pointers to elements, type-casted as void*. These parameters should be cast back to some data type and be compared.
2、The return value of this function should represent whether elem1 is considered less than, equal to, or greater than elem2 by returning, respectively, a negative value, zero or a positive value.
Return Value none (無返回值)

用法舉例：

一、對int類型數組排序

int num[100];

int cmp ( const void *a , const void *b )
{
      return *(int *)a - *(int *)b;
}

qsort(num, 100, sizeof(num[0]), cmp);

二、對char類型數組排序（同int類型）

char word[100];

int cmp( const void *a , const void *b )
{
      return *(char *)a - *(int *)b;
}

qsort(word,100,sizeof(word[0]),cmp);

三、對double類型數組排序

double in[100];

int cmp( const void *a , const void *b )
{
      return *(double *)a > *(double *)b ? 1 : -1;//因為自定義函數的返回值必須是int型，所以這裡不能直接相減
}

qsort(in,100,sizeof(in[0]),cmp);

四、對結構體一級排序

struct Sample
{
      double data;
      int other;
}s[100]

//按照data的值從小到大將結構體排序

int cmp( const void *a ,const void *b)
{
return (*(Sample *)a).data > (*(Sample *)b).data ? 1 : -1;
}

qsort(s,100,sizeof(s[0]),cmp);

五、對結構體二級排序

struct Sample
{
int x;
int y;
}s[100];

//按照x從小到大排序，當x相等時按照y從大到小排序

int cmp( const void *a , const void *b )
{
struct Sample *c = (Sample *)a;
struct Sample *d = (Sample *)b;
if(c->x != d->x) return c->x - d->x;
else return d->y - c->y;
}

qsort(s,100,sizeof(s[0]),cmp);

六、對字符串進行排序

struct Sample
{
      int data;
      char str[100];
}s[100];

//按照結構體中字符串str的字典順序排序

int cmp ( const void *a , const void *b )
{
      return strcmp( (*(Sample *)a).str , (*(Sample *)b).str );
}

qsort(s,100,sizeof(s[0]),cmp);

七、對字符串二維數組排序：

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

char s[2001][1001];

int cmp(const void *a, const void *b){
return strcmp((char *)a,(char *)b);
}

int main(){
int i,n;
scanf("%d",&n);
getchar();
for(i=0;i<n;i++) gets(s[i]);
qsort(s,n,1001*sizeof(char),cmp);
for(i=0;i<n;i++) puts(s[i]);
return 0;
}