【数据结构--八大排序】之归并排序

💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃个人主页 ：阿然成长日记 👈点击可跳转 📆 个人专栏： 🔹数据结构与算法🔹C语言进阶 🚩 不能则学，不知则问，耻于问人，决无长进 🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍

文章目录 一、什么是归并排序二、思路：三、流程图：方法一（递归法）1.代码展示：2.测试结果 方法二（非递归法）1.代码：2.测试结果： 四、时间复杂度

一、什么是归并排序

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

二、思路：

第一阶段：分（下图1~2）采用分治的思想，使用递归的一直向下分割。最终每个元素为一组。如下图红色虚线位置。 第二阶段：合（下图2~3）开始归并，合并分割好的两个数组，将其有序的存储到tmp数组中。向上归并，继续重复此步骤. 归并思路：合并两个有序数组。 最后，由于排序好的元素一直都是存到tmp数组中的，所以最后还需将tmp拷贝到a数组中。 补充：

拷贝数组时需要用到方法memcpy;

void * memcpy ( void * destination, const void * source, size_t num );

三、流程图：

方法一（递归法） 1.代码展示： #include<string.h> //归并排序 void MergeSort(int* a, int* tmp, int begin, int end) { //如果end <= begin结束向下递的过程。 if (end <= begin) return; int mid = (begin + end) / 2; MergeSort(a, tmp, begin, mid); MergeSort(a, tmp, mid + 1, end); //走到这已经递归到头，开始回溯 //每次都是合并两个有序数组归并到tmp数组中，最后在拷贝回a数组。 //记录下当前坐标 int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; int i = begin; //依次比较两个数组的值，选择小的放入数组tmp中。 while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2] ) { tmp[i++] = a[begin1++]; } else { tmp[i++] = a[begin2++]; } } //如果begin1中还剩有元素，依次放入tmp中。 while (begin1 <= end1) { tmp[i++] = a[begin1++]; } //如果begin2中还剩有元素，依次放入tmp中。 while (begin2 <= end2) { tmp[i++] = a[begin2++]; } //将tmp拷贝回a数组。 memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int)); } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } MergeSort(a, tmp, 0, n - 1); free(tmp); } 2.测试结果 int main() { int a[10] = { 2, 6 ,7 ,5 ,9, 3 ,4 ,1 ,0 ,8 }; MergeSort(a, 10); print(a, 10); return 0; }

方法二（非递归法） 1.代码： void MergeSortNon(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); return; } int gap = 1; while (gap < n) { for (int i = 0; i < n; i += 2 * gap) { int begin1 = i, end1 = i + gap - 1; int begin2 = i + gap, end2 = i + 2 * gap - 1; // [begin1,end1] [begin2,end2] 归并 int index = i; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[index++] = a[begin1++]; } else { tmp[index++] = a[begin2++]; } } while (begin1 <= end1) { tmp[index++] = a[begin1++]; } while (begin2 <= end2) { tmp[index++] = a[begin2++]; } // 拷贝回原数组 memcpy(a + i, tmp + i, (2 * gap) * sizeof(int)); } gap *= 2; } free(tmp); } 2.测试结果： int main() { int a[10] = { 2, 6 ,7 ,5 ,9, 3 ,4 ,1 ,0 ,8 }; MergeSortNon(a, 10); print(a, 10); return 0; }

四、时间复杂度

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