归并排序（C语言）

文章目录

• 归并排序
• • 理论
  • 代码

归并排序

理论

分治和递归就像一对好基友，永远不分离，为了看到归并排序的递归过程，我们先看一下归并排序的实现。 这里的递归过程如此曲折，事实上没有什么可担心的，你将代码中的 mergeSort（arr,l,r）理解为「分」和「递」，而将 merge(arr,l,m,r）理解为「治」和「归」，心中就会豁然开朗，递归与分治就是生兄弟。

代码

使用 <= 可以保持排序的稳定性：

// 假设有两个相等的元素，一个在左边(i)，一个在右边(j)
aux1[i] = 5 (原索引位置靠左)
aux2[j] = 5 (原索引位置靠右)

// 使用 <= 时：
if (aux1[i] <= aux2[j]) // 5 <= 5 为 true
// 先放 aux1[i]（左边的5）
// 保持了原始相对顺序：左边的5在右边的5之前

// 使用 < 时：
if (aux1[i] < aux2[j]) // 5 < 5 为 false
// 会先放 aux2[j]（右边的5）
// 破坏了稳定性：右边的5跑到了左

总结

使用 <= 是归并排序的标准写法，因为它保证了排序的稳定性，这在很多实际应用场景中很重要（比如先按分数排序，再按姓名排序）。

#include<stdio.h>
#include<stdlib.h>

static void merge(int* a, int left, int right) {
int i = left;//数组1填位置[left,mid]
int mid = (left + right) / 2;
int j = mid + 1;//数组2填位置偏移量[mid+1,right]

int t[105] = {0};

int k = 0;// 暂存合并好的有序序列
//两个数组都有元素
while ( i <= mid && j <= right) {

if (a[i] <= a[j]) {
t[k] = a[i];
k++;
i++;
}
else {
t[k] = a[j];
k++;
j++;
}
}
//循环结束有一个数组先填完元素
while (i <= mid) {
t[k] = a[i];
k++;
i++;
}
while (j <= right) {
t[k] = a[j];
k++;
j++;
}
/*printf("[%d,%d] [%d,%d]\\n", left, mid, mid+1, right);
printf("left-right+1:%d\\n", right – left + 1);
printf("t:%d\\n", k);*/

for (int i = 0; i < right – left + 1; i++)
{
//把有序序列从t数组中放回到a数组中的原位置
a[left+i] = t[i];//a范围[left,right] t范围[0,k]
}
}

void mergeSort(int* a, int left,int right){
if (left >= right)return;
//1.分
int mid = (left + right) / 2;
mergeSort(a, left, mid);
mergeSort(a, mid + 1, right);
//2.并
merge(a, left, right);
}

int main() {
int n;
int a[105];
scanf("%d", &n);

for (int i = 1; i <= n; i++)
{
scanf("%d", &a[i]);
}

mergeSort(a, 1, n);

for (int i = 1; i <= n; i++)
{
printf("%d", a[i]);
}

return 0;
}