bubble.c

建队列,销毁队列,入队,出队,求队列长度,判断队空,显示队列。

/* 两种起泡排序中比较次数对比。排序过程中后半有序区逐渐增长 */
#include <stdio.h>
#include <stdlib.h>
#define M 20

int r[M],s[M],i,j,change;
long count;

void bubble_sort(int a[ ], int n){  /* 扫描范围(无序区)每次缩小1 */
int temp;
  for (i=n-1, change =1; i>=1&&change; --i){
    change = 0;
    for (j = 0; j<i; ++j){
      if (a[j]>a[j+1]) {
	temp=a[j]; a[j]=a[j+1];
	a[j+1]=temp; change = 1;   /* 若有交换用change标记 */
      } count++;
    }
  }
}

void bubble_sort1(int a[ ], int n){  /* 改进的算法,每次只扫描实际的无序区 */
int temp;
  i=n-1;              /* i为前半无序区的后界 */
  while(i>0){
    change = 0;
    for (j = 0; j<i; j++){
      if (a[j]>a[j+1]) {
	temp=a[j]; a[j]=a[j+1];
	a[j+1]=temp; change = j;   /* change记录出现交换的位置 */
      } count++;
    }
    i=change;  /* 最后的交换位置即为前半无序区的后界 */
  }
}
void main(){
  randomize();
  for(i=0;i<M;i++){ r[i]=s[i]= random(M); }
  printf("\nn=%d first:\n",M);
  for(i=0;i<M;i++) printf("%8d",r[i]);
  count=0; bubble_sort(r,M);
  printf("\nafter sort(count=%ld):\n",count);
  for(i=0;i<M;i++) printf("%8d",r[i]);
  count=0; bubble_sort1(s,M);
  printf("\nafter sort1(count=%ld):\n",count);
  for(i=0;i<M;i++) printf("%8d",s[i]);

}