各种排序方法汇总

#include<stdio.h>
#include<stdlib.h>
typedef int ElementType;
void Swap(int &a,int &b) {int n;n=a,a=b,b=n;}
//--简单排序-- 
//冒泡排序
void  Bubble_Sort(ElementType A[],int N)
{int flag;for(int P=N-1;P>=0;P--){flag=0;for(int i=0;i<P;i++)if(A[i]>A[i+1]){Swap(A[i],A[i+1]);flag=1;}if(!flag) break;}
}
//插入排序
void Insertion_Sort(ElementType A[],int N)
{int i,tmp;for(int P=1;P<N;P++){tmp=A[P];for(i=P;i>0 && A[i-1]>tmp;i--)A[i]=A[i-1];A[i]=tmp;}}
//希尔排序(插入排序的改进)//
void Shell_Sort(ElementType A[],int N)
{int i,tmp,D;for(D=N/2;D>0;D/=2)  //希尔增量序列 {for(int P=D;P<N;P++){tmp=A[P];for(i=P;i>=D && A[i-D]>tmp;i-=D)A[i]=A[i-D];A[i]=tmp;}}
}
//堆排序
void Selection_Sort(ElementType A[],int N)
{int i,MinPosition;for(i=0;i<N;i++){MinPosition = ScanForMin(A,i,N-1);/*从A[i]到A[N-1]找到最小元;用最小堆*/ if(MinPosition!=i)Swap(A[i],A[MinPosition]);}
} 
void Heap_Sort(ElementType A[],int N) /*应用效果可能不如 	 */ 
{									/*	 Sedgewick的希尔序列*/ int i;
/*	ElementType TmpA[N];Create(H);BuildMinHeap(H);for(i=0;i<N;i++)TmpA[i]=DeleteMin(H);for(i=0;i<N;i++)A[i]=TmpA[i]; */for(i=N/2;i>=0;i--) //BuildMinHeapPercDown(A,i,N);for(i=N-1;i>0;i--){Swap(A[0],A[i]); //DeleteMaxPercDown(A,0,i);}
}
//归并排序/ // / 
/*核心:有序子列的归并;*/
void Merge(ElementType A[],ElementType TmpA[],int L,int R,int RightEnd)
{int LeftEnd,Tmp,NumElements;LeftEnd = R-1;Tmp = L;NumElements = RightEnd - L + 1;while(L<=LeftEnd && R<=RightEnd){if(A[L] <= A[R]) TmpA[Tmp++]=A[L++];else             TmpA[Tmp++]=A[R++];}while(L<=LeftEnd)  TmpA[Tmp++]=A[L++];while(R<=RightEnd) TmpA[Tmp++]=A[R++];for(int i = 0;i < NumElements ; i++, RightEnd--)A[RightEnd]=TmpA[RightEnd];
}//递归算法，分割成小块 //
void MSort(ElementType A[],ElementType TmpA[],int L,int RightEnd)
{int Center;if(L < RightEnd){Center=(L + RightEnd) / 2;MSort(A,TmpA,L,Center);MSort(A,TmpA,Center+1,RightEnd);Merge(A,TmpA,L,Center+1,RightEnd);}
}void Merge_Sort(ElementType A[],int N) 
{ElementType *TmpA;TmpA = (ElementType *)malloc(N*sizeof(ElementType));if(TmpA!=NULL){MSort(A,TmpA,0,N-1);free(TmpA);}else Error("空间不足"); 
}//非递归算法
void Merge_pass(ElementType A[],ElementType TmpA[],int N,int length) //length = 当前有序子列长度
{int i;for(i=0;i <= N-2*length;i+=2*length)Merge1(A,TmpA,i,i+length,N-1);if(i+length<N)Merge1(A,TmpA,i,i+length,N-1);elsefor(int j = 1;j<N;j++) TmpA[j] = A[j]; 
}void Merge_Sort(ElementType A[],int N) 
{int length = 1;ElementType *TmpA;TmpA = (ElementType*)malloc(N*sizeof(ElementType));if(TmpA!=NULL ){while(length < N){Merge_pass(A,TmpA,N,length);length*=2;Merge_pass(TmpA,A,N,length);length*=2;}free(TmpA);}else Error("空间不足"); 
}void Merge1(ElementType A[],ElementType TmpA[],int L,int R,int RightEnd)
{int LeftEnd,Tmp,NumElements;LeftEnd = R-1;Tmp = L;NumElements = RightEnd - L + 1;while(L<=LeftEnd && R<=RightEnd){if(A[L] <= A[R]) TmpA[Tmp++]=A[L++];else             TmpA[Tmp++]=A[R++];}while(L<=LeftEnd) TmpA[Tmp++]=A[L++];while(R<=RightEnd) TmpA[Tmp++]=A[R++];
//	for(int i = 0;i < NumElements ; i++, RightEnd--)
//	A[RightEnd]=TmpA[RightEnd];
}快速排序
//核心：选主元 (头，尾，中，三者选中间大小的数字) 
ElementType Median3(ElementType A[],int Left,int Right)
{int Center = (Left + Right) / 2;if(A[Left] > A[Center])Swap(A[Left] , A[Center]);if(A[Left] > A[Right])Swap(A[Left] , A[Right]);if(A[Center] > A[Right])Swap(A[Center] , A[Right]);Swap(A[Center] , A[Right-1]);return A[Right-1];
} 
/*Left保存最小值，Right保存最大值，Right-1保存中值，只需要考虑（left+1，Right-2）的排序就好*/ 
void Quicksort(ElementType A[], int Left, int Right)
{int i,j,Pivot;if(Cutoff <= Right-Left)  //当排序的数小于Cutoff就用插入排序，因为数量小的时候，快排还不如插入排序; {Pivot = Median3(A,Left,Right);i = Left; j = Right - 1;for(;;){while(A[++i] < Pivot);while(A[--j] > Pivot);if(i<j) Swap(A[i],A[j]);else break;}Swap(A[i],A[Right-1]);Quicksort(A,Left,i-1);Quicksort(A,i+1,Right);}else Insertion_Sort(A+Left,Right-Left+1);	} void Quick_Sort(ElementType A[],int N)
{Quicksort(A,0,N-1);
}