将两个有序数组合并为一个有序数组
在第二个列表向第一个列表逐个插入的过程中,由于第二个列表已经有序,所以后续插入的元素一定不会在前面插入的元素之前。在逐个插入的过程中,每次插入时,只需要从上次插入的位置开始,继续向后寻找插入位置即可。这样一来,我们最多只需要将两个有序数组遍历一次就可以完成合并。
vector<int> merge(vector<int> arr1, vector<int> arr2)
{
vector<int> result;
int index1 = 0, index2 = 0;
while (index1 < arr1.size() && index2 < arr2.size()) {
if (arr1[index1] <= arr2[index2]) {
result[index1 + index2] = arr1[index1];
index1++;
}
else {
result[index1 + index2] = arr2[index2];
index2++;
}
}
// 将剩余数字补到结果数组之后
while (index1 < arr1.size()) {
result[index1 + index2] = arr1[index1];
index1++;
}
while (index2 < arr2.size()) {
result[index1 + index2] = arr2[index2];
index2++;
}
return result;
}
将两个无序数组合并为一个有序数组
我们可以把数组不断地拆成两份,直到只剩下一个数字时,这一个数字组成的数组我们就可以认为它是有序的。然后通过上述合并有序列表的思路,将 1 个数字组成的有序数组合并成一个包含 2 个数字的有序数组,再将 2 个数字组成的有序数组合并成包含 4 个数字的有序数组…直到整个数组排序完成。
void mergeSort(vector<int> arr) {
if (arr.size() == 0) return;
vector<int> result = mergeSort(arr, 0, arr.size() - 1);
// 将结果拷贝到 arr 数组中
for (int i = 0; i < result.size(); i++) {
arr[i] = result[i];
}
}
// 对 arr 的 [start, end] 区间归并排序
vector<int> mergeSort(vector<int> arr, int start, int end) {
// 只剩下一个数字,停止拆分,返回单个数字组成的数组
if (start == end) return vector<int>{arr[start]};
int middle = (start + end) / 2;
// 拆分左边区域
vector<int> left = mergeSort(arr, start, middle);
// 拆分右边区域
vector<int> right = mergeSort(arr, middle + 1, end);
// 合并左右区域
return merge(left, right);
}
归并排序的优化:减少临时空间的开辟
为了减少在递归过程中不断开辟空间的问题,我们可以在归并排序之前,先开辟出一个临时空间,在递归过程中统一使用此空间进行归并即可。
// 将 result 的 [start, middle] 和 [middle + 1, end] 区间合并
void merge(vector<int> arr, int start, int end, vector<int> result)
{
int end1 = (start + end) / 2;
int start2 = end1 + 1;
// 用来遍历数组的指针
int index1 = start;
int index2 = start2;
while (index1 <= end1 && index2 <= end) {
if (arr[index1] <= arr[index2]) {
result[index1 + index2 - start2] = arr[index1++];
}
else {
result[index1 + index2 - start2] = arr[index2++];
}
}
// 将剩余数字补到结果数组之后
while (index1 <= end1) {
result[index1 + index2 - start2] = arr[index1++];
}
while (index2 <= end) {
result[index1 + index2 - start2] = arr[index2++];
}
// 将 result 操作区间的数字拷贝到 arr 数组中,以便下次比较
while (start <= end) {
arr[start] = result[start++];
}
}
void mergeSort(vector<int> arr)
{
if (arr.size() == 0) return;
vector<int> result;
mergeSort(arr, 0, arr.size() - 1, result);
}
// 对 arr 的 [start, end] 区间归并排序
void mergeSort(vector<int> arr, int start, int end, vector<int> result)
{
// 只剩下一个数字,停止拆分
if (start == end) return;
int middle = (start + end) / 2;
// 拆分左边区域,并将归并排序的结果保存到 result 的 [start, middle] 区间
mergeSort(arr, start, middle, result);
// 拆分右边区域,并将归并排序的结果保存到 result 的 [middle + 1, end] 区间
mergeSort(arr, middle + 1, end, result);
// 合并左右区域到 result 的 [start, end] 区间
merge(arr, start, end, result);
}
原地归并排序
实现一文章来源:https://www.toymoban.com/news/detail-709125.html
// 将 arr 的 [start, middle] 和 [middle + 1, end] 区间合并
void merge(vector<int> arr, int start, int end)
{
int end1 = (start + end) / 2;
int start2 = end1 + 1;
// 用来遍历数组的指针
int index1 = start;
int index2 = start2;
while (index1 <= end1 && index2 <= end) {
if (arr[index1] <= arr[index2]) {
index1++;
}
else {
// 右边区域的这个数字比左边区域的数字小,于是它站了起来
int value = arr[index2];
int index = index2;
// 前面的数字不断地后移
while (index > index1) {
arr[index] = arr[index - 1];
index--;
}
// 这个数字坐到 index1 所在的位置上
arr[index] = value;
// 更新所有下标,使其前进一格
index1++;
index2++;
end1++;
}
}
}
// 对 arr 的 [start, end] 区间归并排序
void mergeSort(vector<int> arr, int start, int end)
{
// 只剩下一个数字,停止拆分
if (start == end) return;
int middle = (start + end) / 2;
// 拆分左边区域
mergeSort(arr, start, middle);
// 拆分右边区域
mergeSort(arr, middle + 1, end);
// 合并左右区域
merge(arr, start, end);
}
void mergeSort(vector<int> arr)
{
if (arr.size() == 0) return;
mergeSort(arr, 0, arr.size() - 1);
}
实现二文章来源地址https://www.toymoban.com/news/detail-709125.html
void exchange(vector<int> arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 将 arr 的 [start, middle] 和 [middle + 1, end] 区间合并
void merge(vector<int> arr, int start, int end)
{
int end1 = (start + end) / 2;
int start2 = end1 + 1;
// 用来遍历数组的指针
int index1 = start;
while (index1 <= end1 && start2 <= end) {
if (arr[index1] > arr[start2]) {
// 将 index1 和 start2 下标的数字交换
exchange(arr, index1, start2);
if (start2 != end) {
// 调整交换到 start2 上的这个数字的位置,使右边区域继续保持有序
int value = arr[start2];
int index = start2;
// 右边区域比 arr[start2] 小的数字不断前移
while (index < end && arr[index + 1] < value) {
arr[index] = arr[index + 1];
index++;
}
// 交换到右边区域的这个数字找到了自己合适的位置,坐下
arr[index] = value;
}
}
index1++;
}
}
// 对 arr 的 [start, end] 区间归并排序
void mergeSort(vector<int> arr, int start, int end)
{
// 只剩下一个数字,停止拆分
if (start == end) return;
int middle = (start + end) / 2;
// 拆分左边区域
mergeSort(arr, start, middle);
// 拆分右边区域
mergeSort(arr, middle + 1, end);
// 合并左右区域
merge(arr, start, end);
}
void mergeSort(vector<int> arr) {
if (arr.size() == 0) return;
mergeSort(arr, 0, arr.size() - 1);
}
到了这里,关于数据结构——排序算法——归并排序的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!