8中常见的排序算法

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

//冒泡排序
void boblesort(int * arr,int n);
//插入排序
void insertsort2(int *arr,int n);
//希尔排序
void shellsort2(int *arr,int n);
//选择排序
void selectsort(int *arr,int n);
//归并排序
void mergesort(int *arr,int n);
//快速排序
void quicksort(int *arr,int n);
//桶次排序
void bucketsort(int * arr,int n);
//堆排序
void minheapsort(int *arr,int n);

/*打印数组中的元素*/
void printarray(int *arr,int n){
	for(int i=0;i<n;++i)
		printf("%d ",arr[i]);
	printf("\n");
}

///////////////////////////////////////////////////////////////////////////////////////////////////
//冒泡排序，每一次比较将较大的数值放在后面，这样进行一轮比较后最大的数就在最后面了
//然后下一轮比较时只比较到上一轮排好序的那个数
void boblesort(int * arr,int n){
	int i,j;
	//这里i是从1开始，一直到小于n，比如有10个数，外层只需要进行9轮比较即可
	//因为每一轮会将最大的数移到后面，当只有一个数时，就不需要移动了
	for(i=1;i<n;++i){
		//这里的j从0开始，最大要小于n-i，不能到达n-i，因为下面会引用到arr[j+1]，如果到达了
		//n-i,会产生溢出，需要注意这里i和j的取值范围
		for(j=0;j<n-i;j++)
		{
			if(arr[j]>arr[j+1])
			{
				int tmp=arr[j];
				arr[j]=arr[j+1];
				arr[j+1]=tmp;
			}
		}
	}
}
///////////////////////////////////////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////////////////////////////////////
//插入排序，设数组为a[0…n-1]。
//1.      初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1
//2.      将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。
//3.      i++并重复第二步直到i==n-1。排序完成。
void insertsort1(int *arr,int n){
	int i,j,k;
	//外层循环，需要做n-1轮循环，即从下标为1的元素开始比较起
	for(i=1;i<n;++i){
		for(j=0;j<i;++j){
			//如果找到比arr[i]大的元素，那么需要将其后面的元素后移
			if(arr[j]>arr[i]){
				int tmp=arr[i];
				for(k=i;k>j;k--){
					arr[k]=arr[k-1];
				}
				arr[j]=tmp;
			}
		}
	}
}

//将搜索和数据后移这两步合并
void insertsort2(int *arr,int n){
	int i,j;
	for(i=1;i<n;i++){
		if(arr[i]<arr[i-1]){
			int tmp=arr[i];
			//将arr[i]和数组中的元素倒过来进行比较久可以比较的同时进行后移操作
			for(j=i-1;j>=0&&arr[j]>tmp;j--){
				arr[j+1]=arr[j];
			}
			arr[j+1]=tmp;//这儿需要对arr[j+1]而不是对arr[j]赋值，因为上面循环的退出条件是arr[j]<tmp，此时arr[j+1]的值没有被存储。
		}
	}
}
///////////////////////////////////////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////////////////////////////////////
/*希尔排序：该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。*/
void shellsort1(int *arr,int n){
	int gap,i,j,k;
	for(gap=n/2;gap>0;gap=gap/2){//步长
		for(i=0;i<gap;i++){//按组排序，每组都需要进行插入排序
			//下面实际上是一个插入排序
			for(j=i+gap;j<n;j+=gap){
				if(arr[j]<arr[j-gap]){
					int tmp=arr[j];
					for(k=j-gap;k>=0&&arr[k]>tmp;k-=gap){
						arr[k+gap]=arr[k];
					}
					arr[k+gap]=tmp;
				}
			}
		}
	}
	
	
}

void shellsort2(int *arr,int n){
	int gap,i,j;
	for(gap=n/2;gap>0;gap/=2){
		//将按组排序合并到一步进行比较，即一次遍历即比较完几组的数据
		for(i=gap;i<n;i++){
			if(arr[i]<arr[i-gap]){
				int tmp=arr[i];
				for(j=i-gap;j>=0&&arr[j]>tmp;j-=gap){
					arr[j+gap]=arr[j];
				}
				arr[j+gap]=tmp;
			}	
		}
	}
}
///////////////////////////////////////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////////////////////////////////////
/*选择排序：设数组为a[0…n-1]。
1.      初始时，数组全为无序区为a[0..n-1]。令i=0
2.      在无序区a[i…n-1]中选取一个最小的元素，将其与a[i]交换。交换之后a[0…i]就形成了一个有序区。
3.      i++并重复第二步直到i==n-1。排序完成。*/
void selectsort(int *arr,int n){
	int i,j;
	for(i=0;i<n;++i){
		int mindex=i;
		for(j=i+1;j<n;j++){
			if(arr[j]<arr[mindex])
				mindex=j;
		}
		int tmp=arr[mindex];
		arr[mindex]=arr[i];
		arr[i]=tmp;
	}
}
///////////////////////////////////////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////////////////////////////////////
/**归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
首先考虑下如何将将二个有序数列合并。这个非常简单，只要从比较二个数列的第一个数，谁小就先取谁，取了后就在对应数列中删除这个数。然后再进行比较，如果有数列为空，那直接将另一个数列的数据依次取出即可。
归并排序，其的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？
可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了.
这样通过先递归的分解数列，再合并数列就完成了归并排序*/

