排序---归并排序

一、定义

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

二、实现原理

归并排序的思想是：将数组分成左右两个数组，假如左右两个数组都有序了，那么可以借用一个临时数组来对这两个有序数组进行拼接，使整体有序（归并过程）。而该两个左右数组又可分成左右子数组（递归过程），以此类推，当子数组元素个数为1时，就可以认为这个子数组是有序的，然后用临时数组对这两个子数组进行排序，再将已经有序的临时数组拷贝给原数组。

三、代码实现

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

//时间复杂度：O(N*logN),空间复杂度：O(N)

void MergeSort(int* arr, int* tmp, int begin, int end)
{
if (begin >= end) {
return;
}

//分区间：
int mid = (begin + end) / 2;
    //[begin,mid] mid [mid+1,end]  ,区间要这样分，防止死循环，如： begin=2,end=3,mid=2;
//                           假如区间以这种方式递归：(arr,tmp,begin,mid-1)==(arr,tmp,2,1)：正常
//                                                   (arr,tmp,mid,end)==(arr,tmp,2,3) ：这里会导致死循环
MergeSort(arr, tmp, begin, mid);
MergeSort(arr, tmp, mid + 1, end);       //下面这种区间分法就不会：(arr,tmp,begin,mid)==(arr,tmp,2,2)
//                                                                 (arr,tmp,mid+1,end)==(arr,tmp,3,3)

//归并：
int left1 = begin, right1 = mid;
int left2 = mid + 1, right2 = end;

int i = begin; //临时数组开始存储数据的位置要在begin的位置开始，否则在拷贝临时数组给原数组时，
                                      //会将原数组的数据弄乱

while (left1 <= right1 && left2 <= right2) {
if (arr[left1] <= arr[left2]) {
tmp[i++] = arr[left1++];
}
else {
tmp[i++] = arr[left2++];
}
}
//剩余的：
while (left1 <= right1) {
tmp[i++] = arr[left1++];
}
while (left2 <= right2) {
tmp[i++] = arr[left2++];
}

//将已经有序的tmp数组复制到arr中，注意拷贝的起始位置起点和目标位置起点也是要根据begin来确定的
//起始位置是tmp+begin ,目标位置是arr+beign
memcpy(arr + begin, tmp + begin, sizeof(int) * (end - begin + 1));//end-begin+1是待拷贝数组的元素个数
}



void Print(int* p, int size)
{
for (int i = 0; i < size; i++) {
printf("%d ", p[i]);
}
printf("\n");
}
void test()
{
int arr[] = { 5,3,7,2,8,4,6,1 };
int size = sizeof(arr) / sizeof(int);
int* tmp = (int*)malloc(sizeof(int) * size);
MergeSort(arr,tmp,0,size-1);
Print(arr, size);
free(tmp);
}
int main()
{

test();
return 0;
}

原文地址：https://blog.csdn.net/2303_79004636/article/details/140569829

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！