读数据结构与算法分析
插入排序
核心：利用的是从位置0到位置P都是已排序的
所以从位置1开始排序，如果当前位置不对，则和前面元素反复交换重新排序
实现
void InsertionSort(ElementType A[], int N)
{
int i,P;
ElementType Tmp ;
for(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 ;
}
}
希尔排序
使用hk增量序列进行一趟排序后，对每个i都有
A[i] \leq A[i+hk]
重要性质：一个hk排序的文件在之后的排序中将保持hk排序性
实现
- ht = [N / 2]
- hk = [hk+1 / 2]
void ShellSort(ElmentType A[], int N)
{
ElementType Tmp ;
int i,j,Increment ;
for(Increment = N/2;Increment > 0;Increment /= 2)
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 ;
}
}
堆排序
基于原有的二叉堆
建立二叉堆，执行DeleteMax操作，储存至数组（节省空间可以倒序储存在当前数组）
实现
#define LeftChild(i) (2 * i + 1) ;
void Percdown(ElementType A[],int i,int N)
{
int Child ,i;
ElementType Tmp ;
for(Tmp = A[i]; LeftChild(i) < N-1;i = Child)
{
Child = LeftChild(i) ;
if(Tmp < A[Child])
A[i] = A[Chile] ;
else
break ;
}
A[i] = Tmp ;
}
void HeapSore(ElementType A[],int N)
{
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) ;
}
}
归并排序
基本思想是合并两个已排序的表
实现
递归合并
void Msort(ElementType A[],ElementeType TmpArray[],int Left,int Right)
{
int Center ;
if(Left < Right)
{
Center = (Left + Right) /2 ;
Msort(A,TmpArray,Left,Right) ;
Msort(A,TmpArray,Center + 1,Right) ;
Merge(A,TmpArray,Left,Center + 1,Right) ;
}
}
驱动程序
void Mergesort(ElementType A[],int N)
{
ElementType *TmpArray ;
TmpArray = malloc(N * sizeof(ElementType)) ;
if(TmpArray != NULL)
{
Msort(A,TmpArray,0,N-1) ;
free(TmpArray) ;
}
else
FatalError("内存不足") ；
}
合并函数
void Merge(ElementType A[],ElementType TmpArray[],int Lpos,int Rpos,int RightEnd)
{
int i,LeftEnd,NumElements,TmpPos ;
LeftEnd = Rpos - 1;
TmpPos = Lpos ;
NumElement = 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 < NumElement ;i++,RightEnd--)
A[RightEnd] = TmpArray[RightEnd] ;
}
快速排序
和归并排序一样都是分治递归算法,在小数组上效率并没有插入排序好
- 如果S中元素个数是0或1，则返回
- 取S中任一元素v,称为枢纽元
- 将S剩余的其它元素，分为两个不相交的集合
- 返回quicksort(S1),继续选择v,继续quicksort(S2) ;
实现
选取枢纽元
三数中值分割方法
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] ;
}
主函数
#define Cutoff(3) ;
void Qsort(ElementType A[],int Left,int Right)
{
int i,j ;
ElementType Pivot ;
if(Left + Cutoff <= Right)
{
Pivot = Midian3(A,Left,Right)
i = Left ; j = Right ;
for(;;)
{
While(A[++i] < Privot){}
While(A[--j] > Privot){}
if(i < j)
Swap(&A[i],&A[j]) ;
else
break ;
}
Swap(&A[i],&A[Right-1]) ;
Qsort(A,Left,i-1) ;
Qsort(A,i+1,Right) ;
}
else
InsertionSort(A + Left,Right - Left + 1) ;
}
驱动函数
void QuickSort(ElementType A[],int N)
{
Qsort(A,0,N-1) ;
}
总结
- 对于一般的内部排序，选用的方法一般是插入排序、希尔排序和快速排序，根据输入来选择
- 高度优化的快速排序在对于很少的输入也可能和希尔排序一样快
对于快速排序，选取枢纽元十分关键
- 堆排序比希尔排序要满
- 插入排序一般用于较小的或接近排好序的输入
- 归并排序在主存排序中不如快速排序那么好，但是合并时外部排序的中心思想