数据结构的归并排序（c语言版）-个人在线分享

数据结构的归并排序（c语言版）插图

一.归并排序的基本概念

1.基本概念

归并排序是一种高效的排序算法,它采用了分治的思想。它的基本过程如下:

将待排序的数组分割成两个子数组,直到子数组只有一个元素为止。
然后将这些子数组两两归并,得到有序的子数组。
不断重复第二步,直到最终得到有序的整个数组。

2.核心思想

归并排序的核心是”分而治之”的思想。通过不断地将数组拆分成更小的子数组,直至子数组只有一个元素,然后再将这些有序的子数组合并起来,最终得到一个有序的数组。

与简单的冒泡排序或选择排序相比,归并排序的时间复杂度为O(nlogn),这使它能够高效地处理大规模的数据集。虽然它需要O(n)的额外空间来存储中间结果,但其优秀的时间复杂度使其成为处理大数据量排序问题的首选算法之一。

总的来说,归并排序是一种强大而高效的排序算法,它体现了分治策略在算法设计中的重要应用。如果您有任何其他问题,欢迎随时向我咨询。

3.优点

优点:

时间复杂度稳定:归并排序的时间复杂度为O(nlogn),不管输入数据的初始状态如何,时间复杂度都是稳定的。这使它能够高效处理大规模数据。
稳定排序:归并排序是一种稳定的排序算法,也就是说,当两个相等的元素出现时,它们在输出序列中的相对顺序与输入序列中的相对顺序一致。这对某些应用场景很重要。
并行计算友好:归并排序的”分而治之”特性使得它很容易并行化,在多核处理器上可以获得很好的性能提升。

4.缺点

缺点:

需要额外空间:归并排序需要额外的内存空间来存储中间结果,空间复杂度为O(n)。这可能成为一个瓶颈,尤其是在内存受限的环境中。
数据交换频繁:归并排序需要频繁地将数据从输入数组复制到临时数组,这在某些情况下可能会降低性能。
无法就地排序:归并排序无法在原数组上就地排序,需要使用额外的空间。这对于某些内存受限的场景可能是个问题。

二.归并排序的功能

归并排序的基本功能就是对一组数据进行排序。具体来说,它可以实现以下几个功能:

将无序的数组或列表排序为有序的数组或列表。归并排序可以将任意大小的输入集合有效地排序,包括大型数据集。
保持数据的相对位置关系。如果输入数据中存在相等的元素,归并排序会保留它们原有的相对顺序,这在某些应用场景中很重要。
支持并行计算。由于归并排序的”分而治之”特性,它非常适合在多核处理器上并行执行,从而获得大幅的性能提升。
可以用于外部排序。当数据量太大无法一次性装入内存时,可以采用外部排序的方式,先将数据划分成多个小块,然后使用归并排序分别对这些小块进行排序,最后合并这些有序块。
可以作为其他算法的子过程。归并排序常被用作其他算法的核心步骤,比如快速排序、外部排序等。

归并排序是一种通用且高效的排序算法,它在各种规模和类型的数据排序中都有重要应用。它的功能十分强大,能够满足绝大多数排序需求。

三.归并排序的代码实现

1.合并两个有序数组

定义三个索引变量 i, j, k，分别用来遍历左数组、右数组和目标数组。
使用 while 循环比较左右数组当前元素的大小,将较小的元素依次添加到目标数组中。
当左数组或右数组中还有剩余元素时,将它们依次添加到目标数组的末尾。

// 合并两个有序数组
void merge(int arr[], int left[], int left_size, int right[], int right_size, int size) {
    int i = 0, j = 0, k = 0;
    while (i < left_size && j < right_size) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    while (i < left_size) {
        arr[k++] = left[i++];
    }
    while (j < right_size) {
        arr[k++] = right[j++];
    }
}

2.递归实现

首先,它检查数组大小是否小于等于 1,如果是,则直接返回,因为单个元素已经是有序的了。
接下来,它将数组分为两个子数组:左子数组 left 和右子数组 right。计算中点 mid 作为分割点,将原数组 arr 分为左右两部分。
然后,它将原数组 arr 的元素复制到左右两个临时数组 left 和 right 中。
递归地对左右两个子数组分别调用 merge_sort 函数,对它们进行排序。
最后,它调用 merge 函数,将已经排序的左右子数组合并回原数组 arr。

