2021-01-29 18:03 阅读 17

# 关于归并排序的一些BUG

``````#include <iostream>
using namespace std;

/**
* 归并排序
* 简介:将两个（或两个以上）"有序"表合并成一个新的有序表 即把待排序序列分为若干个子序列，
*     每个子序列是有序的。然后再把有序子序列合并为整体有序序列
* 时间复杂度为O(nlogn)
* 稳定排序方式
* @param nums 待排序数组
@return 输出有序数组
**/
void merge(int arr[], int start, int mid,int end)
{
mid = (start + end) / 2;
int mi = mid + 1;
int k = 0;
int  *tmp = new int[end+1];

while (start <= mid && mi <= end)
{
if (arr[start] <= arr[mid])
{
tmp[k++] = arr[start++];
}
else
{
tmp[k++] = arr[mi++];
}

}
//若其中一个没排完，把剩下的元素放进tmp
while (start <= mid)
tmp[k++] = arr[start++];
while (mi<= end)
tmp[k++] = arr[mi++];

for (int i = start, j = 0; i <= end; i++, j++) {
arr[i] = tmp[j];
}
delete []tmp;
tmp = nullptr;
}

void merge_sort(int arr[], int start, int end)//递归
{

if (arr==nullptr||end == 0 || ( end-start)<=1)
{
return;
}

if (start < end)
{
int mid = (start + end) / 2;
int middle = mid + 1;

merge_sort(arr, start, mid);
merge_sort(arr, middle , end);
merge(arr, start, mid, end);//将两个有序子数组合并操作
}

}

int main()
{
int a[] = {3,2,9,20,8,15,18};
int length = sizeof(a) / sizeof(a[0]);
merge_sort(a, 0, length-1);
for (int i = 0; i < length; i++)
cout << a[i] << " ";
}

``````

• 点赞
• 写回答
• 关注问题
• 收藏
• 复制链接分享

#### 2条回答默认 最新

• 已采纳
great-sakya 2021-01-29 19:22
``````#include <iostream>
using namespace std;
void merge(int arr[], int start, int mid,int end)
{
mid = (start + end) / 2;
int mi = mid + 1;
int k = 0;
int  *tmp = new int[end-start+1];
int s = start;//下面start++自增，改变start的值，s为start备份
while (start <= mid && mi <= end)
{
if (arr[start] <= arr[mi])//这里mid应该改为mi
{
tmp[k++] = arr[start++];
}
else
{
tmp[k++] = arr[mi++];
}

}
//若其中一个没排完，把剩下的元素放进tmp
while (start <= mid)
tmp[k++] = arr[start++];
while (mi<= end)
tmp[k++] = arr[mi++];

for (int i = s, j = 0; i <= end; i++, j++) {//用start的备份s，start已自增
arr[i] = tmp[j];
cout << tmp[j] << " ";
}
cout<<endl;
delete []tmp;
tmp = nullptr;
}

void merge_sort(int arr[], int start, int end)//递归
{

if (arr==nullptr||end == 0 || ( end-start)==0)
{
return;
}
if(end-start == 1){//少了一步
if(arr[start]>arr[end]){
int temp = arr[start];
arr[start] = arr[end];
arr[end] = temp;
}
return;
}

if (start < end)
{
int mid = (start + end) / 2;
int middle = mid + 1;

merge_sort(arr, start, mid);
merge_sort(arr, middle , end);
merge(arr, start, mid, end);//将两个有序子数组合并操作
}

}

int main()
{
int a[] = {3,2,9,20,8,15,18};
int length = sizeof(a) / sizeof(a[0]);
merge_sort(a, 0, length-1);
for (int i = 0; i < length; i++)
cout << a[i] << " ";
}``````
点赞 1 评论 复制链接分享