作者： yylogo

能够把中缀表达式转换成后缀表达式，是在为http://www.rqnoj.cn/Problem_18.html 这一题做准备，感觉写的还不错，关键是在优先级的处理方面（compare函数），整个代码如下(包含驱动函数main)：
只支持+-*^()和变量

#include <stdio.h>
#include <ctype.h>
#define MAX 101
#define NUM 0
#define CHAR 1
#define OPER 2
#define STR +-*^()
const unsigned used = 100000000;
#define bits 8
struct t{
 unsigned num[MAX];
 char type[MAX];
 int len;
}std;
unsigned stack[50];
int top;
#define push(a) ({stack[top++] = a;})
#define pop() ({stack[--top];})

void add(struct t *to, unsigned key, char type)
{
 to->num[to->len] = key;
 to->type[to->len] = type;
 to->len++;
}

int par[6][6] ={{-1, -1, 1, 1, 1, -1},
 {-1, -1, 1, 1, 1, -1},
 {-1, -1, -1, 1, 1, -1},
 {-1, -1, -1, -1, 1, -1},
 {1, 1, 1, 1, 1, 0},
 {-1, -1, -1, -1, 0, 1},};
/*
 0:加法
 1:减法
 2:乘法
 3:求幂
 4:正括号
 5:反括号
*/

int compare(int a, int b)
{
 char *i, *j;
 i = strchr(STR, a);
 j = strchr(STR, b);
 a = i - STR;
 b = j - STR;
 return par[a][b];
}

