abellong's Blog

c 语言的标准库有一个函数实现了快速排序----qsort().

man 3 qsort

看看 qsort 函数原型

void qsort(void *base, size_t nmemb, size_t size,
                  int(*compar)(const void *, const void *));

base 指向要排序的数组. 长度为 nmemb, 每个元素的大小是 size. compar 是比较函数, 如果第一个参数"小于"("等于", "大于")第二个参数, 那么比较函数返回一个负整数(0, 正整数). 数组按升序排序, 改变"小于"的定义就可以按需要的顺序排序了. 下面是 man page 里的一个程序例子, 这个程序将它的参数进行排序

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

static int
cmpstringp(const void *p1, const void *p2)
{
  /* The actual arguments to this function are "pointers to
     pointers to char", but strcmp(3) arguments are "pointers
     to char", hence the following cast plus dereference */

  return strcmp(* (char * const *) p1, * (char * const *) p2);
}

int
main(int argc, char *argv[])
{
  int j;

  if (argc < 2) {
    fprintf(stderr, "Usage: %s <string>...\n", argv[0]);
    exit(EXIT_FAILURE);
  }

  qsort(&argv[1], argc - 1, sizeof(argv[1]), cmpstringp);

  for (j = 1; j < argc; j++)
    puts(argv[j]);
  exit(EXIT_SUCCESS);
}

关键句

  qsort(&argv[1], argc - 1, sizeof(argv[1]), cmpstringp);

由于 qsort 函数第四个参数类型要求, 不能直接使用 strcmp 函数, 改写的 cmpstringp 函数的类型是:

int(*)(const void *, const void *)

这就符合要求了. qsort 的调用和函数 cmpstringp 的写法有些让人难懂.

我的理解:

&argv[1] 的类型为 char *, 作为实参传给 qsort 函数自动转变为 void * 型指针, 这样在 qsort 函数内部并不知道数组的类型(仅仅知道是void型数组), 因此需要一个参数 size 来标明数组元素的大小.

  return strcmp(* (char * const *) p1, * (char * const *) p2);

中的 *  (char * const *) p1 应该这么理解: 首先将 p1 转变成 (char * const  *) 型指针, 然后在作 * 运算, p1 is a pointer to a const pointer to char. 好费解!  *p1 是指向一个 (char * const) 数据, 即 (const char *)数据, 即常字符串. 关于const 的理解可以用"倒读"的方法, 见 const int vs. int const as function parameter in C++ and C 上 Ates Goral 的回答.

qsort 还能怎么用, 看看一个浮点数数组的排序该怎么写, 只需要改变比较函数就可以了

#define eps 0.000001
int numcmp(const void *x,const void *y){  // 排序比较函数
  float z=*((double*)x)-*((double*)y);
  if(z>eps) return 1;
  if(z<-eps)	return -1;
  return 0;
}

要排序的数组为 price, 如此调用即可:

float price[10] = {32.0, 12, 8, 45.1,
                         13, 30, 53.2, 34.1, 80, 22}
qsort(price, 10, sizeof(float), numcmp);

大半学期过去，还没交过作业，上上周密码学老师要我们设计一个流密码当作业这周交。俺刚刚学了比较流行的RC4，把自己所学分享出来吧

for i from 0 to 255
    S[i] := i
endfor
j := 0
for i from 0 to 255
    j := (j + S[i] + key[i mod keylength]) mod 256
    swap values of S[i] and S[j]
endfor

i := 0
j := 0
while GeneratingOutput:
    i := (i + 1) mod 256
    j := (j + S[i]) mod 256
    swap values of S[i] and S[j]
    K := S[(S[i] + S[j]) mod 256]
    output K
endwhile