[C++] 初夏小谈：排序算法---归并排序（非递归）

在进行归并排序时需要进行三步：①：针对两个有序子序列的合并
②：针对一趟所有子序列的合并
③：循环使得子序列越来越少最终全部合并完毕




针对第一个步骤①：当所有子序列的元素个数都是1时，那么每个子序列都是有序的。因此第一次就是两个元素（也是两个子序列）进行合并。
针对第二个步骤②：就是把所有子序列进行两两合并（注意：第一次就是把所有的元素两两合并）
针对第三个步骤③：由于是二路归并所以每一趟合并的子序列就是上一次长度的二倍。所以此次循环O(logn)次

#pragma once
#include<ctime>
#include<malloc.h>
#include<iostream>
using namespace std;
//将两个有序子序列合并
void merge(int arr[], int small, int mid, int big);
//进行一趟子序列的全排序
void OneMerge(int arr[], int length, int size);
//进行归并排序
void MergeSort(int arr[], int size);
//打印
void PrintMergeSort(int array[], int size);

#include"MergeSort.h"
//将两个有序子序列合并
void merge(int arr[], int small, int mid, int big)
{
  //创建一个临时数组来存储排序后的子序列
  int* ptr = (int*)malloc(sizeof(int)*(big - small + 1));
  int i = small;//0
  int j = mid + 1;//2
  int k = 0;
  while (i <= mid && j <= big)
  {
  if (arr[i] <= arr[j])
  {
    ptr[k++] = arr[i++];
  }
  else
  {
    ptr[k++] = arr[j++];
  }
  }
  while (i <= mid)
  {
  ptr[k++] = arr[i++];
  }
  while (j <= big)
  {
  ptr[k++] = arr[j++];
  }
  for (i = small, k = 0; i <= big; k++, i++)
  {
  arr[i] = ptr[k];
  }
  free(ptr);
  ptr = nullptr;
}
//进行一趟子序列的全排序
void OneMerge(int arr[], int length, int size)
{
  int i;
  for (i = 0; i + 2 * length - 1 < size; i = i + 2 * length)
  {
  merge(arr, i, i + length - 1, i + 2 * length - 1);
  }
  if (i + length - 1 < size)
  {
  merge(arr, i, i + length - 1, size - 1);
  }
}
//进行归并排序
void MergeSort(int arr[], int size)
{
  for (int i = 1; i <= size; i *= 2)
  {
  OneMerge(arr, i, size);
  }
}
//打印
void PrintMergeSort(int array[], int size)
{
  int i = 0;
  while (i < size)
  {
  cout << array[i++] << " ";
  }
  cout << endl;
}

#include"MergeSort.h"
#define ARRA_YSIZE 100
int main()
{
  srand((unsigned int)time(NULL));
  int array[ARRA_YSIZE];
  for (int i = 0; i < ARRA_YSIZE; i++)
  {
    array[i] = rand() % 100;
  }
  int size = sizeof(array) / sizeof(array[0]);
  cout << "未排序：";
  PrintMergeSort(array, size);
  MergeSort(array, size);
  cout << "归并排序：";
  PrintMergeSort(array, size);
  system("pause");
  return 0;
}

①：归并排序的不足在于它需要借助O(N)的空间复杂度。归并排序可以解决当数据达到无法全部加载进内存的数据的排序。
②：时间复杂度O(nlogn)
③：空间复杂度O(n) --->需要借助空间来存放合并的子序列
④：归并排序是一种稳定的排序算法