追梦之旅【数据结构篇】——基于C语言实现快排和归并排序代码

#include<stdio.h>
void Swap(int* p1, int* p2)
{
  int tem = *p1;
  *p1 = *p2;
  *p2 = tem;
}
int GetMid(int* a, int begin, int end)
{
  int mid = (begin + end) / 2;
  if (a[begin] > a[mid])
  {
    if (a[mid] > a[end])
    {
      return mid;
    }
    else if (a[begin] > a[end])
    {
      return end;
    }
    else
    {
      return begin;
    }
  }
  else
  {
    if (a[mid] < a[end])
    {
      return mid;
    }
    else if (a[begin] < a[end])
    {
      return end;
    }
    else
    {
      return begin;
    }
  }
}
int _QuickSort(int* a, int begin, int end)
{
  int prev = begin;
  int cur = begin + 1;
  int keyi = begin;
  int mid = GetMid(a, begin, end);
  Swap(&(a[keyi]), &(a[mid]));
  while (cur <= end)
  {
    if (a[cur] < a[keyi] && ++prev != cur)
      Swap(&(a[cur]), &(a[prev]));
    cur++;
  }
  Swap(&(a[keyi]), &(a[prev]));
  keyi = prev;
  return keyi;
}
void QuickSort(int* a, int begin, int end)
{
  int left = begin;
  int right = end;
  if (left >= right)
    return;
  int keyi = _QuickSort(a, begin, end);
  QuickSort(a, begin, keyi - 1);
  QuickSort(a, keyi + 1, end);
}
int main()
{
  int a[] = { 1,3,4,5,36,7,8,9,0,22 };
  int len = sizeof(a) / sizeof(int);
  QuickSort(a, 0, len - 1);
  for (int i = 0; i < len; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

#include<stdio.h>
#include<assert.h>
#include<string.h>
#include<stdlib.h>
void _MergeSort(int* a, int begin, int end, int* tem)
{
  if (begin >= end)
    return;
  //划分区间 begin  mid mid + 1 end
  int mid = (begin + end) / 2;
  _MergeSort(a, begin, mid, tem);
  _MergeSort(a, mid + 1, end, tem);
  int begin1 = begin;
  int end1 = mid;
  int begin2 = mid + 1;
  int end2 = end;
  int i = begin1;
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (a[begin1] < a[begin2])
    {
      tem[i++] = a[begin1++];
    }
    else
    {
      tem[i++] = a[begin2++];
    }
  }
  while (begin1 <= end1)
  {
    tem[i++] = a[begin1++];
  }
  while (begin2 <= end2)
  {
    tem[i++] = a[begin2++];
  }
  //后序遍历二叉树的思路，进行归并。
  memcpy(a + begin, tem + begin, sizeof(int) * (end - begin + 1));
}
void MergeSort(int* a, int len)
{
  assert(a);
  int* tem = (int*)malloc(sizeof(int) * len);
  if (tem == NULL)
  {
    perror("malloc");
    exit(-1);
  }
  _MergeSort(a, 0, len - 1, tem);
}
void PintArray(int* a, int len)
{
  int i = 0;
  for (i = 0; i < len; i++)
  {
    printf("%d ", a[i]);
  }
}
int main()
{
  int a[] = { 1,3,4,5,36,7,8,9,0,22 };
  int len = sizeof(a) / sizeof(int);
  MergeSort(a, len);
  PintArray(a, len);
  return 0;
}