【数据结构与算法】归并排序

devtools/2024/9/23 10:42:35/

归并排序目录

一.归并排序的原理
二.有序的归并实现
三.无序的归并实现(分治法)
四.归并排序的实现
五.完整代码

一.归并排序的原理

在这里插入图片描述
如何将这两个数组排序?

二.有序的归并实现

将一个数组分为两段,那边的值小就加入到新数组中,直到一边已经加完了.
在这里插入图片描述
有一种情况就是一边已经加入完了,但是还有一边还有没有加入的,所以我们需要添加进数组,最后在拷贝到原数组.

在这里插入图片描述

三.无序的归并实现(分治法)

我们也已经注意到了,上面的是有序的两端合并排序,那如果无序的呢?
我们可以拆分为有序的,就是一直拆为只有1个元素,1个元素必定有序,然后可以采用归并.

四.归并排序的实现

在这里插入图片描述

五.完整代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>void mergeAdd(int arr[], int left, int mid, int right,int *temp)
{int i = left;   //指向左边数组最小的元素位置int j = mid;    //指向右边数组最小的元素位置int k = left;   //临时数组的下标while (i < mid && j <= right){if (arr[i] < arr[j]){temp[k++] = arr[i++];}else{temp[k++] = arr[j++];}}while (i < mid){temp[k++] = arr[i++];}while (j <= right){temp[k++] = arr[j++];}//把temp中的内容拷贝到arr数组中memcpy(arr + left, temp+left, sizeof(int) * (right - left + 1));
}void mergeSort(int arr[], int left, int right, int* temp)
{int mid = 0;if (left < right){mid = left + (right - left) / 2;//数据太大时可以防止溢出mergeSort(arr, left, mid, temp);mergeSort(arr, mid + 1, right, temp);mergeAdd(arr, left, mid+1, right, temp);}
}int main()
{int beauties[] = { 5,1,3,6,4,2,8,7 };int len = sizeof(beauties) / sizeof(beauties[0]);int* temp = new int[len];int mid = len / 2;mergeSort(beauties, 0, len - 1, temp);printf("执行归并大法:\n");for (int i = 0; i < len; i++){printf("%d ", beauties[i]);}system("pause");return 0;
}