www.pudn.com > all_sort.rar > all_sort.cpp

#include 
#include 
#include 
#include 
#define MAX_NUM_OF_KEY 8 
#define RADIX 10 
#define MAXSIZE 20001		//元素最大个数1,000,000 
#define MAX	10000			    //最大数100,000 
//堆结构 
typedef struct Heap 
{ 
	int heap_arr[MAXSIZE]; 
	int maxsize; 
	int currentsize; 
}Heap,*Heap_Tree; 
//初始化堆 
void initHeap(Heap_Tree &he,int mx) 
{ 
	he = (Heap_Tree)malloc(sizeof(Heap)); 
	he->currentsize=0; 
	he->maxsize=mx; 
} 
//堆是否为空 
bool isEmpty(Heap_Tree he) 
{ 
	return he->currentsize==0; 
} 
//向上调整堆 
void trickleUp(Heap_Tree &he,int index) 
{ 
	int parent = (index-1)/2; 
	int bottom = he->heap_arr[index]; 
	while(index>0&&he->heap_arr[parent]>bottom) 
	{ 
		he->heap_arr[index] = he->heap_arr[parent]; 
		index = parent; 
		parent = (parent-1)/2; 
	} 
	he->heap_arr[index]=bottom; 
} 
//在堆中插入元素 
bool insertHeap(Heap_Tree &he,int elem) 
{ 
	if(he->currentsize==he->maxsize) return false;//heap is full 
	he->heap_arr[he->currentsize]=elem; 
	trickleUp(he,he->currentsize); 
	he->currentsize++; 
	return true; 
} 
//向下调整 
void trickleDown(Heap_Tree &he,int index) 
{ 
	int smallerChild; 
	int size = he->currentsize; 
	int top = he->heap_arr[0]; 
	while(indexheap_arr[leftChild]>he->heap_arr[rightChild]) 
			smallerChild = rightChild; 
		else smallerChild = leftChild; 
		if(top<=he->heap_arr[smallerChild]) break; 
		he->heap_arr[index] = he->heap_arr[smallerChild]; 
		index = smallerChild; 
	} 
	he->heap_arr[index]=top; 
} 
//从堆里删除元素 
bool removeHeap(Heap_Tree &he,int &elem) 
{ 
	if(he->currentsize==0) return false;  //heap is empty 
	elem = he->heap_arr[0]; 
	he->heap_arr[0] = he->heap_arr[--he->currentsize]; 
	trickleDown(he,0); 
	return true; 
} 
//改变堆里的某个元素 
bool change(Heap_Tree &he,int index,int newValue) 
{ 
	int size = he->currentsize; 
	if(index<0||index>size) return false; 
	int oldValue = he->heap_arr[index]; 
	he->heap_arr[index] = newValue; 
	if(oldValue < newValue) 
		trickleUp(he,index); 
	else if(oldValue >newValue) 
		trickleDown(he,index); 
	return true; 
} 
//交换元素 
void swap(int arr[],int i,int j) 
{ 
	int temp = arr[i]; 
	arr[i] = arr[j]; 
	arr[j] = temp; 
} 
//冒泡排序 
void bubbleSort(int arr[],int size) 
{ 
	int in,out; 
	for(out= size-1;out>1;out--) 
	{ 
		for(in =0;inarr[in+1]) 
				swap(arr,in,in+1); 
		} 
	} 
} 
//选择排序 
void selectionSort(int arr[],int size) 
{ 
	int in,out,max; 
	for(out=0;outarr[in]) 
				max=in; 
		swap(arr,out,max); 
	} 
} 
//插入排序 
void insertSort(int arr[],int size) 
{ 
	int in,out; 
	for(out=1;out0&&arr[in-1]>=temp) 
		{ 
			arr[in]=arr[in-1]; 
			in--; 
		} 
		arr[in]=temp; 
	} 
} 
//堆排序 
void heapSort(int arr[],int size) 
{ 
	Heap_Tree he; 
	initHeap(he,size); 
	int i = 0; 
	for(i=0;i < size;i++) 
	{ 
		insertHeap(he,arr[i]); 
	} 
	for(i = 0;i < size;i++) 
	{ 
		int elem; 
		removeHeap(he,elem); 
		arr[i]=elem; 
	} 
} 
//希尔排序 
void shellSort(int arr[],int size) 
{ 
	int in,out; 
	int temp; 
	int h = 1;				//Knuth间隔序列{1，4，13，40，121...} 
							//开始间隔应该很大，然后逐渐变小，直至间隔为1	 
							//通过前面的希尔排序，数组已经基本有序，这就是希尔排序的优势 
	while(h <=size/3)		h = h*3+1; 
	while(h>0) 
	{ 
		for(out=h;outh-1&&arr[in-h]>=temp)//插入排序 
			{ 
				arr[in] = arr[in-h]; 
				in -= h; 
			} 
			arr[in]=temp; 
		} 
		h = (h-1)/3; 
	} 
} 
//归并排序--利用递归归并 
void merge(int arr[],int arr_copy[],int left,int middle,int right); 
void copy(int arr[],int arr_copy[],int left,int right); 
void mergeSort(int arr[],int left,int right) 
{ 
	int arr_copy[MAXSIZE]; 
	if(leftmiddle) 
	{ 
		for(int begin=m;begin<=right;begin++) 
			arr_copy[nl++]=arr[begin]; 
	} 
	else 
	{ 
		for(int begin=l;begin<=middle;begin++) 
			arr_copy[nl++]=arr[begin]; 
	} 
} 
void copy(int arr[],int arr_copy[],int left,int right) 
{ 
	if(left>right) return; 
	for(int begin=left;begin<=right;begin++) 
	{ 
		arr[begin]=arr_copy[begin]; 
	} 
} 
 
