[数据结构与算法]插入排序 、冒泡排序、选择排序、希尔排序、快速排序、归并排序、堆排序、基数排序的C语言实现

代码如下：

#include <iostream>

using namespace std;

//直接插入排序 
void InsertSort(int *a,int len){
	int i,j,tmp;
	for(i=1;i<len;i++){
	    tmp=a[i];
		for(j=i-1;j>=0;j--){
			if(tmp<a[j]){
				a[j+1]=a[j];
			}
			else break;
		}
		a[j+1]=tmp;
	}
}
// 冒泡排序
void Bubble(int *a,int len){
	int i,j;
	for(i=0;i<len-1;i++){
		for(j=0;j<len-1-i;j++){
			int tmp=a[j];
			if(a[j]>a[j+1])
			{
				a[j]=a[j+1];
				a[j+1]=tmp;
			}
		}
	}
} 

//选择排序
void Select(int *a,int len){
	int i, j;
	int min;
	for(i=0;i<len-1;i++)//选择次数
	{
		min=i;
		for(j=i+1;j<len;j++){
			if(a[j]<a[min]) min=j;
		} 
		if(min!=i){
			int tmp=a[i];
			a[i]=a[min];
			a[min]=tmp;
		}	
	} 	
} 
//希尔插入排序
//pos 数组开始位置，step 步数 
void group(int *a,int len,int pos,int step){
	int i,j,tmp;
	for(i=pos+step;i<len;i+=step){
		tmp=a[i];
		for(j=i-step;j>=0;j-=step){
			if(tmp<a[j]){
				a[j+step]=a[j];
			}else break;
		}
		a[j+step]=tmp;
	} 
}
void Shell(int *a,int len){
	int i,step;
	for(step=len/2;step>0;step/=2){
		for(i=0;i<step;i++){
			group(a,len,i,step);
		}
	} 
} 
//快速排序
void Quick(int *a,int len){
	if(len<2) return;
	int tmp=a[0];//基准数
	int left=0;
	int right=len-1;
	int moving=2;//1-移动左指针，2-移动右指针 
	
	while(left<right){
		if(moving==2){
			if(tmp<a[right]){
				right--;
				continue;
			}
			a[left]=a[right];
			left++;
			moving=1;
			continue;
		}
		if(moving==1){
			if(tmp>a[left]){
				left++;
				continue;
			}
			a[right]=a[left];
			right--;
			moving=2;
			continue;
		} 
	} 
	a[left]=tmp;
	Quick(a,left);
	Quick(a+left+1,len-1-left);	 
} 
//归并排序(只做有序的合并)
void merge1(int *a1,int *a2,int *a3,int len1,int len2){
	int i=0,left=0,right=0;
	while(left<len1&&right<len2){
		if(a1[left]<a2[right]){
			a3[i++]=a1[left++];
		}
		else a3[i++]=a2[right++];
	}
	while(left<len1) a3[i++]=a1[left++];
	while(right<len2) a3[i++]=a2[right++];

} 
//堆排序
void swap(int *a,int *b){
	int temp=*b;
	*b=*a;
	*a=temp;
}
void heapify(int *arr,int start,int end){
	int dad=start;
	int son=dad*2+1;
	
	if(son>end) return;
	
	if((son+1<=end)&&(arr[son]<arr[son+1])) son++;
	
	if(arr[dad]>arr[son]) return;

	swap(&arr[dad],&arr[son]);
	
	heapify(arr,son,end);	
}
void HeapSort(int *arr,int len){
	int i;
	for(i=(len-1)/2;i>=0;i--) heapify(arr,i,len-1);
	
	for(i=len-1;i>0;i--){
		swap(&arr[0],&arr[i]);
		heapify(arr,0,i-1);
	}
}
//基数排序
int findmax(int *arr,int len){
	int max=arr[0];
	for(int i=1;i<len;i++){
		if(arr[i]>max) max=arr[i]; 
	}
	return max;
} 
void RadixSort(int *arr,int base,int len){
	int i;
	int result[len];
	int bucket[10]={0};
	for(i=0;i<len;i++) bucket[(arr[i]/base)%10]++;
	
	for(i=1;i<10;i++) bucket[i]=bucket[i]+bucket[i-1];
	
	for(i=len-1;i>=0;i--){
		int exp=(arr[i]/base)%10;
		result[bucket[exp]-1]=arr[i];
		bucket[exp]--;
	}
	memcpy(arr,result,len*sizeof(int));
}
void Radix(int *arr,int len){
	int max=findmax(arr,len);
	int base;
	for(base=1;max/base>0;base*=10){
		RadixSort(arr,base,len);
	}
}
int main(){
	int arr[10]={1,2,3333,43,55,68,777,888,9,11};
//	int arr[10]={278,109,063,930,589,184,505,069,008,083 };
	int arr1[5]={10,11,12,13,14};
	
//	cout<<&arr[0]<<endl;
	int len=sizeof(arr)/sizeof(arr[0]);
	int len1=sizeof(arr1)/sizeof(int);
	
//	int arr2[len+len1];
//	merge1(arr,arr1,arr2,len,len1);
//	InsertSort(arr,len);
//	Bubble(arr,len);
//	Select(arr,len);
//	Shell(arr,len); 
//	Quick(arr,len);
//	HeapSort(arr,len);
	Radix(arr,len);
	for(int r=0;r<len;r++) cout<<arr[r]<<" ";
//	cout<<*(&arr[1]);
//	cout<<len<<sizeof(arr)<<" "<<sizeof(arr[0]);
	return 0;
}