//合并操作，假设数组arr中firt到mid是有序的，mid+1到last是有序的，下面通过一个中间数组将arr变的有序
void merge(int *arr,int first,int mid,int last){
	int m,n;
	m=first;
	n=mid+1;
	int k=0;
	int * tmp=new int[last-first+1];
	while(m<=mid&&n<=last){
		if(arr[m]<arr[n])
		{
			tmp[k++]=arr[m++];
		}else{
			tmp[k++]=arr[n++];
		}
	}
	while(m<=mid)
		tmp[k++]=arr[m++];
	while(n<=last)
		tmp[k++]=arr[n++];
	for(int j=0;j<k;++j){
		arr[first+j]=tmp[j];
	}
	delete []tmp;
}

//分解操作，将数组不断分解成两个部分，直到只剩下一个元素，就是递归
void mergechild(int *arr,int first ,int last){

	if(first<last){
		int mid=(first+last)/2;
		mergechild(arr,first,mid);
		mergechild(arr,mid+1,last);
		merge(arr,first,mid,last);		
	}
}

void mergesort(int *arr,int n){
	mergechild(arr,0,n-1);
}
///////////////////////////////////////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////////////////////////////////////
/*快速排序，一次遍历只查询一个元素，1论结果如何，进行下一次遍历，效率比较低
 * */
void quicksort1(int * array,int first,int last){
	if(first>=last)
		return;
	int *p1;
	p1=array;
	int m=first,n=last;
	int data=array[m];
	bool move=true;//还需要用一个变量来判断是从左边还是从右边还是遍历，默认从右边往左边遍历
	while(m<n){
		if(move){
			if(data<p1[n]){
				--n;
			}
			else if(data>p1[n])
			{
				p1[m]=p1[n];
				++m;
				move=false;
			}
			}
		else{
	       		 if(data<p1[m]){
				p1[n]=p1[m];
				--n;
				move=true;
			 }
			else if(data>p1[m]){
				++m;
			}
		}
	}
	array[m]=data;
	quicksort1(array,first,m-1);
	quicksort1(array,m+1,last);
}

/*快速排序2，一次先从右往左直到找到符合要求的值，再从左向右找到要求的值，效率比较高，注意递归跳出的条件
 * */
void quicksort2(int *arr,int first,int last){
	if(first>=last)
		return;
	int m=first,n=last;
	int data=arr[m];
	while(m<n){
		while(m<n&&data<arr[n]) --n;
		if(data>arr[n]){
			arr[m]=arr[n];
			++m;
		}

		while(m<n&&data>arr[m]) ++m;
		if(data<arr[m]){
			arr[n]=arr[m];
			--n;
		}
	}
	arr[m]=data;
	quicksort2(arr,first,m-1);
	quicksort2(arr,m+1,last);//这个地方必须用m+1做边界，不能用m做边界，如果m未发生变化，那么这是个死循环
}

void quicksort(int *arr,int n){
	quicksort2(arr,0,n-1);
}
///////////////////////////////////////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////////////////////////////////////
int getnuminpos(int num,int pos){
	int temp=1;
	for(int i=0;i<pos-1;i++)
		temp*=10;
	return (num/temp)%10;
}

/*基数排序（以整形为例），将整形10进制按每位拆分，然后从低位到高位依次比较各个位。主要分为两个过程：
(1)分配，先从个位开始，根据位值(0-9)分别放到0~9号桶中（比如53,个位为3，则放入3号桶中）
(2)收集，再将放置在0~9号桶中的数据按顺序放到数组中
重复(1)(2)过程，从个位到最高位（比如32位无符号整形最大数4294967296，最高位10位）
 * */