void change(struct t *to, char *from)
{
 int i, j;
 int ch;
 unsigned t;
 push(\'(\');
 for(i = 0; from[i] != \'\\0\'; i++){
 ch = from[i];
 if(strchr(STR, ch) != NULL){ /* 处理三种情况 */
 j = compare(stack[top - 1], ch);
 while(j < 0){
 add(to, pop(), CHAR);
 j = compare(stack[top - 1], ch);
 }
 if(j == 0){
 pop();
 }else{
 push(ch);
 }
 }else if(isdigit(ch)){
 t = 0;
 while(isdigit(from[i])){
 t *= 10;
 t += from[i++] - \'0\';
 }
 i--;
 add(to, t, NUM);
 }else if(ch == \'a\'){
 add(to, ch, OPER);
 }
 }
 while(top != 1){ /* 把最后几个符号去掉, 但是在函数
 开始加入的正括号不加入 */
 add(to, pop(), CHAR);
 }
}

int main(void)
{
 int i;
 char tmp[51];
 scanf(%s, tmp);
 change(&std, tmp);
 for(i = 0; i < std.len; i++){
 if(i != 0){
 printf( );
 }
 switch(std.type[i]){
 case NUM:
 printf(%u, std.num[i]);
 break;
 case CHAR:
 printf(%c, std.num[i]);
 break;
 case OPER:
 printf(%c, std.num[i]);
 break;
 }
 }
 printf(\\n);
 return 0;
}

插入排序其实很好理解，就是保证前i – 1个都是排好序了的，再排第i个，下面这个是从大到小排序的：

/* 从大到小的插入排序 */
void insert_sort(int a[], int n)
{
 int i, j;
 int key;
 for(i = 1; i < n; i++){
 key = a[i];
 for(j = i - 1; (j >= 0) && (key > a[j]); j--){
 a[j + 1] = a[j];
 }
 a[j + 1] = key;
 }
}

/* 驱动程序如下 */
int main(void)
{
 int a[10];
 int i;
 for(i = 0; i < 10; i++){
 scanf(%d, &a[i]);
 }
 insert_sort(a, 10);
 for(i = 0; i < 10; i++){
 printf(%d , a[i]);
 }
 return 0;
}

这函数真够长的，吓死！
记得我前两天看到别人做的一个程序，用的是自己写的快速排序，而我用的qosrt，结果我的100ms，他的350ms。这程序真贼快的
因为我把每天的倾城都安排好了，所以只有半个小时的时间看，所以没看完，先注释一部分吧，明天再补一部分，估计一下子还看不完。整个qsort的代码如下：

#include <alloca.h>
#include <limits.h>
#include <stdlib.h>
#include <string.h>

/* 交换一块内存数据, 长度为size字节 */
#define SWAP(a, b, size) \\
 do \\
 { \\
 register size_t __size = (size); \\
 register char *__a = (a), *__b = (b); \\
 do \\
 { \\
 char __tmp = *__a; \\
 *__a++ = *__b; \\
 *__b++ = __tmp; \\
 } while (--__size > 0); \\
 } while (0)

#define MAX_THRESH 4

typedef struct{
 char *lo;
 char *hi;
}stack_node;
/* 初步猜测lo和hi，的功能，根据下面的PUSH和POP宏, 估计是一段内存的两端
 lo就是low, hi就是high，就是说从low所指向的位置到hi所指向的位置就是
 这个元素的内容。 */

#define STACK_SIZE (CHAR_BIT * sizeof(size_t))
 /* 关于这个CHAR_BIT在网上搜了下，在limits.h文件中有定义:
 #define CHAR_BIT 8 */
#define PUSH(low, high) ((void)((top->lo = (low)), (top->hi = (high)), ++top))
#define POP(low, high) ((void)(--top, (low = top->lo), (high = top->hi)))
 /* 译(准确的说是注释的人:zqynux/My S-K-Y)者感到有点奇怪，
 能转换void这个类型 */
#define STACK_NOT_EMPTY (stack < top)
/* 上面三个都是超快速 + 简单的栈操作 */

void _quicksort (void *const pbase, size_t total_elems, size_t size,
 __compar_d_fn_t cmp, void *arg)
 /* 其实__compar_d_fn_t这个类型我没查也知道是什么类型, 就是一个函数指针,
 所以就没查了. */
{
 register char *base_ptr = (char *) pbase;
 const size_t max_thresh = MAX_THRESH * size;

 if(total_elems == 0)
 /* Avoid lossage with unsigned arithmetic below. */
 return;

 if(total_elems > MAX_THRESH){
 char *lo = base_ptr;
 char *hi = &lo[size * (total_elems - 1)];
 stack_node stack[STACK_SIZE];
 stack_node *top = stack;

 PUSH (NULL, NULL);

 while (STACK_NOT_EMPTY){
 char *left_ptr;
 char *right_ptr;

 /* Select median value from among LO, MID, and HI. Rearrange
 LO and HI so the three values are sorted. This lowers the
 probability of picking a pathological pivot value and
 skips a comparison for both the LEFT_PTR and RIGHT_PTR in
 the while loops. */

 char *mid = lo + size * ((hi - lo) / size >> 1);

 if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
 SWAP (mid, lo, size);
 if ((*cmp) ((void *) hi, (void *) mid, arg) < 0)
 SWAP (mid, hi, size);
 else
 goto jump_over;
 if ((*cmp) ((void *) mid, (void *) lo, arg) < 0)
 SWAP (mid, lo, size);
jump_over: ;

 left_ptr = lo + size;
 right_ptr = hi - size;

 /* Here\'s the famous ``collapse the walls\'\' section of quicksort.
 Gotta like those tight inner loops! They are the main reason
 that this algorithm runs much faster than others. */
 do{
 while ((*cmp) ((void *) left_ptr, (void *) mid, arg) < 0)
 left_ptr += size;

 while ((*cmp) ((void *) mid, (void *) right_ptr, arg) < 0)
 right_ptr -= size;

 if (left_ptr < right_ptr){
 SWAP (left_ptr, right_ptr, size);
 if (mid == left_ptr)
 mid = right_ptr;
 else if (mid == right_ptr)
 mid = left_ptr;
 left_ptr += size;
 right_ptr -= size;
 }else if (left_ptr == right_ptr){
 left_ptr += size;
 right_ptr -= size;
 break;
 }
 }while (left_ptr <= right_ptr);

 /* Set up pointers for next iteration. First determine whether
 left and right partitions are below the threshold size. If so,
 ignore one or both. Otherwise, push the larger partition\'s
 bounds on the stack and continue sorting the smaller one. */

 if ((size_t) (right_ptr - lo) <= max_thresh){
 if ((size_t) (hi - left_ptr) <= max_thresh)
 /* Ignore both small partitions. */
 POP (lo, hi);
 else
 /* Ignore small left partition. */
 lo = left_ptr;
 }else if ((size_t) (hi - left_ptr) <= max_thresh)
 /* Ignore small right partition. */
 hi = right_ptr;
 else if ((right_ptr - lo) > (hi - left_ptr)){
 /* Push larger left partition indices. */
 PUSH (lo, right_ptr);
 lo = left_ptr;
 }else{
 /* Push larger right partition indices. */
 PUSH (left_ptr, hi);
 hi = right_ptr;
 }
 }
 }

 /* Once the BASE_PTR array is partially sorted by quicksort the rest
 is completely sorted using insertion sort, since this is efficient
 for partitions below MAX_THRESH size. BASE_PTR points to the beginning
 of the array to sort, and END_PTR points at the very last element in
 the array (*not* one beyond it!). */

#define min(x, y) ((x) < (y) ? (x) : (y))

 {
 char *const end_ptr = &base_ptr[size * (total_elems - 1)];
 char *tmp_ptr = base_ptr;
 char *thresh = min(end_ptr, base_ptr + max_thresh);
 register char *run_ptr;

 /* Find smallest element in first threshold and place it at the
 array\'s beginning. This is the smallest array element,
 and the operation speeds up insertion sort\'s inner loop. */

 for (run_ptr = tmp_ptr + size; run_ptr <= thresh; run_ptr += size)
 if ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
 tmp_ptr = run_ptr;

 if (tmp_ptr != base_ptr)
 SWAP (tmp_ptr, base_ptr, size);

 /* Insertion sort, running from left-hand-side up to right-hand-side. */

 run_ptr = base_ptr + size;
 while ((run_ptr += size) <= end_ptr){
 tmp_ptr = run_ptr - size;
 while ((*cmp) ((void *) run_ptr, (void *) tmp_ptr, arg) < 0)
 tmp_ptr -= size;

 tmp_ptr += size;
 if (tmp_ptr != run_ptr){
 char *trav;

 trav = run_ptr + size;
 while (--trav >= run_ptr){
 char c = *trav;
 char *hi, *lo;

 for (hi = lo = trav; (lo -= size) >= tmp_ptr; hi = lo)
 *hi = *lo;
 *hi = c;
 }
 }
 }
 }
}