排序算法的基本操作

////插入排序
//直接插入排序 
void insertSort(int a[],int n){
	int i,j;
	for(i=2;i<=n;i++){
		if(a[i]<a[i-1]){
			a[0] = a[i];
		    for(j=i-1;a[0]<a[j];--j){
			   a[j+1] = a[j];
		    }
		    a[j+1] = a[0];
		} 	
	} 
} 

//二分插入排序
void insertBiSort(int a[],int n){
	int i,j,low,high,mid;
	for(i=2;i<=n;i++){
		a[0] = a[i];
		low = 1; high = i-1;
		while(low<=high){
			mid = (low+high)/2;
			if(a[mid]>a[0]){
				high = mid-1;
			}else{
				low = mid+1;
			}
		}
		for(j=i-1;j>=high+1;j--){
			a[j+1] = a[j];
		}
		a[high+1] = a[0];
	}
} 

//希尔排序
void shellSort(int a[],int n){
	int dk,i,j;
	for(dk=n/2;dk>=1;dk=dk/2){
		for(i=dk+1;i<=n;++i){
			if(a[i]<a[i-dk]){
				a[0] = a[i];
				for(j=i-dk;j>0&&a[0]<a[j];j=j-dk){
					a[j+dk] = a[j];
				}
				a[j+dk] = a[0];
			}
		}
	}
} 

////交换排序 
//冒泡排序
void bubbleSort(int a[],int n){
	//为什么是n-1，因为i=n-1时下方的循环不做操作
	//其实i在这里<n或小于n-1均不影响操作，但使用n-1会少一次比较，推荐使用 
	for(int i=0;i<n-1;i++){
	   bool flag = false;
	   //为什么是n-1，因为下标到n-1 
	   for(int j=n-1;j>i;j--){
	   	 if(a[j-1]>a[j]){
	   	   int temp = a[j-1];
		   a[j-1] = a[j];
		   a[j] = temp;
		   flag = true;	
	     }
	   }
	   if(!flag)return;
	}
} 

//快速排序
int Partition(int a[],int low,int high){
	int pivot = a[low];
	while(low<high){
		while(low<high&&a[high]>pivot)high--;
		a[low] = a[high];
		while(low<high&&a[low]<pivot)low++;
		a[high] = a[low];
	}
	a[low] = pivot;
	return low;
}
void fastSort(int a[],int low,int high){
	if(low<high){
		int pivotpos = Partition(a,low,high);
		fastSort(a,low,pivotpos-1);
		fastSort(a,pivotpos+1,high);
	}
} 

////选择排序 
//堆排序
void headAdjust(int a[],int k,int len){
	a[0] = a[k];
	for(int i=2*k;i<=len;i*=2){
		if(i<len&&a[i]<a[i+1])i++;
		if(a[0]>a[i])break;
		else{
			a[k] = a[i];
			k = i;
		}
	}
	a[k] = a[0]; 
}

void buildMaxHeap(int a[],int len){
	for(int i=len/2;i>0;i--){
		headAdjust(a,i,len);
	}
}

void headSort(int a[],int n){
	buildMaxHeap(a,n);
	for(int i=n;i>1;i--){
		int temp = a[1];
		a[1] = a[i];
		a[i] = temp;
		headAdjust(a,1,i-1);
	}
}
//简单选择排序 
void selectSort(int a[],int n){
	for(int i=0;i<n-1;i++){
		int min = i;
		for(int j=i+1;j<n;j++){
			if(a[j]<a[min])min = j;
		}
		if(min!=i){
			int temp = a[i];
		    a[i] = a[min];
		    a[min] = temp;
		}	
	}
} 
//归并排序
int *b = (int*)malloc((MAXSIZE+1)*sizeof(int));
void merge(int a[],int low,int mid,int high){
	int i,j,k;
	for(k=low;k<=high;k++){
		b[k] = a[k];
	}
	for(i=low,j=mid+1,k=i;i<mid&&j<=high;k++){
		if(b[i]<=b[j])a[k] = b[i++];
		else a[k] = b[j++];
	}
	while(i<=mid)a[k++] = b[i++];
	while(j<=high)a[k++] = b[j++];
}

void mergeSort(int a[],int low,int high){
	if(low<high){
		int mid = (low+high)/2;
		mergeSort(a,low,mid);
		mergeSort(a,mid+1,high);
		merge(a,low,mid,high);
	}
}