算法分析-数组6种排序(少桶排序)

参考书目《数据结构与算法分析(C语言描述)》 快速排序参考实验楼快速排序

//排序函数接口

#ifndef _ALLSORT_H#define _ALLSORT_Hvoid BubbleSort(int A[],int N);void InsertSort(int A[],int N);void ShellSort(int A[],int N);void HeapSort(int A[],int N);void MergeSort(int A[],int N);void QuickSort(int A[],int L,int R);void PRintArray(int A[],int N);#endif
//排序函数定义
#include <stdio.h>#include <stdlib.h>#define LeftChild(i)   (2*(i)+1)static void Swap(int *x,int *y);  //隐藏函数 文件作用域static void PercDown(int A[],int i,int N);static void MSort(int A[],int TmpArray[],int Left,int Right);static void Merge(int A[],int TmpArray[],int Lpos,int Rpos,int RightEnd);static int Qsort(int A[],int Left,int Right);void BubbleSort(int A[],int N) //sort 0{	int i,j;	for(i=0;i<N;i++)	{		for(j=0;j<N-i-1;j++)		{			if(A[j]>A[j+1]) //交换位置			{				Swap(&A[j],&A[j+1]);			}		}	}}void InsertSort(int A[],int N)  //sort 1{	int j,P;	int tmp;	for(P=1;P<N;P++)	{		tmp=A[P];		for(j=P;j>0&&A[j-1]>tmp;j--)  //找到合适的插入位置			A[j]=A[j-1];		A[j]=tmp; //将其插入到对应的位置当中	}}void ShellSort(int A[],int N)  //sort 2{	int i,j,Increment;	int tmp;	for(Increment=N/2;Increment>0;Increment/=2)  //希尔增量 插入排序 最后一次插入必须是增量为1		for(i=Increment;i<N;i++)		{			tmp=A[i];			for(j=i;j>=Increment;j-=Increment)			{				if(tmp<A[j-Increment])					A[j]=A[j-Increment];				else					break;			}			A[j]=tmp;		}}void HeapSort(int A[],int N)   //sort 3{	int i;	for(i=N/2;i>=0;i--)  //建立大顶堆		PercDown(A,i,N);	for(i=N-1;i>0;i--) //取出堆顶元素 然后倒序放入数组	{		Swap(&A[0],&A[i]);		PercDown(A,0,i);	}}static void Swap(int *x,int *y){	*x^=*y;  //异或来交换元素	*y^=*x;	*x^=*y;}static void PercDown(int A[],int i,int N)  //下滤{	int Child;	int tmp;	for(tmp=A[i];LeftChild(i)<N;i=Child)	{		Child=LeftChild(i);		if(Child!=N-1&&A[Child+1]>A[Child])			Child++;		if(tmp<A[Child])			A[i]=A[Child];		else			break;	}	A[i]=tmp;}void MergeSort(int A[],int N)  //sort 4{	int *TmpArray;	TmpArray=(int *)malloc(sizeof(int)*N); //动态申请内存 储存第三个数组	if(TmpArray!=NULL)	{		MSort(A,TmpArray,0,N-1);		free(TmpArray);	}	else		printf("No space for tmp array!!");}static void MSort(int A[],int TmpArray[],int Left,int Right){	int Center;	if(Left<Right)	{		Center=(Left+Right)/2;		MSort(A,TmpArray,Left,Center);		MSort(A,TmpArray,Center+1,Right);		Merge(A,TmpArray,Left,Center+1,Right);  //将要储存的位置传入动态数组当中	}}static void Merge(int A[],int TmpArray[],int Lpos,int Rpos,int RightEnd){	int i,LeftEnd,Num,TmpPos;	LeftEnd=Rpos-1;	TmpPos=Lpos;	Num=RightEnd-Lpos+1;	while(Lpos<=LeftEnd&&Rpos<=RightEnd)  //将有序数组合并在一起	{		if(A[Lpos]<=A[Rpos])			TmpArray[TmpPos++]=A[Lpos++];		else			TmpArray[TmpPos++]=A[Rpos++];	}	while(Lpos<=LeftEnd)  //将剩余部分的数组复制到该数组后面部分		TmpArray[TmpPos++]=A[Lpos++];	while(Rpos<=RightEnd)		TmpArray[TmpPos++]=A[Rpos++];	for(i=0;i<Num;i++,RightEnd--)		A[RightEnd]=TmpArray[RightEnd];}void QuickSort(int A[], int low, int high) //sort 5 {    if (low < high)    {        int pivotloc = Qsort(A, low, high);        QuickSort(A, low, pivotloc - 1); //分割数组        QuickSort(A, pivotloc + 1, high);    }}static int Qsort(int A[],int Left,int Right){	int temp;    int pivotkey = A[Left]; //选取数组首元素作为主元     temp = pivotkey;    while (Left < Right)    {        while (Left < Right && A[Right] >= pivotkey)        {            Right--;        }        A[Left] = A[Right];        while (Left < Right && A[Left] <= pivotkey)        {            Left++;        }        A[Right] = A[Left];    }    A[Left] = temp;    return Left;}void PrintArray(int A[],int N) //打印数组{	int i;	for(i=0;i<N;i++)	{		if(i%20==0)			printf("/n");		printf("%3d",A[i]);	}}
//main函数入口
#include <stdio.h>#include "allsort.h"int main(int argc, char **argv){int random0[15]={24,15,12,62,35,43,34,73,7,34,77,43,89,54,76};int random1[15]={24,15,12,62,35,43,34,73,7,34,77,43,89,54,76};int random2[15]={24,15,12,62,35,43,34,73,7,34,77,43,89,54,76};int random3[15]={24,15,12,62,35,43,34,73,7,34,77,43,89,54,76};int random4[15]={24,15,12,62,35,43,34,73,7,34,77,43,89,54,76};int random5[15]={24,15,12,62,35,43,34,73,7,34,77,43,89,54,76};BubbleSort(random0,15);InsertSort(random1,15);ShellSort(random2,15);HeapSort(random3,15);MergeSort(random4,15);QuickSort(random5,0,14); //这里从0开始到14结束printf("Bubblesort:");PrintArray(random0,15);printf("/nInsertSort:");PrintArray(random1,15);printf("/nShellSort:");PrintArray(random2,15);printf("/nHeapSort:");PrintArray(random3,15);printf("/nMergeSort:");PrintArray(random4,15);printf("/nQuickSort:");PrintArray(random5,15);return 0;}
测试结果：