💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤
📃个人主页 ：阿然成长日记 👈点击可跳转
🚩 不能则学，不知则问，耻于问人，决无长进
🍭 🍯 🍎 🍏 🍊 🍋 🍒 🍇 🍉 🍓 🍑 🍈 🍌 🍐 🍍
文章目录
一、什么是归并排序
归并排序：是建立在归并操作上的一种
有效，稳定的排序算法，该算法是采用分治法（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)