// 递归实现归并排序
void merge_sort(int arr[], int size) {
if (size <= 1) {
return;
}
int mid = size / 2;
int left[mid];
int right[size - mid];
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < size; i++) {
right[i - mid] = arr[i];
}
merge_sort(left, mid);
merge_sort(right, size - mid);
merge(arr, left, mid, right, size - mid);
}

3.非递归实现

首先,它申请了一个临时数组 temp，用来存储合并后的有序子数组。这是非递归实现所需要的额外空间。
然后,它使用一个外层循环来控制子数组的宽度 width。初始值为 1,每次翻倍,直到 width 大于等于数组大小 size。
内层循环遍历数组,每次处理长度为 2 * width 的两个相邻子数组。
对于每个子数组对,它计算左子数组的长度 left_size 为 width,右子数组的长度 right_size 可能会小于 width (当剩余元素不足 width 时)。
然后调用 merge 函数,将左右两个有序子数组合并为一个有序子数组,存储在原数组 arr 中。
最后,释放临时数组 temp 占用的动态内存。

// 非递归实现归并排序
void iterative_merge_sort(int arr[], int size) {
    int *temp = (int *)malloc(size * sizeof(int));
    if (!temp) {
        printf("Memory allocation failed.
");
        return;
    }

    for (int width = 1; width < size; width *= 2) {
        for (int i = 0; i < size; i += 2 * width) {
            int left_size = width;
            int right_size = (i + 2 * width < size) ? width : size - i - width;
            merge(arr + i, arr + i, left_size, arr + i + width, right_size, size);
        }
    }

    free(temp);
}

四.归并排序的源代码

1.递归

#include 
#include 

// 合并两个有序数组
void merge(int arr[], int left[], int left_size, int right[], int right_size) {
    int i = 0, j = 0, k = 0;
    while (i < left_size && j < right_size) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    while (i < left_size) {
        arr[k++] = left[i++];
    }
    while (j < right_size) {
        arr[k++] = right[j++];
    }
}

// 递归实现归并排序
void merge_sort(int arr[], int size) {
    if (size <= 1) {
        return;
    }
    int mid = size / 2;
    int left[mid];
    int right[size - mid];
    for (int i = 0; i < mid; i++) {
        left[i] = arr[i];
    }
    for (int i = mid; i < size; i++) {
        right[i - mid] = arr[i];
    }
    merge_sort(left, mid);
    merge_sort(right, size - mid);
    merge(arr, left, mid, right, size - mid);
}

int main() {
    int arr[] = {5, 2, 4, 6, 1, 3, 2, 6};
    int size = sizeof(arr) / sizeof(arr[0]);
    merge_sort(arr, size);
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("
");
    return 0;
}

2.非递归

#include 
#include 

// 合并两个有序数组
void merge(int arr[], int left[], int left_size, int right[], int right_size, int size) {
    int i = 0, j = 0, k = 0;
    while (i < left_size && j < right_size) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    while (i < left_size) {
        arr[k++] = left[i++];
    }
    while (j < right_size) {
        arr[k++] = right[j++];
    }
}

// 非递归实现归并排序
void iterative_merge_sort(int arr[], int size) {
    int *temp = (int *)malloc(size * sizeof(int));
    if (!temp) {
        printf("Memory allocation failed.
");
        return;
    }

    for (int width = 1; width < size; width *= 2) {
        for (int i = 0; i < size; i += 2 * width) {
            int left_size = width;
            int right_size = (i + 2 * width < size) ? width : size - i - width;
            merge(arr + i, arr + i, left_size, arr + i + width, right_size, size);
        }
    }

    free(temp);
}

int main() {
    int arr[] = {5, 2, 4, 6, 1, 3, 2, 6};
    int size = sizeof(arr) / sizeof(arr[0]);
    iterative_merge_sort(arr, size);
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("
");
    return 0;
}

一	二	三	四	五	六	日
						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