//消除递归归并 
//合并排序好的相邻数组段 
void mergePass(int arr[],int arr_copy[],int size,int len) 
{ 
	int l = 0;	 
	while(l<=size-2*len) 
	{ 
		merge(arr,arr_copy,l,l+len-1,l+2*len-1); 
		l+=2*len; 
	} 
	if(l+lenleft&&arr[right_Ptr]>=temp) right_Ptr--; 
		if(left_Ptr>=right_Ptr) break; 
		swap(arr,left_Ptr,right_Ptr); 
	} 
	arr[left]=arr[right_Ptr]; 
	arr[right_Ptr]=temp; 
	return right_Ptr; 
} 
//基数排序 
typedef struct 
{ 
	short keys[MAX_NUM_OF_KEY]; 
	int next; 
}SLCell; 
typedef struct 
{ 
	SLCell r[MAXSIZE]; 
	int keynum; 
	int recnum; 
}SLList; 
typedef int ArrType[RADIX]; 
void Distribute(SLCell r[],int index,ArrType &first,ArrType &end) 
{ 
	for(int j = 0;j < RADIX; ++j) first[j]=0; 
	for(int p=r[0].next; p != 0; p=r[p].next) 
	{ 
		j = r[p].keys[index]; 
		if(first[j] == 0) first[j] = p; 
		else r[end[j]].next = p; 
		end[j] = p; 
	} 
} 
void Collect(SLCell r[],int index,ArrType &first,ArrType &end) 
{ 
	int t=0; 
	int j=0; 
	do{ 
		for(;j= 0; j--) 
		{ 
			num =num*10+L.r[p].keys[j]; 
		} 
		arr[i] = num; 
		p = L.r[p].next; 
	} 
} 
void RadixSort(int arr[],int size) 
{ 
	SLList L; 
	ArrType first,end; 
	create_SLList(L,arr,size); 
	for(int i = 0;i >size; 
	int i = 0; 
	int temp; 
	for(i=0;i>index; 
		}while(index<0||index>9); 
		int arr_out[MAXSIZE]; 
		for(i=0;i