目录
- 1 归并排序的基本思想
- 1.1 下标分治与值分治
- 1.2 归并排序实现思路
- 2 归并排序的实现
- 2.1 递归版归并排序
- 2.2 迭代版归并排序
- 3 归并排序的时间复杂度和空间复杂度
1 归并排序的基本思想
1.1 下标分治与值分治
- 和快速排序一样,基本思想即分治,但其两者区别在于归并排序是下标分治,而快速排序是值分治
- 分治
即"分而治之",将大问题化成多个小问题解决,小问题又化成更多个小问题解决
- 两种不同的分治思想的不同之处其实就是化成小问题的方式不同
- 值分治就是先比较数的大小,再将数组分为"小数部分"和"大数部分"两个部分解决问题
- 而下标分治则先通过物理位置将数组分为若干个小部分,再比较值的大小重新排序
1.2 归并排序实现思路
- 如图,我们将数据先按下标单个分开,同类颜色的分到一个组内,意味着每个组拥有两个有序数组(如果数组只有一个元素就必定有序)
- 同类颜色的数组按以下方式并为一个有序数组(在两组数中的begin位置选取较小的数放入tmp数组),并再次重新分组,第二趟分组时,依旧保持每组数有两个有序数组,意味着有序数组的元素个数变为了2
- 当末尾数字不够构成一组数的时候就不参与分组(注意:构成一组数的必要条件是拥有两个有序数组,数组内元素个数不做要求)
- 如此往复下最终一定能并为一个有序数组
请看完整动画:
2 归并排序的实现
2.1 递归版归并排序
- 递归版归并排序需要先将数组不断细分再开始排序,所以你能在代码中看到类似于后序遍历的逻辑(类似于深度优先)
// arr--要排序的数组 // tmp--临时开辟的数组 // left--用于划分"组" // right--用于划分"组" // begin1--用于划分组内的两个有序数组,参与拷贝到tmp的过程 // end1--用于划分组内的两个有序数组,参与拷贝到tmp的过程 // begin2--用于划分组内的两个有序数组,参与拷贝到tmp的过程 // end2--用于划分组内的两个有序数组,参与拷贝到tmp的过程 //归并排序子函数 void _MergeSort(int* arr, int* tmp, int left, int right) { assert(arr); //arr判空 if (left >= right) //如果"组"内只有1个数或者少于1个数,就返回 { return; } int midi = (left + right) / 2; //midi帮助原数组对半分 if (right - left != 1) //如果"组"只有1个数就不对半分了 { _MergeSort(arr, tmp, left, midi); //分左 _MergeSort(arr, tmp, midi + 1, right); //分右 } //以上代码调用完后就能保证当前"组"内一定包含2个有序数组 int begin1 = left; //定义排序时需要的变量 int end1 = midi; int begin2 = midi + 1; int end2 = right; int tmp_pos = left; //tmp数组的下标 while (begin1 <= end1 && begin2 <= end2) //比较两个有序数组begin位置的数并选出小的放进tmp里 { tmp[tmp_pos++] = arr[begin1] <= arr[begin2] ? arr[begin1++] : arr[begin2++]; } while (begin1 <= end1) //如果第一个有序数组有剩下的就一股脑扔给tmp { tmp[tmp_pos++] = arr[begin1++]; } while (begin2 <= end2) //如果第二个有序数组有剩下的就一股脑扔给tmp { tmp[tmp_pos++] = arr[begin2++]; } memcpy(arr + left, tmp + left, sizeof(int) * (right - left + 1)); //将排过序的内容拷贝回原数组的原位置 } //归并排序 void MergeSort(int* arr, int left, int right) { assert(arr); //arr判空 int* tmp = (int*)calloc(right - left + 1, sizeof(int)); //开辟tmp数组 if (tmp == NULL) { perror("calloc fail"); exit(1); } _MergeSort(arr, tmp, left, right); //不使用子函数的话会让tmp重复开辟,会浪费很多空间 free(tmp); //释放tmp数组 tmp = NULL; }2.2 迭代版归并排序
- 迭代版的逻辑不同于递归版的是,递归版是先把整个arr数组都细分成单个数再开始排序,而迭代版则是细分一组就排序一组,并且从一开始就直接细分为"最小组"而不是像递归版一样不断向下分(因为细分的结果是已知的,即单个数成为一个有序数组,所以递归对半分这个步骤就直接被省略了)
// 其他变量与递归版一致,但这里多了step这个变量,step指1个"组"内的有序数组的元素个数 //归并排序(迭代) void MergeSortNonR(int* arr, int left, int right) { assert(arr); //arr判空 int* tmp = (int*)calloc((right - left + 1), sizeof(int)); //临时数组tmp的开辟 if (tmp == NULL) { perror("calloc fail"); exit(1); } for (int step = 1; step < (right - left + 1); step *= 2) //step初始设置为1即有序数组的初始元素个数就是1 //在下轮排序时,有序数组的元素个数是上一轮的2倍,所以step设置为每轮过后 *2 //有序数组至少需要2组,所以step必须要小于总元素个数 { for (int i = 0; i <= right; i += (2 * step)) //i是"组"的初始位置 { int begin1 = i; int end1 = i + step - 1; if (end1 > right) //如果最后一组的第一个有序数组都凑不齐,就直接不用排了直接结束 { break; } int begin2 = i + step; if (begin2 > right) //如果最后一组的第一个有序数组凑齐了但第二个有序数组压根就不存在,那也不用排了直接结束 { break; } int end2 = i + 2 * step - 1; if (end2 > right) //如果最后一组的第二个有序数组没凑齐但有数字在数组里,那就可以参与数组排序,此时只需要休整一下end2的位置就行 { end2 = right; } int tmp_pos = i; while (begin1 <= end1 && begin2 <= end2) //比较两个有序数组begin位置的数并选出小的放进tmp里 { tmp[tmp_pos++] = arr[begin1] <= arr[begin2] ? arr[begin1++] : arr[begin2++]; } while (begin1 <= end1) //如果第一个有序数组有剩下的就一股脑扔给tmp { tmp[tmp_pos++] = arr[begin1++]; } while (begin2 <= end2) //如果第二个有序数组有剩下的就一股脑扔给tmp { tmp[tmp_pos++] = arr[begin2++]; } memcpy(arr + i, tmp + i, (end2 - i + 1) * sizeof(int)); //每"组"排过序之后都要重新拷贝回原数组 } } }3 归并排序的时间复杂度和空间复杂度
- 归并排序的时间复杂度其实很好算,递归的深度为logN,每层都需要对N个数排序,所以时间复杂度是O(N*logN)
- 因为归并排序只开辟过一个大小为N的tmp数组,所以归并排序的空间复杂度为O(N)
佬!都看到这了,如果觉得有帮助的话一定要点赞啊佬 >v< !!!
放个卡密在这,感谢各位能看到这儿啦!