排序

插入排序

核心:利用的是从位置0到位置P都是已排序的

所以从位置1开始排序,如果当前位置不对,则和前面元素反复交换重新排序

实现

1
2
3
4
5
6
7
8
9
10
11
12
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都有

1
A[i] \leq A[i+hk]

重要性质:一个hk排序的文件在之后的排序中将保持hk排序性

实现

  • ht = [N / 2]
  • hk = [hk+1 / 2]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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操作,储存至数组(节省空间可以倒序储存在当前数组)

实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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) ;
}

}

归并排序

基本思想是合并两个已排序的表

实现

递归合并

1
2
3
4
5
6
7
8
9
10
11
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) ;
}
}

驱动程序

1
2
3
4
5
6
7
8
9
10
11
12
13
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("内存不足") ;
}

合并函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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] ;
}

快速排序

和归并排序一样都是分治递归算法,在小数组上效率并没有插入排序好

  1. 如果S中元素个数是0或1,则返回
  2. 取S中任一元素v,称为枢纽元
  3. 将S剩余的其它元素,分为两个不相交的集合
  4. 返回quicksort(S1),继续选择v,继续quicksort(S2) ;

实现

选取枢纽元

三数中值分割方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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] ;

}

主函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#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) ;
}

驱动函数

1
2
3
4
void QuickSort(ElementType A[],int N)
{
Qsort(A,0,N-1) ;
}

总结

  • 对于一般的内部排序,选用的方法一般是插入排序、希尔排序和快速排序,根据输入来选择
  • 高度优化的快速排序在对于很少的输入也可能和希尔排序一样快

    对于快速排序,选取枢纽元十分关键

  • 堆排序比希尔排序要满
  • 插入排序一般用于较小的或接近排好序的输入
  • 归并排序在主存排序中不如快速排序那么好,但是合并时外部排序的中心思想