算法学习入门之使用C语言实现各大基本的排序算法

/*By Vamei*//*swap the neighbors if out of order*/void bubble_sort(int a[], int ac){  /*use swap*/  int i,j;  int sign;  for (j = 0; j < ac-1; j++) {    sign = 0;    for(i = ac-1; i > j; i--)    {      if(a[i-1] > a[i]) {        sign = 1;        swap(a+i, a+i-1);      }    }    if (sign == 0) break;  }}

/*By Vamei*//*insert the next element  into the sorted part*/void insert_sort(int a[], int ac){  /*use swap*/  int i,j;    for (j=1; j < ac; j++)   {    i = j-1;    while((i>=0) && (a[i+1] < a[i]))     {      swap(a+i+1, a+i);      i--;    }  }}

/*By Vamei*//*find the smallest of the rest, then append to the sorted part*/void select_sort(int a[], int ac) {  /*use swap*/  int i,j;  int min_idx;  for (j = 0; j < ac-1; j++)   {    min_idx = j;    for (i = j+1; i < ac; i++)     {      if (a[i] < a[min_idx])       {        min_idx = i;      }    }    swap(a+j, a+min_idx);  }  }

/*By Vamei*//*quickly sort the turtles at the tail of the array*/void shell_sort(int a[], int ac){  int step;  int i,j;  int nsub;  int *sub;  /* initialize step */  step = 1;  while(step < ac) step = 3*step + 1;  /* when step becomes 1, it's equivalent to the bubble sort*/  while(step > 1) {    /* step will go down to 1 at most */    step = step/3 + 1;    for(i=0; i<step; i++) {      /* pick an element every step,        and combine into a sub-array */      nsub = (ac - i - 1)/step + 1;            sub = (int *) malloc(sizeof(int)*nsub);      for(j=0; j<nsub; j++) {        sub[j] = a[i+j*step];       }      /* sort the sub-array by bubble sorting.        It could be other sorting methods */      bubble_sort(sub, nsub);      /* put back the sub-array*/      for(j=0; j<nsub; j++) {        a[i+j*step] = sub[j];      }      /* free sub-array */      free(sub);    }    }}

/*By Vamei*//*recursively merge two sorted arrays*/void merge_sort(int *a, int ac){  int i, j, k;    int ac1, ac2;  int *ah1, *ah2;  int *container;  /*base case*/    if (ac <= 1) return;  /*split the array into two*/  ac1 = ac/2;  ac2 = ac - ac1;  ah1 = a + 0;  ah2 = a + ac1;  /*recursion*/  merge_sort(ah1, ac1);  merge_sort(ah2, ac2);   /*merge*/  i = 0;  j = 0;  k = 0;  container = (int *) malloc(sizeof(int)*ac);  while(i<ac1 && j<ac2) {    if (ah1[i] <= ah2[j]) {      container[k++] = ah1[i++];    }     else {      container[k++] = ah2[j++];    }  }  while (i < ac1) {    container[k++] = ah1[i++];  }  while (j < ac2) {    container[k++] = ah2[j++];  }  /*copy back the sorted array*/  for(i=0; i<ac; i++) {    a[i] = container[i];  }  /*free space*/  free(container);}

/*By Vamei*//*select pivot, put elements (<= pivot) to the left*/void quick_sort(int a[], int ac){  /*use swap*/  /* pivot is a position,     all the elements before pivot is smaller or equal to pvalue */  int pivot;  /* the position of the element to be tested against pivot */  int sample;  /* select a pvalue.     Median is supposed to be a good choice, but that will itself take time.    here, the pvalue is selected in a very simple wayi: a[ac/2] */  /* store pvalue at a[0] */  swap(a+0, a+ac/2);  pivot = 1;   /* test each element */  for (sample=1; sample<ac; sample++) {    if (a[sample] < a[0]) {      swap(a+pivot, a+sample);      pivot++;    }  }  /* swap an element (which <= pvalue) with a[0] */  swap(a+0,a+pivot-1);  /* base case, if only two elements are in the array,    the above pass has already sorted the array */  if (ac<=2) return;  else {    /* recursion */    quick_sort(a, pivot);    quick_sort(a+pivot, ac-pivot);  }}

/* By Vamei   Use an big array to implement heap  DECLARE: int heap[MAXSIZE] in calling function  heap[0] : total nodes in the heap  for a node i, its children are i*2 and i*2+1 (if exists)  its parent is i/2 */void insert(int new, int heap[]) {  int childIdx, parentIdx;  heap[0] = heap[0] + 1;  heap[heap[0]] = new;    /* recover heap property */  percolate_up(heap);}static void percolate_up(int heap[]) {  int lightIdx, parentIdx;  lightIdx = heap[0];  parentIdx = lightIdx/2;  /* lightIdx is root? && swap? */  while((parentIdx > 0) && (heap[lightIdx] < heap[parentIdx])) {    /* swap */    swap(heap + lightIdx, heap + parentIdx);     lightIdx = parentIdx;    parentIdx = lightIdx/2;  }}int delete_min(int heap[]) {  int min;  if (heap[0] < 1) {    /* delete element from an empty heap */    printf("Error: delete_min from an empty heap.");    exit(1);  }  /* delete root     move the last leaf to the root */  min = heap[1];  swap(heap + 1, heap + heap[0]);  heap[0] -= 1;  /* recover heap property */  percolate_down(heap);   return min;}static void percolate_down(int heap[]) {  int heavyIdx;  int childIdx1, childIdx2, minIdx;  int sign; /* state variable, 1: swap; 0: no swap */  heavyIdx = 1;  do {    sign   = 0;    childIdx1 = heavyIdx*2;    childIdx2 = childIdx1 + 1;    if (childIdx1 > heap[0]) {      /* both children are null */      break;     }    else if (childIdx2 > heap[0]) {      /* right children is null */      minIdx = childIdx1;    }    else {      minIdx = (heap[childIdx1] < heap[childIdx2]) ?             childIdx1 : childIdx2;    }    if (heap[heavyIdx] > heap[minIdx]) {      /* swap with child */      swap(heap + heavyIdx, heap + minIdx);      heavyIdx = minIdx;      sign = 1;    }  } while(sign == 1);}

/* By Vamei *//* exchange the values pointed by pa and pb*/void swap(int *pa, int *pb){  int tmp;  tmp = *pa;  *pa = *pb;  *pb = tmp;}