void bucketsort(int * arr,int num){
	int *p[10];
	for(int i=0;i<10;i++){
		p[i]=new int[num+1];
		p[i][0]=0;//index为0处记录这组数据的个数
	}
	for(int pos=1;pos<31;pos++){
		for(int j=0;j<num;j++){
			int num=getnuminpos(arr[j],pos);
			int index = ++p[num][0];
			p[num][index]=arr[j];
		}
		for(int k=0,m=0;k<10;k++){
			for(int n=1;n<=p[k][0];n++)
				arr[m++]=p[k][n];
			p[k][0]=0;
		}
	}
}
///////////////////////////////////////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////////////////////////////////////
void swap(int &a,int &b){
	int c;
	c=a;
	a=b;
	b=c;
}

//最小堆中插入元素后恢复函数,向上恢复
//向上恢复的过程中类似于插入排序中的一轮比较，即前面的数据是有序的，但是需要注意的是这里需要用两个下标变量来保存数据而不能像插入排序中用一个变量来保存数据
void minheapfixup(int* arr,int n){
	int p=n;//下标p指示的是子节点
	int i=(p-1)/2;//下标i指示的是父节点
	int tmp=arr[n];
	while(i>=0&&p!=0){
		if(arr[i]<tmp){
			break;	
		}
		arr[p]=arr[i];
		p=i;
		i=(i-1)/2;
	}
	arr[p]=tmp;
}

//最小堆中插入数据num
void minheapadd(int* arr,int n,int num){
	arr[n]=num;
	minheapfixup(arr,n);
}

//最小堆中删除节点i后的恢复函数，向下恢复,n表示节点数目
void minheapfixdown(int *arr,int i,int n){
	int k=i;
	int j=2*k+1;//要删除节点的左子节点
	int tmp=arr[i];
	//一直向下寻找到最后的节点
	while(j<n){
		if((j+1)<n&&arr[j]>arr[j+1])//如果左子节点比右子节点大，那么需要上升的是右子节点
		{
			j+=1;
		
		}
		if(arr[j]>=tmp) break; //如果某一步子节点的值比tmp小，那么可以停止继续向下寻找了
		arr[k]=arr[j];
	        k=j;
		j=2*j+1;
	}
	arr[k]=tmp;
}

//删除堆中的元素
void minheapdelete(int *arr,int n){
	swap(arr[0],arr[n-1]);
	minheapfixdown(arr,0,n-1);
}

//堆化数组
void makeminheap(int *arr,int n){
	int i;
	for(i=(n-2)/2;i>=0;i--)
		minheapfixdown(arr,i,n);
}

//对堆进行排序
void minheapsort(int *arr,int n){
	makeminheap(arr,n);
	for(int i=n-1;i>=1;--i){
		swap(arr[i],arr[0]);
		minheapfixdown(arr,0,i);
	}
}
///////////////////////////////////////////////////////////////////////////////////////////////////


///////////////////////////////////////////////////////////////////////////////////////////////////
//定义函数指针数组类型，里面的每一个元素是一种指向某种排序函数的指针
typedef void (*SORTFUC[8])(int *arr,int n);

int main(){
	//定义一个函数指针数组类型的变量，里面的每一个元素是一种排序算法
	SORTFUC func={boblesort,insertsort2,shellsort2,selectsort,mergesort,quicksort,bucketsort,minheapsort};
	//定义每种排序算法的说明
	const char * str[8]={"1.冒泡排序","2.插入排序","3.希尔排序","4.选择排序","5.归并排序","6.快速排序","7.桶次排序","8.堆排序"};
	//input用来接收用户输入，maxSize表示数组最大大小，i用来表示动态数组的下标
	int input,maxSize,i=0;
	printf("please input the max array size:");
	scanf("%d",&maxSize);
	int *arr=new int[maxSize];	
	//遇到结束符时停止接收数据，控制台下通过输入Ctrl+Z并输入回车来输入EOF
	while(i<maxSize&&scanf("%d",&input)==1&&input!=EOF){
		arr[i++]=input;
	}
	printf("intput array is:");
	printarray(arr,i);
	printf("choose a kind of sort algorithm(0 to exit):\n");
	for(int j=0;j<8;j++)
	{
		printf("%s\n",str[j]);
	}
	//选择排序算法
	while(scanf("%d",&input)==1&&input!=EOF&&input!=0){	
		if(input>=1&&input<=8){
			//这里通过一个临时动态数组来实现多次排序
			int *tmp=new int[i];
			memcpy(tmp,arr,i*sizeof(int));

			//打印输出
			printf("basic array:");
			printarray(tmp,i);

			//排序
			func[input-1](tmp,i);
			
			//打印输出
			printf("algorithm:%s,sorted array is:",str[input-1]);
			printarray(tmp,i);
			delete tmp;
		}else{
			printf("please choose a number between 1 and 8 !\n");
		}
	}

	delete arr;
	return 0;
}