henry991217
�Blade灬
采纳率33.3%
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条回答 默认 最新

  • 已采纳
    weixin_44343083 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 评论 复制链接分享
  • henry991217 �Blade灬 2021-01-30 00:26

    感谢一楼大哥的提醒

    点赞 评论 复制链接分享

相关推荐