all_sort.cpp

用C++实现各种排序算法：如冒泡排序、选择排序、插入排序、希尔排序、快速排序、归并排序、基数排序和堆排序

#include<iostream.h>
#include<stdlib.h>
#include<time.h>
#include<malloc.h>
#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(index<size/2)
	{
		int leftChild = 2*index+1;
		int rightChild = leftChild+1;
		if(rightChild<size&&he->heap_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;in<out;in++)
		{

			if(arr[in]>arr[in+1])
				swap(arr,in,in+1);
		}
	}
}
//选择排序
void selectionSort(int arr[],int size)
{
	int in,out,max;
	for(out=0;out<size-1;out++)
	{
		max=out;
		for(in=out;in<size;in++)
			if(arr[max]>arr[in])
				max=in;
		swap(arr,out,max);
	}
}
//插入排序
void insertSort(int arr[],int size)
{
	int in,out;
	for(out=1;out<size;out++)
	{
		in=out;
		int temp=arr[out];
		while(in>0&&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;out<size;out++)
		{
			temp = arr[out];
			in = out;
			while(in>h-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(left<right)
	{
		int middle=(left+right)/2;
		mergeSort(arr,left,middle);
		mergeSort(arr,middle+1,right);
		merge(arr,arr_copy,left,middle,right);
		copy(arr,arr_copy,left,right);
	}
}
void merge(int arr[],int arr_copy[],int left,int middle,int right)
{
	int l=left,m=middle+1,nl=left;//left,middle,newleft
	while((l<=middle)&&(m<=right))
	{
		if(arr[l]<arr[m])
			arr_copy[nl++]=arr[l++];
		else
			arr_copy[nl++]=arr[m++];
	}
	if(l>middle)
	{
		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+len<size)
	{
		merge(arr,arr_copy,l,l+len-1,size-1);
	}
	else
	{
		for(int ll=l;ll<size;ll++)
			arr_copy[ll]=arr[ll];
	}
}
void mergeSort(int arr[],int size)
{
	int arr_copy[MAXSIZE];
	int len =1;//元素个数
	while(len<size)
	{
		mergePass(arr,arr_copy,size,len);
		len+=len;
		mergePass(arr_copy,arr,size,len);
		len+=len;
	}
}
//自然归并排序
void mergePass(int arr[],int arr_copy[],int arr_break[],int size,int break_len,int len)
{
	int l = 0;	
	while(l<=break_len-1-2*len)
	{
		merge(arr,arr_copy,arr_break[l],arr_break[l+len]-1,arr_break[l+2*len]-1);
		l+=2*len;
	}
	if(l+len<break_len-1)
	{
		merge(arr,arr_copy,arr_break[l],arr_break[l+len]-1,arr_break[break_len-1]-1);
	}
	else
	{
		for(int ll=arr_break[l];ll<size;ll++)
			arr_copy[ll]=arr[ll];
	}
}
void mergeSort_NA(int arr[],int size)
{
	int arr_copy[MAXSIZE],arr_break[MAXSIZE];
	int len = 1,break_len=0;
	if(size<1)return;
	int temp = arr[0];
	arr_break[break_len++] = 0;//开始为0
	for(int i=0;i<size;i++)
	{
		if(arr[i]<temp)
		{
			arr_break[break_len++]= i;
		}
		temp = arr[i];
	}
	arr_break[break_len++] = size;//结束为最后一个
	while(len<break_len)
	{
		mergePass(arr,arr_copy,arr_break,size,break_len,len);
		len+=len;
		mergePass(arr_copy,arr,arr_break,size,break_len,len);
		len+=len;
	}
}
//快速排序
int partition(int arr[],int left,int right);
void recQuickSort(int arr[],int left,int right)
{
	if(right-left<=0)		//个数为一或没有元素
		return;
	else
	{
		int part = partition(arr,left,right);
		recQuickSort(arr,left,part-1);
		recQuickSort(arr,part+1,right);
	}
}

int partition(int arr[],int left,int right)
{
	int left_Ptr=left+1;		//将最左端空出，存放枢纽记录的大小
	int right_Ptr=right;
	int temp = arr[left]; 
	while(true)
	{
		while(left_Ptr<right&&arr[left_Ptr]<temp) left_Ptr++;
		while(right_Ptr>left&&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<RADIX-1&&first[j]==0;j++);
		if(first[j]!=0)
		{
			r[t].next = first[j];
			t = end[j];
		}
		j++;
	}while(j<RADIX);
	r[t].next = 0;
}

void create_SLList(SLList &L,int arr[],int size)
{
	L = *(SLList *)malloc(sizeof(SLList)); 
	int keynum = 1;
	int maxnum = MAX;
	while(maxnum/10!=0)
	{
		keynum++;
		maxnum = maxnum/10;
	}
	L.keynum = keynum;
	L.recnum = size;
	for(int i = 1;i <=size;i++)
	{
		int num = arr[i-1];			//带头结点，r[0]为头结点
		for(int j=0;j < keynum;j++)
		{
			L.r[i].keys[j] = num%10;
			num = num/10;
		}
	}
	for(i = 0;i < L.recnum; i++)
	{
		L.r[i].next = i+1;
	}
	L.r[L.recnum].next = 0;
}
void sortToarr(SLList L,int arr[],int size)
{
	int p = L.r[0].next;
	for(int i = 0; i < size; i++)
	{
		int num = 0;
		for(int j = L.keynum-1; 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 <L.keynum;++i)
	{
		Distribute(L.r,i,first,end);
		Collect(L.r,i,first,end);
	}
	sortToarr(L,arr,size);
}

void AllSort(int arr_in[],int size)
{
	int i=0;
	int arr_out[MAXSIZE];
	for(int index=1;index<9;index++)
	{
		for(i=0;i<size;i++)
		{
			arr_out[i]=arr_in[i];
		}
		//time
		long time_begin = clock();
		long time_end = clock();
		long time =0;
		switch(index)
		{
		case 1:
			cout<<"*******************冒泡排序*******************"<<endl;
			bubbleSort(arr_out,size);
			break;
		case 2:
			cout<<"*******************选择排序*******************"<<endl;
			selectionSort(arr_out,size);
			break;
		case 3:
			cout<<"*******************插入排序*******************"<<endl;
			insertSort(arr_out,size);
			break;
		case 4:
			cout<<"*******************希尔排序*******************"<<endl;
			shellSort(arr_out,size);
			break;
		case 5:
			cout<<"*******************快速排序*******************"<<endl;
			recQuickSort(arr_out,0,size-1);
			break;
		case 6:
			cout<<"*******************归并排序*******************"<<endl;
			mergeSort(arr_out,size);
			break;
		case 7:
			cout<<"*******************基数排序*******************"<<endl;
			RadixSort(arr_out,size);
			break;
		case 8:
			cout<<"*******************堆排序*******************"<<endl;
			heapSort(arr_out,size);
			break;
		case 9:
			cout<<"*******************退出!*******************"<<endl;
			break;
		}
		if(index==9) break;
		for(i=0;i<size;i++)
		{
			if(i%10==0) cout<<endl;
			cout<<arr_out[i]<<" ";
		}
		time_end = clock();
		time = time_end-time_begin;
		cout<<"time is :"<<time<<endl;
	}
	for(i=0;i<size;i++)
	{
		arr_in[size-1-i] = arr_out[i];
	}
}

void main()
{
	int arr_in[MAXSIZE];
	int size = 0;
	cout<<"输入数组大小：";
	cin>>size;
	int i = 0;
	int temp;
	for(i=0;i<size;i++)
	{
		if(i%10==0) cout<<endl;
		temp = rand()%MAX+1;
		arr_in[i]=temp;
		cout<<temp<<" ";
	}
	cout<<endl;
	cout<<"***************************************"<<endl;
	//AllSort(arr_in,size);//无序
	//for(i=0;i<size;i++)
		//cout<<arr_in[i]<<" ";
	//AllSort(arr_in,size);//有序

	while(true)
	{
		int index=0;
		cout<<endl<<"请输入排序代号（0~8）："<<endl;
		cout<<"		1:冒泡排序;";
		cout<<"2:选择排序;";
		cout<<"3:插入排序;";
		cout<<"4:希尔排序;";
		cout<<"5:快速排序;"<<endl;
		cout<<"		6:归并排序;";
		cout<<"7:基数排序;";
		cout<<"8:堆排序;";
		cout<<"9:自然归并排序;";
		cout<<"0:退出程序;"<<endl;
		do{
			if(index!=0)
				cout<<"输入不正确，请正确输入代号为（0~8）!";
			cin>>index;
		}while(index<0||index>9);
		int arr_out[MAXSIZE];
		for(i=0;i<size;i++)
		{
			arr_out[i]=arr_in[i];
		}
		//time
		long time_begin = clock();
		long time_end = clock();
		long time =0;
		switch(index)
		{
		case 0:
			cout<<"退出!"<<endl;
			break;
		case 1:
			cout<<"*******************冒泡排序*******************"<<endl;
			bubbleSort(arr_out,size);
			break;
		case 2:
			cout<<"*******************选择排序*******************"<<endl;
			selectionSort(arr_out,size);
			break;
		case 3:
			cout<<"*******************插入排序*******************"<<endl;
			insertSort(arr_out,size);
			break;
		case 4:
			cout<<"*******************希尔排序*******************"<<endl;
			shellSort(arr_out,size);
			break;
		case 5:
			cout<<"*******************快速排序*******************"<<endl;
			recQuickSort(arr_out,0,size-1);
			break;
		case 6:
			cout<<"*******************归并排序*******************"<<endl;
			mergeSort(arr_out,size);
			break;
		case 7:
			cout<<"*******************基数排序*******************"<<endl;
			RadixSort(arr_out,size);
			break;
		case 8:
			cout<<"*******************堆排序*******************"<<endl;
			heapSort(arr_out,size);
			break;
		case 9:
			cout<<"*******************自然归并排序*******************"<<endl;
			mergeSort_NA(arr_out,size);
			break;
		}
		if(index==0) break;
		time_end = clock();
		time = time_end-time_begin;
		for(i=0;i<size;i++)
		{
			if(i%10==0) cout<<endl;
			cout<<arr_out[i]<<" ";
		}
		cout<<endl<<"index:"<<index<<"  time is :"<<time<<endl;
	}
}