归并排序-C++

[hubvue]

归并排序C++版

#include <iostream>

using namespace std;

void merge_sort(int *arr, int len);
void merge(int *arr, int *L, int leftLen, int *R, int rightLen);
// 主函数
int main()
{
  int arr[10] = {9, 8, 7, 6, 5, 4, 3, 2, 1, 0};
  int len = sizeof(arr) / sizeof(int);
  merge_sort(arr, len);
  for (int i = 0; i < len; i++)
  {
    cout << arr[i] << " ";
  }
  cout << endl;
  return 0;
}
// 归并排序
void merge_sort(int *arr, int len)
{
  if (len < 2)
  {
    return;
  }
  int mid = len / 2;
  int *L = new int[mid];
  int *R = new int[len - mid];
  for (int i = 0; i < mid; i++)
  {
    L[i] = arr[i];
  }
  for (int i = mid; i < len; i++)
  {
    R[i - mid] = arr[i];
  }
  merge_sort(L, mid);
  merge_sort(R, len - mid);
  merge(arr, L, mid, R, len - mid);
}

void merge(int *arr, int *L, int leftLen, int *R, int rightLen)
{
  int i = 0, j = 0, k = 0;
  while (i < leftLen && j < rightLen)
  {
    if (L[i] < R[j])
    {
      arr[k++] = L[i++];
    }
    else
    {
      arr[k++] = R[j++];
    }
  }
  while (i < leftLen)
  {
    arr[k++] = L[i++];
  }
  while (j < rightLen)
  {
    arr[k++] = R[j++];
  }
}