归并排序 实现 要点 代码 注释 内存优化

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了归并排序 实现 要点 代码 注释 内存优化，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1912字，纯文字阅读大概需要3分钟。

内容图文

要点

• 分治，把数组二分成2部分，分别对这两部分排序，合并这两部分
• 合并函数借助新的内存空间

内存优化

• 合并函数不借助新的内存，使用插入排序完成合并

    /*
    使用插入排序优化合并方法
    不用创建新的数组，减少内存使用
     */
    public void Merge2(int[] array, int from, int mid, int to)
    {
      for (var i = mid + 1; i <= to; i++)
      {
        var temp = array[i];
        for (var j = i - 1; j >= from; j--)
        {
          if (temp < array[j])
          {
            array[j + 1] = array[j];
            array[j] = temp;
          }
          else
          {
            break;
          }
        }
      }
    }

实现

namespace DataStructure
{

/*
归并排序，分治、排序、合并
 */
  public class MergeSort
  {

    public int[] Sort(int[] array)
    {
      return Sort(array, 0, array.Length - 1);
    }

    //include from and to
    public int[] Sort(int[] array, int from, int to)
    {
      if (from < to)
      {
        var mid = (from + to) / 2;
        Sort(array, from, mid);
        Sort(array, mid + 1, to);
        Merge2(array, from, mid, to);
      }
      return array;
    }

    public void Merge(int[] array, int from, int mid, int to)
    {
      var tempArray = new int[to - from + 1];
      var indexA = from;
      var indexB = mid + 1;
      var indexTemp = 0;

      while (indexA <= mid && indexB <= to)
      {
        if (array[indexA] < array[indexB])
        {
          tempArray[indexTemp] = array[indexA];
          indexA++;
        }
        else
        {
          tempArray[indexTemp] = array[indexB];
          indexB++;
        }
        indexTemp++;
      }

      while (indexA <= mid)
      {
        tempArray[indexTemp] = array[indexA];
        indexTemp++;
        indexA++;
      }

      while (indexB <= to)
      {
        tempArray[indexTemp] = array[indexB];
        indexTemp++;
        indexB++;
      }

      for (var i = from; i <= to; i++)
      {
        array[i] = tempArray[i - from];
      }
    }

    /*
    使用插入排序优化合并方法
    不用创建新的数组，减少内存使用
     */
    public void Merge2(int[] array, int from, int mid, int to)
    {
      for (var i = mid + 1; i <= to; i++)
      {
        var temp = array[i];
        for (var j = i - 1; j >= from; j--)
        {
          if (temp < array[j])
          {
            array[j + 1] = array[j];
            array[j] = temp;
          }
          else
          {
            break;
          }
        }
      }
    }

    public void TestMerge()
    {
      var array = new int[] { 3, 4, 9, 1, 2, 7 };
      Merge(array, 0, 2, array.Length - 1);
      BaseSolution.printArray(array);
    }

    public void TestMerge2()
    {
      var array = new int[] { 3, 4, 9, 1, 2, 7 };
      Merge2(array, 0, 2, array.Length - 1);
      BaseSolution.printArray(array);
    }

  }

}

内容总结

以上是互联网集市为您收集整理的归并排序 实现 要点 代码 注释 内存优化全部内容，希望文章能够帮你解决归并排序 实现 要点 代码 注释 内存优化所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---