备案控制台
探索云世界
开发者社区 人工智能 文章 正文

归并排序——“数据结构与算法”

2024-04-17 13
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 归并排序——“数据结构与算法”

各位CSDN的uu们好呀，今天，小雅兰的内容仍然是数据结构与算法专栏的排序呀，下面，让我们进入归并排序的世界吧！！！

归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。 归并排序核心步骤：

void _MergeSort(int* a, int begin, int end, int* tmp)
{
  if (begin >= end)
  {
    return;
  }
  int mid = (begin + end) / 2;
  //[begin,mid] [mid+1,end]
  _MergeSort(a, begin, mid, tmp);
  _MergeSort(a, mid + 1, end, tmp);
  //归并两个区间
  int begin1 = begin;
  int begin2 = mid + 1;
  int end1 = mid;
  int end2 = end;
  int i = begin;
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (a[begin1] < a[begin2])
    {
      tmp[i++] = a[begin1++];
    }
    else
    {
      tmp[i++] = a[begin2++];
    }
  }
  while (begin1 <= end1)
  {
    tmp[i++] = a[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[i++] = a[begin2++];
  }
  memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
//归并排序
void MergeSort(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  _MergeSort(a, 0, n - 1, tmp);
  free(tmp);
}

测试一下归并排序：

void TestMergeSort()
{
   int a[] = { 2,1,4,3,6,5,7,9,8,10 };
   PrintArray(a, sizeof(a) / sizeof(a[0]));
   MergeSort(a, sizeof(a) / sizeof(a[0]));
   PrintArray(a, sizeof(a) / sizeof(a[0]));
}

归并排序的特性总结：

  1. 归并的缺点在于需要O(N)的空间复杂度，归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度：O(N*logN)
  3. 空间复杂度：O(N)
  4. 稳定性：稳定

归并排序非递归

void MergeSortNonR(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
    perror("malloc失败!!!");
    return;
  }
  int gap = 1;
  while (gap < n)
  {
    int j = 0;
    for (int i = 0; i < n; i += gap)
    {
      //每组的合并数据
      int begin1 = i;
      int end1 = i + gap - 1;
      int begin2 = i + gap;
      int end2 = i + 2 * gap - 1;
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] < a[begin2])
        {
          tmp[j++] = a[begin1++];
        }
        else
        {
          tmp[j++] = a[begin2++];
        }
      }
      while (begin1 <= end1)
      {
        tmp[j++] = a[begin1++];
      }
      while (begin2 <= end2)
      {
        tmp[j++] = a[begin2++];
      }
 
    }
    memcpy(a, tmp, sizeof(int) * n);
    gap *= 2;
  }
  free(tmp);
}

但是这个代码是有非常严重的越界问题的，只有有2的次方的数据的时候，才不会越界！！！

小雅兰在这里打印几组数据看得更加清楚：

void MergeSortNonR(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
    perror("malloc失败!!!");
    return;
  }
  // 1  2  4 ....
  int gap = 1;
  while (gap < n)
  {
    int j = 0;
    for (int i = 0; i < n; i += 2 * gap)
    {
      // 每组的合并数据
      int begin1 = i;
      int end1 = i + gap - 1;
      int begin2 = i + gap;
      int end2 = i + 2 * gap - 1;
 
      printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
 
      if (end1 >= n || begin2 >= n)
      {
        break;
      }
 
      // 修正
      if (end2 >= n)
      {
        end2 = n - 1;
      }
 
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] < a[begin2])
        {
          tmp[j++] = a[begin1++];
        }
        else
        {
          tmp[j++] = a[begin2++];
        }
      }
 
      while (begin1 <= end1)
      {
        tmp[j++] = a[begin1++];
      }
 
      while (begin2 <= end2)
      {
        tmp[j++] = a[begin2++];
      }
 
      // 归并一组，拷贝一组
      memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
    }
    printf("\n");
    gap *= 2;
  }
  free(tmp);
}

