期末复习——排序算法

直接选择排序

原理：将待排序数组分为已排序区间和未排序区间，每一次循环从未排序区间中找到最小（或者最大）的元素，与未排序区间的第一个元素交换位置，从而扩大已排序区间的长度，直到未排序区间为空。

思路：每次从未排序区间的第一个元素开始遍历寻找最小元素→将未排序区间中的最小元素放置到已排序区间中

代码实现：

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
#include <stdio.h>
void selectionSort(int arr[], int n){
    for(int i=0;i<n-1;i++){ //外层循环i指示未排序区间的第一个元素的位置。循环只进行n-1轮，最后一个元素自动有序
        int min_index=i; //在外层循环内部定义min_index，进入新一轮自动更新min_index的值
        for (int j = i; j< n; j++) //内层循环：遍历寻找未排序区间中最小元素的位置
        {
            if (arr[j]<arr[min_index])
            {
                min_index=j;
            }
        }
        if (min_index!=i)
        {
            int temp=arr[i];
            arr[i]=arr[min_index];
            arr[min_index]=temp;
        }//交换最小元素和未排序区间第一个元素的位置；当min_index==i时无需交换
    }
    return;
}
int main(){
    int arr[]={6,8,2,1,3};//测试用例
    selectionSort(arr,5);
    for (int i = 0; i < 5; i++)
    {
        printf("%d ",arr[i]);
    }
}

输出结果为

1 2 3 6 8

直接排序算法稳定性：不稳定

时间复杂度

最好情况 最坏情况 平均情况
O() O() O()

归并排序

原理：将数组拆分为最小单元，再将最小单元两两组合成有序数组，逐步向上整合，直至最终组合成有序的原数组

C语言实现：

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

#include <stdio.h>
#include <stdlib.h>
// 合并两个有序子数组：arr[left...mid] 和 arr[mid+1...right]
//思路：计算左右两个数组长度→定义临时数组存储左右数组→逐次比较左右数组元素的大小，填入原数组
void merge(int arr[], int left, int mid, int right) {
    int len1=mid-left+1;//计算左子数组的长度要加1
    int len2=right-mid;//计算右子数组的长度不用+1

    //定义两个临时数组存储左右子数组，防止改变原数组
    int *leftarr=(int*)malloc(len1*sizeof(int));
    int *rightarr=(int*)malloc(len2*sizeof(int));
    if (leftarr==NULL||rightarr==NULL)
    {
        printf("内存分配失败！\n");
        return;
    }
    for (int i = 0; i < len1; i++)
    {
        leftarr[i]=arr[left+i];
    }
    for (int j = 0; j < len2; j++)
    {
        rightarr[j]=arr[mid+j+1];//注意要加1
    }

    //定义三个数组指针，i为左数组指针，j为右数组指针，k指向原数组的起始位置
    int i=0,j=0,k=left;
    //比较左右数组的元素，将较小值填进原数组
    while (i<len1&&j<len2)
    {
        if (leftarr[i]<=rightarr[j])
        {
            arr[k++]=leftarr[i++];
        }
        else{
            arr[k++]=rightarr[j++];
        }
    }
    //当左右数组中有一个数组已经全部填入原数组，另一个数组未填入的元素直接赋值给原数组
    while (i<len1)
    {
        arr[k++]=leftarr[i++];
    }
    while (j<len2)
    {
        arr[k++]=rightarr[j++];
    }
    
    //释放动态内存
    free(leftarr);
    free(rightarr);
    return;
}

// 归并排序递归函数：对arr[left...right]进行排序
void mergeSort(int arr[], int left, int right){
    //递归终止条件：left>=right，说明数组已经拆分到最小单元了
    if (left>=right)
    {
        return;
    }

    //拆分数组
    int mid=left+(right-left)/2;
    mergeSort(arr,left,mid);
    mergeSort(arr,mid+1,right);//注意加1

    //拆到最小单元后，逐步向上有序整合数组
    merge(arr,left,mid,right);
}

// 打印数组
void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 主函数：测试归并排序
int main() {
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("原始数组：");
    printArray(arr, n);

    // 调用归并排序：左边界0，右边界n-1
    mergeSort(arr, 0, n - 1);

    printf("排序后数组（升序）：");
    printArray(arr, n);

    return 0;
}

输出结果

原始数组：12 11 13 5 6 7 
排序后数组（升序）：5 6 7 11 12 13

归并排序算法稳定性：稳定

时间复杂度

最好情况 最坏情况 平均情况
O() O() O()