09-排序1 排序 (堆、归并)

题目全文见此文数据结构与算法刷题笔记8——排序（冒泡、插入、希尔）

堆排序

中心思想

选择排序的优化版，选择排序是顺序扫描整个数组，找到最大值然后放到末尾，堆排序是使用了一个最大堆来存储最大值，然后每次找最大值就使用删除首节点的方法，最终继续使用选择排序完成剩下的排序过程。

实现代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include<stdlib.h>
#include<stdio.h>

void Heap_sort(int Data[],int N);
void PercDown(int *Data,int M,int N);
void swap(int *A,int *B);

int main()
{
    int i,N,*Data;
    scanf("%d\n",&N);
    Data = (int*)malloc(N*sizeof(int));
    for(i = 0;i < N;i++)
        scanf("%d ",&Data[i]);
    Heap_sort(Data,N);
    for(i = 0;i < N-1; i++)
        printf("%d ",Data[i]);
    printf("%d\n",Data[N-1]);
}

void Heap_sort(int *Data,int N)
{   
    int i;
    for(i = N/2;i>=0;i--)
        PercDown(Data,i,N);
    for(i = N-1;i > 0; i--)
    {
        swap(&Data[0],&Data[i]);
        PercDown(Data,0,i);
    }
}
void PercDown(int *Data,int M,int N)
{
    int parent,child,X;
    X = Data[M];
    for(parent = M; parent*2 + 2 <= N; parent = child){
        child = parent*2 + 1;
        if((child != N-1)&&(Data[child] < Data[child+1]))
            child++;
        if(Data[child] <= X) break;
        else
            Data[parent] = Data[child];
    }
    Data[parent] = X;
}
void swap(int *A,int *B)
{
    int tmp;
    tmp = *A;
    *A = *B;
    *B = tmp;
}

测试结果

image-20210811101701248

堆排序是一个复杂度为$O(NlogN)$的排序算法，可以看出来它的排序效率和希尔排序是差不多的，不过堆排序额外开辟了一个数量级为$N$的数组，导致了可排序的数字减少了一半，不过使用空间换时间也是比较常见的策略

归并排序

中心思想

归并排序的想法是开辟一个数组，把我们要排序的数组分成左右两部分，先解决左边的排序问题在解决右边的排序问题。要怎么解决左边的问题呢？再递归调用归并排序的函数，继续分而治之。

递归实现代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<stdlib.h>
#include<stdio.h>

void Merge_sort(int *Data,int N);
void Merge( int Data[], int TmpData[], int L, int R, int RightEnd );
void Msort(int Data[], int TmpData[], int L, int RightEnd);
int main()
{
    int i,N,*Data;
    scanf("%d\n",&N);
    Data = (int*)malloc(N*sizeof(int));
    for(i = 0;i < N;i++)
        scanf("%d ",&Data[i]);
    Merge_sort(Data,N);
    for(i = 0;i < N-1; i++)
        printf("%d ",Data[i]);
    printf("%d\n",Data[N-1]);
}

void Merge_sort(int *Data,int N)
{
    int *TmpData;
    TmpData = (int*)malloc(N * sizeof(int));
    Msort( Data, TmpData, 0, N-1 );
    free( TmpData );
}
void Msort(int Data[], int TmpData[], int L, int RightEnd)
{
    int Center;
    if( L < RightEnd )
    {
        Center = ( L + RightEnd ) / 2;
        Msort( Data, TmpData, L, Center );
        Msort( Data, TmpData, Center+1, RightEnd );
        Merge( Data, TmpData, L, Center+1, RightEnd);
    }
}

/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge( int Data[], int TmpData[], int L, int R, int RightEnd )
{ /* 将有序的Data[L]~Data[R-1]和Data[R]~Data[RightEnd]归并成一个有序序列 */
    int LeftEnd, NumElements, Tmp, i;
    NumElements = RightEnd - L + 1;
    LeftEnd = R-1;
    Tmp = L;
    while(L <= LeftEnd && R <= RightEnd)
    {
        if(Data[L] > Data[R])
            TmpData[Tmp++] = Data[R++];
        else
            TmpData[Tmp++] = Data[L++];
    }
    while( L <= LeftEnd )
        TmpData[Tmp++] = Data[L++];
    while( R <= RightEnd )
        TmpData[Tmp++] = Data[R++];
    for(i = 0; i < NumElements; i++, RightEnd--)
        Data[RightEnd] = TmpData[RightEnd];
}

测试结果

image-20210811112743604

非递归实现代码

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include<stdlib.h>
#include<stdio.h>

void Merge_sort(int *Data,int N);
void Merge( int Data[], int TmpData[], int L, int R, int RightEnd );
void Msort(int Data[], int TmpData[], int N, int length);
int main()
{
    int i,N,*Data;
    scanf("%d\n",&N);
    Data = (int*)malloc(N*sizeof(int));
    for(i = 0;i < N;i++)
        scanf("%d ",&Data[i]);
    Merge_sort(Data,N);
    for(i = 0;i < N-1; i++)
        printf("%d ",Data[i]);
    printf("%d\n",Data[N-1]);
}

void Merge_sort(int *Data,int N)
{
    int *TmpData,length;
    length = 1;
    TmpData = (int*)malloc(N * sizeof(int));
    while(length < N){
        Msort( Data, TmpData, N, length );
        length *= 2;
        Msort( TmpData, Data, N, length );
        length *= 2;
    }
free( TmpData );
}
void Msort(int Data[], int TmpData[], int N, int length)
{
    int i,j;
    for( i = 0;i < N - 2*length; i+=2*length)
        Merge(Data, TmpData, i, i+length, i+2*length-1 );
    if(i + length < N)
        Merge(Data, TmpData, i, i+length, N-1);
    else
        for(j = i;j < N;j++)TmpData[j] = Data[j];
}

/* L = 左边起始位置, R = 右边起始位置, RightEnd = 右边终点位置*/
void Merge( int Data[], int TmpData[], int L, int R, int RightEnd )
{ /* 将有序的Data[L]~Data[R-1]和Data[R]~Data[RightEnd]归并成一个有序序列 */
    int LeftEnd, NumElements, Tmp;
    NumElements = RightEnd - L + 1;
    LeftEnd = R-1;
    Tmp = L;
    while(L <= LeftEnd && R <= RightEnd)
    {
        if(Data[L] > Data[R])
            TmpData[Tmp++] = Data[R++];
        else
            TmpData[Tmp++] = Data[L++];
    }
    while( L <= LeftEnd )
        TmpData[Tmp++] = Data[L++];
    while( R <= RightEnd )
        TmpData[Tmp++] = Data[R++];
}

测试结果

image-20210811130527026

感觉看整体测试效果里面的非递归实现的效率相对于递归实现的效率并没有特别特别大的提升，算是中规中矩，不过总体看来非递归还是要比递归更快一些，也更节省资源