排序函数是一种插入排序法. 假设待排序的元素的类型为Item, 定义在其上的操作符有 less(比较两个关键字), exch(交换两个元素) 和 compexch(比较两个元素)

数组排序的例子

#include <stdio.h>
#include <stdlib.h>
typedef int Item;
#define key(A) (A)
#define less(A, B) (key(A) < key(B))
#define exch(A, B) { Item t = A; A = B; B = t; } 
//#define exch(A, B) { A = A^B; B = B ^ A;  A = A ^ B; } 
#define compexch(A, B) if (less(B, A)) exch(A, B)

/*
插入排序法.
非适应性插入排序
*/
void sort(Item a[], int l, int r) { 
  int i, j; 
  for (i = l+1; i <= r; i++) {
    for (j = i; j > l; j--) {
      compexch(a[j-1], a[j]);
    }
  }
}

/*
插入排序法. 对 sort 的一种改进
首先将数组最小的元素放在第一位, 当做观察哨
在内部循环中,只是做一个简单的赋值, 而不执行交换操作
当元素插入到正确的位置后就终止内存循环
运行时间和输入文件的原始顺序密切相关.
如果文件较大, 并且关键字已经排好序(或几乎排好序), 插入排序比选择排序要快.
*/
void insertion(Item a[], int l, int r) {
  int i;
  for ( i = r; i > l; i-- ) {
    compexch(a[i-1],a[i]);
  }
  for ( i = l+2; i <= r; i++ ) {
    int j = i;
    Item v = a[i];
    while ( less(v, a[j-1]) ) {
      a[j] = a[j-1];
      j--;
    }
    a[j] = v;
  }
}


/*希尔排序 其实是变种的插入排序*/
void shellsort(Item a[], int l, int r) {
  int i, j, h;
  for ( h = l; h <= (r-1)/9; h = 3*h+1 );
  //printf("%d\n", h );
  for ( ; h > 0; h /= 3) {
    for ( i = l+h; i <= r; i++ ) {
      int j = i;
      Item v = a[i];
      while ( j >= l+h && less(v,a[j-h]) ) {
        a[j] = a[j-h];
        j -= h;
      }
      a[j] = v;
    }
  }
}

/*
选择排序, 通过不断选出剩余元素中最小的元素来实现
缺点: 运行时间对文件中已有序的部分依赖较少.
对于元素比较大, 关键字又比较小的文件, 应该选择该方法, 而其他算法移动数据数据的步骤比选择排序要多.
*/
void selection(Item a[], int l, int r) {
  int i, j;
  for ( i = l; i < r; i++ ) {
    int min = i;
    for ( j = i+1; j <= r; j++ ) {
      if ( less(a[j], a[min]) ) {
        min = j;
      }
    }
    //if( i != min ) {
      exch( a[i], a[min] );  
    //}
    
  }
}

/*
冒泡排序实际上是一种选择排序, 但需要开销更多工作将每个元素放到合适的位置.
*/
void bubble(Item a[], int l, int r) {
  int i, j;
  for ( i = l; r < r; i++ ) {
    for ( j = r; j > i; j-- ) {
      compexch(a[j-1],a[j]);
    }
  }
}

main(int argc, char *argv[]) { 
  //int i, N = atoi(argv[1]), sw = atoi(argv[2]);
  int i, N, sw;
  N = 100;
  sw = 100;
  int *a = malloc(N*sizeof(int));
  if (sw) {
    for (i = 0; i < N; i++) {
         a[i] = 1000*(1.0*rand()/RAND_MAX); 
          printf("%3d \n", a[i]);   
    }     
  } else {
    while (scanf("%d", &a[N]) == 1) N++; 
  }
  //sort(a, 0, N-1);
  //selection(a,0,N-1);
  //insertion(a,0,N-1);
  shellsort(a,0,N-1);
  for (i = 0; i < N; i++) printf("%3d ", a[i]); 
    printf("\n");

  system("pause");
}