15 half_sort.cpp

数据结构的必做编程题

#include <stdio.h>

int a[100],n;

void sort(){
	int i,j,t;
	int m,low,high;
	for(i=2;i<n;i++){
		t=a[i];
		low = 1;   high=i-1;
		while (low<=high) { 
			m = (low+high)/2;      // 折半
			if (a[i]<=a[m])
				high = m-1;        // 插入点在低半区
			else  low = m+1;        // 插入点在高半区
		}
		for ( j=i-1;  j>=high+1;  --j )	a[j+1]=a[j];
		a[j+1]=t;
	}
}

void main(){
	int b,i;
	i=1;
	a[0]=1;
  	printf("请输入数字（0为结束）\n");
	while(a[i-1]!=0){
		scanf("%d",&b);
		a[i]=b;
		i++;
	}
	n=i-1;
	sort();
	for(i=1;i<n;i++){
		printf("%d  ",a[i]);
	}
}