这样修正一下就可以啦！！！

这个越界问题还有第二种解决方案：

void MergeSortNonR(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
 
  // 1  2  4 ....
  int gap = 1;
  while (gap < n)
  {
    int j = 0;
    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;
 
      printf("修正前：[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
 
      if (end1 >= n)
      {
        end1 = n - 1;
 
        // 不存在区间
        begin2 = n;
        end2 = n - 1;
      }
      else if (begin2 >= n)
      {
        // 不存在区间
        begin2 = n;
        end2 = n - 1;
      }
      else if(end2 >= n)
      {
        end2 = n - 1;
      }
 
      printf("修正后：[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
 
 
      while (begin1 <= end1 && begin2 <= end2)
      {
        if (a[begin1] <= a[begin2])
        {
          tmp[j++] = a[begin1++];
        }
        else
        {
          tmp[j++] = a[begin2++];
        }
      }
 
      while (begin1 <= end1)
      {
        tmp[j++] = a[begin1++];
      }
 
      while (begin2 <= end2)
      {
        tmp[j++] = a[begin2++];
      }
    }
    printf("\n");
 
    memcpy(a, tmp, sizeof(int) * n);
    gap *= 2;
  }
 
  free(tmp);
}

测试各种排序

// 测试排序的性能对比
void TestOP()
{
  srand(time(0));
  const int N = 1000000;
  int* a1 = (int*)malloc(sizeof(int) * N);
  int* a2 = (int*)malloc(sizeof(int) * N);
  int* a3 = (int*)malloc(sizeof(int) * N);
  int* a4 = (int*)malloc(sizeof(int) * N);
  int* a5 = (int*)malloc(sizeof(int) * N);
  int* a6 = (int*)malloc(sizeof(int) * N);
  int* a7 = (int*)malloc(sizeof(int) * N);
 
  for (int i = 0; i < N; ++i)
  {
    a1[i] = rand();
    a2[i] = a1[i];
    a3[i] = a1[i];
    a4[i] = a1[i];
    a5[i] = a1[i];
    a6[i] = a1[i];
    a7[i] = a1[i];
  }
  int begin1 = clock();
  InsertSort(a1, N);
  int end1 = clock();
 
  int begin2 = clock();
  ShellSort(a2, N);
  int end2 = clock();
 
  int begin3 = clock();
  SelectSort(a3, N);
  int end3 = clock();
 
  int begin4 = clock();
  HeapSort(a4, N);
  int end4 = clock();
 
  int begin5 = clock();
  QuickSort(a5, 0, N - 1);
  int end5 = clock();
 
  int begin6 = clock();
  MergeSort(a6, N);
  int end6 = clock();
 
  int begin7 = clock();
  BubbleSort(a7, N);
  int end7 = clock();
 
  printf("InsertSort:%d\n", end1 - begin1);
  printf("ShellSort:%d\n", end2 - begin2);
  printf("SelectSort:%d\n", end3 - begin3);
  printf("HeapSort:%d\n", end4 - begin4);
  printf("QuickSort:%d\n", end5 - begin5);
  printf("MergeSort:%d\n", end6 - begin6);
  printf("BubbleSort:%d\n", end7 - begin7);
 
 
  free(a1);
  free(a2);
  free(a3);
  free(a4);
  free(a5);
  free(a6);
  free(a7);
}

所有排序源代码：

Sort.h的内容：

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<stdbool.h>
#include<string.h>

void PrintArray(int* a, int n);

// 直接插入排序
void InsertSort(int* a, int n);

// 希尔排序
void ShellSort(int* a, int n);

// 直接选择排序
void SelectSort(int* a, int n);

// 堆排序
void AdjustDown(int* a, int n, int root);
void HeapSort(int* a, int n);

// 冒泡排序
void BubbleSort(int* a, int n);

//快速排序
int PartSort1(int* a, int left, int right);
int PartSort2(int* a, int left, int right);
int PartSort3(int* a, int left, int right);
void QuickSort(int* a, int begin, int end);

void QuickSortNonR(int* a, int begin, int end);

//归并排序
void MergeSort(int* a, int n);

void MergeSortNonR(int* a, int n);

Sort.c的内容：

#include"Sort.h"
#include"Stack.h"
void PrintArray(int* a, int n)
{
   int i = 0;
   for (i = 0; i < n; i++)
   {
       printf("%d ", a[i]);
   }
   printf("\n");
}

//直接插入排序
void InsertSort(int* a, int n)
{
   int i = 0;
   for (i = 1; i < n; i++)
   {
       int end = i - 1;
       int tmp = a[i];
       while (end >= 0)
       {
           //插入的数据比原来的数据小
           if (a[end] > tmp)
           {
               a[end + 1] = a[end];
               --end;
           }
           else
           {
               break;
           }
       }
       a[end + 1] = tmp;
   }
}

//希尔排序
void ShellSort(int* a, int n)
{
   //1.gap>1,预排序
   //2.gap==1,直接插入排序
   int gap = n;
   while (gap > 1)
   {
       gap = gap / 3 + 1;
       //+1可以保证最后一次一定是1
       for (int i = 0; i < n - gap; i++)
       {
           int end = i;
           int tmp = a[end + gap];
           while (end >= 0)
           {
               if (a[end] > tmp)
               {
                   a[end + gap] = a[end];
                   end = end - gap;
               }
               else
               {
                   break;
               }
           }
           a[end + gap] = tmp;
       }
   }
}

//冒泡排序
void BubbleSort(int* a, int n)
{
   for (int j = 0; j < n; j++)
   {
       bool exchange = false;
       for (int i = 1; i < n - j; i++)
       {
           if (a[i - 1] > a[i])
           {
               int tmp = a[i];
               a[i] = a[i - 1];
               a[i - 1] = tmp;
               exchange = true;
           }
       }
       if (exchange == false)
       {
           break;
       }
   }
}

void Swap(int* a1, int* a2)
{
   int tmp = *a1;
   *a1 = *a2;
   *a2 = tmp;
}

//直接选择排序
void SelectSort(int* a, int n)
{
   int begin = 0;
   int end = n - 1;
   while (begin < end)
   {
       int maxi = begin;
       int mini = begin;
       for (int i = begin; i <= end; i++)
       {
           if (a[i] > a[maxi])
           {
               maxi = i;
           }
           if (a[i] < a[mini])
           {
               mini = i;
           }
       }
       Swap(&a[begin], &a[mini]);
       //如果maxi和begin重叠，修正一下即可
       if (begin ==maxi)
       {
           maxi = mini;
       }
       Swap(&a[end], &a[maxi]);
       ++begin;
       --end;
   }
}

//向下调整算法
void AdjustDown(int* a, int n, int parent)
{
   //默认左孩子小
   int child = parent * 2 + 1;
   while (child < n)//孩子在数组范围内
   {
       //选出左右孩子中大的那一个
       //有可能假设错了
       //左孩子不存在，一定没有右孩子——完全二叉树
       //左孩子存在，有可能没有右孩子
       if (child + 1 < n && a[child + 1] > a[child])
           //    右孩子存在            右孩子>左孩子
           //不能这么写 if (a[child + 1] > a[chid] && child + 1 < n )
           //这样写会有越界的风险 因为是先访问了数组中的元素 再去比较右孩子是否存在
       {
           ++child;
       }
       //child就是大的那个孩子
       //不关心到底是左孩子还是右孩子
       if (a[child] > a[parent])
       {
           Swap(&a[child], &a[parent]);
           parent = child;
           child = parent * 2 + 1;//默认又算的是左孩子
       }
       else
       {
           break;
       }

   }
}
//堆排序
void HeapSort(int* a, int n)
{
   //建堆——向下调整建堆
   int i = 0;
   for (i = (n - 1 - 1) / 2; i >= 0; i--)
   {
       AdjustDown(a, n, i);
   }
   //升序——建大堆
   int end = n - 1;
   while (end > 0)
   {
       Swap(&a[0], &a[end]);
       AdjustDown(a, end, 0);
       --end;
   }
}

//三数取中
int GetMidIndex(int* a, int left, int right)
{
   int mid = (left + right) / 2;
   if (a[left] < a[mid])
   {
       if (a[mid] < a[right])
       {
           return mid;
       }
       else if (a[left] < a[right])
       {
           return right;
       }
       else
       {
           return left;
       }
   }
   else // a[left] > a[mid]
   {
       if (a[mid] > a[right])
       {
           return mid;
       }
       else if (a[left] > a[right])
       {
           return right;
       }
       else
       {
           return left;
       }
   }
}
// hoare
// [left, right]
int PartSort1(int* a, int left, int right)
{
   int midi = GetMidIndex(a, left, right);
   Swap(&a[left], &a[midi]);

   int keyi = left;
   while (left < right)
   {
       // 右边找小
       while (left < right && a[right] >= a[keyi])
       {
           --right;
       }

       // 左边找大
       while (left < right && a[left] <= a[keyi])
       {
           ++left;
       }

       Swap(&a[left], &a[right]);
   }

   Swap(&a[keyi], &a[left]);

   return left;
}

挖坑法
[left, right]
//int PartSort2(int* a, int left, int right)
//{
//    int midi = GetMidIndex(a, left, right);
//    Swap(&a[left], &a[midi]);
//
//    int key = a[left];
//    int hole = left;
//    while (left < right)
//    {
//        // 右边找小
//        while (left < right && a[right] >= key)
//        {
//            --right;
//        }
//
//        a[hole] = a[right];
//        hole = right;
//
//        // 左边找大
//        while (left < right && a[left] <= key)
//        {
//            ++left;
//        }
//
//        a[hole] = a[left];
//        hole = left;
//    }
//
//    a[hole] = key;
//
//    return hole;
//}
//
前后指针法
[left, right]
//int PartSort3(int* a, int left, int right)
//{
//    int midi = GetMidIndex(a, left, right);
//    Swap(&a[left], &a[midi]);
//
//    int prev = left;
//    int cur = left + 1;
//    int keyi = left;
//    while (cur <= right)
//    {
//        if (a[cur] < a[keyi] && ++prev != cur)
//        {
//            Swap(&a[prev], &a[cur]);
//        }
//
//        ++cur;
//    }
//
//    Swap(&a[prev], &a[keyi]);
//    keyi = prev;
//    return keyi;
//}
//快速排序
void QuickSort(int* a, int begin, int end)
{
   if (begin >= end)
   {
       return;
   }
   int keyi = PartSort1(a, begin, end);
   //[begin,keyi-1] keyi [keyi+1,end]
   QuickSort(a, begin, keyi - 1);
   QuickSort(a, keyi + 1, end);
}

//快速排序非递归
void QuickSortNonR(int* a, int begin, int end)
{
   Stack st;
   StackInit(&st);
   StackPush(&st, end);
   StackPush(&st, begin);

   while (!StackEmpty(&st))
   {
       int left = StackTop(&st);
       StackPop(&st);

       int right = StackTop(&st);
       StackPop(&st);

       int keyi = PartSort1(a, left, right);

       // [left, keyi-1] keyi [keyi+1, right]

       if (keyi + 1 < right)
       {
           StackPush(&st, right);
           StackPush(&st, keyi + 1);
       }

       if (left < keyi - 1)
       {
           StackPush(&st, keyi - 1);
           StackPush(&st, left);
       }
   }

   StackDestroy(&st);
}

void _MergeSort(int* a, int begin, int end, int* tmp)
{
   if (begin >= end)
   {
       return;
   }
   int mid = (begin + end) / 2;
   //[begin,mid] [mid+1,end]
   _MergeSort(a, begin, mid, tmp);
   _MergeSort(a, mid + 1, end, tmp);
   //归并两个区间
   int begin1 = begin;
   int begin2 = mid + 1;
   int end1 = mid;
   int end2 = end;
   int i = begin;
   while (begin1 <= end1 && begin2 <= end2)
   {
       if (a[begin1] < a[begin2])
       {
           tmp[i++] = a[begin1++];
       }
       else
       {
           tmp[i++] = a[begin2++];
       }
   }
   while (begin1 <= end1)
   {
       tmp[i++] = a[begin1++];
   }
   while (begin2 <= end2)
   {
       tmp[i++] = a[begin2++];
   }
   memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
//归并排序
void MergeSort(int* a, int n)
{
   int* tmp = (int*)malloc(sizeof(int) * n);
   if (tmp == NULL)
   {
       perror("malloc失败!!!");
       return;
   }
   _MergeSort(a, 0, n - 1, tmp);
   free(tmp);
}

//归并排序非递归
void MergeSortNonR(int* a, int n)
{
   int* tmp = (int*)malloc(sizeof(int) * n);

   // 1  2  4 ....
   int gap = 1;
   while (gap < n)
   {
       int j = 0;
       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;

           printf("修正前：[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);

           if (end1 >= n)
           {
               end1 = n - 1;

               // 不存在区间
               begin2 = n;
               end2 = n - 1;
           }
           else if (begin2 >= n)
           {
               // 不存在区间
               begin2 = n;
               end2 = n - 1;
           }
           else if(end2 >= n)
           {
               end2 = n - 1;
           }

           printf("修正后：[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);

           while (begin1 <= end1 && begin2 <= end2)
           {
               if (a[begin1] <= a[begin2])
               {
                   tmp[j++] = a[begin1++];
               }
               else
               {
                   tmp[j++] = a[begin2++];
               }
           }

           while (begin1 <= end1)
           {
               tmp[j++] = a[begin1++];
           }

           while (begin2 <= end2)
           {
               tmp[j++] = a[begin2++];
           }
       }
       printf("\n");

       memcpy(a, tmp, sizeof(int) * n);
       gap *= 2;
   }

   free(tmp);
}
//void MergeSortNonR(int* a, int n)
//{
//    int* tmp = (int*)malloc(sizeof(int) * n);
//    if (tmp == NULL)
//    {
//        perror("malloc失败!!!");
//        return;
//    }
//    // 1  2  4 ....
//    int gap = 1;
//    while (gap < n)
//    {
//        int j = 0;
//        for (int i = 0; i < n; i += 2 * gap)
//        {
//            // 每组的合并数据
//            int begin1 = i;
//            int end1 = i + gap - 1;
//            int begin2 = i + gap;
//            int end2 = i + 2 * gap - 1;
//
//            printf("[%d,%d][%d,%d]\n", begin1, end1, begin2, end2);
//
//            if (end1 >= n || begin2 >= n)
//            {
//                break;
//            }
//
//            // 修正
//            if (end2 >= n)
//            {
//                end2 = n - 1;
//            }
//
//            while (begin1 <= end1 && begin2 <= end2)
//            {
//                if (a[begin1] < a[begin2])
//                {
//                    tmp[j++] = a[begin1++];
//                }
//                else
//                {
//                    tmp[j++] = a[begin2++];
//                }
//            }
//
//            while (begin1 <= end1)
//            {
//                tmp[j++] = a[begin1++];
//            }
//
//            while (begin2 <= end2)
//            {
//                tmp[j++] = a[begin2++];
//            }
//
//            // 归并一组，拷贝一组
//            memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1));
//        }
//        printf("\n");
//        gap *= 2;
//    }
//    free(tmp);
//}

Leetcode每日一题——“912.排序数组”

在leetcode上面有一道题，可以用各种排序测试可不可以通过：

小雅兰在这边尝试了一下归并排序，很轻松就过啦！！！

void _MergeSort(int* a, int begin, int end, int* tmp)
{
  if (begin >= end)
  {
    return;
  }
  int mid = (begin + end) / 2;
  //[begin,mid] [mid+1,end]
  _MergeSort(a, begin, mid, tmp);
  _MergeSort(a, mid + 1, end, tmp);
  //归并两个区间
  int begin1 = begin;
  int begin2 = mid + 1;
  int end1 = mid;
  int end2 = end;
  int i = begin;
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (a[begin1] < a[begin2])
    {
      tmp[i++] = a[begin1++];
    }
    else
    {
      tmp[i++] = a[begin2++];
    }
  }
  while (begin1 <= end1)
  {
    tmp[i++] = a[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[i++] = a[begin2++];
  }
  memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
//归并排序
void MergeSort(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
    perror("malloc失败!!!");
    return;
  }
    
  _MergeSort(a, 0, n - 1, tmp);
  free(tmp);
}
int* sortArray(int* nums, int numsSize, int* returnSize){
  MergeSort(nums, numsSize);
  *returnSize = numsSize;
  return nums;
}

还可以这样写，是进行了小区间优化的版本，相对来说好一点，但leetcode上面测试不了此效果：

//直接插入排序
void InsertSort(int* a, int n)
{
  int i = 0;
  for (i = 1; i < n; i++)
  {
    int end = i - 1;
    int tmp = a[i];
    while (end >= 0)
    {
      //插入的数据比原来的数据小
      if (a[end] > tmp)
      {
        a[end + 1] = a[end];
        --end;
      }
      else
      {
        break;
      }
    }
    a[end + 1] = tmp;
  }
}
void _MergeSort(int* a, int begin, int end, int* tmp)
{
  if (begin >= end)
  {
    return;
  }
    //小区间优化
    if(end-begin+1<10)
    {
        InsertSort(a+begin,end-begin+1);
        return;
    }
  int mid = (begin + end) / 2;
  //[begin,mid] [mid+1,end]
  _MergeSort(a, begin, mid, tmp);
  _MergeSort(a, mid + 1, end, tmp);
  //归并两个区间
  int begin1 = begin;
  int begin2 = mid + 1;
  int end1 = mid;
  int end2 = end;
  int i = begin;
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (a[begin1] < a[begin2])
    {
      tmp[i++] = a[begin1++];
    }
    else
    {
      tmp[i++] = a[begin2++];
    }
  }
  while (begin1 <= end1)
  {
    tmp[i++] = a[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[i++] = a[begin2++];
  }
  memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1));
}
 
//归并排序
void MergeSort(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  if (tmp == NULL)
  {
    perror("malloc失败!!!");
    return;
  }
  _MergeSort(a, 0, n - 1, tmp);
  free(tmp);
}
int* sortArray(int* nums, int numsSize, int* returnSize){
  MergeSort(nums,numsSize);
  *returnSize = numsSize;
  return nums;
}

但是这道题，用直接插入排序、冒泡排序这种排序就过不了了，会提示：超出时间限制

遗憾的是：快速排序也没过，小雅兰反复测试了好多遍

好啦，小雅兰今天的归并排序的内容就到这里啦，还要继续加油！！！


文章标签：
人工智能
算法
搜索推荐
认真学习的小雅兰.
目录
相关文章
认真学习的小雅兰.
|
13天前
|
算法
快速排序——“数据结构与算法”
快速排序——“数据结构与算法”
认真学习的小雅兰.
16 0
游客yit5ffk3osumc
|
1月前
|
存储 算法 搜索推荐
【数据结构与算法】：选择排序与快速排序
欢迎来到排序的第二个部分：选择排序与快速排序！
游客yit5ffk3osumc
25 1
【数据结构与算法】：选择排序与快速排序
盒马盒马
|
3月前
|
算法
数据结构与算法：归并排序
数据结构与算法：归并排序
盒马盒马
42 7
盒马盒马
|
3月前
|
存储 算法 C语言
数据结构与算法：快速排序
数据结构与算法：快速排序
盒马盒马
29 1
nagiY
|
9月前
|
算法
【数据结构与算法】快速排序的三种实现方法
【数据结构与算法】快速排序的三种实现方法
nagiY
100 0
鹤冲天Pro
|
11月前
|
人工智能 算法 搜索推荐
数据结构与算法（七）：排序算法
数据结构与算法（七）：排序算法
鹤冲天Pro
71 0
游客mpbbpgnnu5sxe
|
搜索推荐 算法 测试技术
【数据结构与算法】排序算法总结（下）
【数据结构与算法】排序算法总结（下）
游客mpbbpgnnu5sxe
66 0
【数据结构与算法】排序算法总结（下）
游客mpbbpgnnu5sxe
|
搜索推荐 算法 C++
【数据结构与算法】排序算法总结（上）
【数据结构与算法】排序算法总结（上）
游客mpbbpgnnu5sxe
113 0
【数据结构与算法】排序算法总结（上）
Binaire-沐辰
|
搜索推荐 算法 Java
【数据结构与算法】——必知必会的排序算法你会几种
这篇文章主要介绍了常见的几种排序算法
Binaire-沐辰
120 0
【数据结构与算法】——必知必会的排序算法你会几种
mogqp3unktbnq
|
存储 算法
数据结构与算法-分治法
分治法： 把一片领土分解，分解为若干块小部分，然后一块块地占领征服，被分解的可以是不同的政治派别或是其他什么，然后让他们彼此异化。
mogqp3unktbnq
109 0

热门文章

最新文章

  • 1
    大咖云集，技术宅开趴倒计时 —— 2017 Kubernetes Meetup | 成都站
  • 2
    Centos7：“Entering emergency mode. Exit the shell to continue”错误解决方法
  • 3
    一分钟了解阿里云产品：解析不生效的原因诊断
  • 4
    DVWA-SQL注入(SQL Injection)低/中/高级别
  • 5
    教AI打星际2也不难，试试暴雪和DeepMind的工具包 | 附论文+代码
  • 6
    python入门学习之变量注释篇
  • 7
    Rainbow分页解决方案
  • 8
    Androids含文档erver结束（工具包 Httputils）两
  • 9
    GitHub最新命令使用教程
  • 10
    Android事件分发详解(二)——Touch事件传入到Activity的流程
  • 1
    Serverless 应用引擎产品使用之在阿里云函数计算中通过调用函数如何解决
    122
  • 2
    Serverless 应用引擎产品使用之在阿里函数计算中，使用签名认证调用HTTP触发器的步骤如何解决
    128
  • 3
    Serverless 应用引擎产品使用之在阿里函数计算中，设置单实例并发1如何解决
    125
  • 4
    Serverless 应用引擎产品使用之在阿里云函数计算中，需要处理的文件大于100MB如何解决
    116
  • 5
    Serverless 应用引擎产品使用之在阿里函数计算中开启函数计算 API 接口如何解决
    97
  • 6
    Python的进程锁，进程队列
    118
  • 7
    Serverless 应用引擎产品使用之在Serverless 应用引擎中跳过AHAS创建如何解决
    106
  • 8
    Python的进程，以及进程同步，守护进程详细解读
    132
  • 9
    Serverless 应用引擎产品使用之在 Serverless 应用引擎中，查看镜像文件中的 JAR 文件如何解决
    127
  • 10
    Python中的反射
    115

    • 相关电子书

    更多
  • 图解算法小抄
  • 低代码开发师（初级）实战教程
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考