int PartSort3(int* a, int left, int right)
{
  int prev = left;//前指针
  int keyi = left;
  int cur = prev + 1;//后指针
  while (cur <= right)
  {
  if (a[cur] < a[keyi] && a[++prev] != a[cur])//在这里prev++是因为后续的交换是需要prev的后一位
    Swap(&a[prev], &a[cur]);
  cur++;
  }
  Swap(&a[keyi], &a[prev]);
  return prev;
}

int GetMidIndex(int* a, int left, int right)
{//来得到一个值及不是最大值也不是最小值并返回
  int mid = left + (right - left) / 2;
  if (a[left] < a[mid])
  {
  if (a[mid] < a[right])
  {
    return mid;
  }
  else if (a[left] > a[right])
  {
    return left;
  }
  else
  {
    return right;
  }
  }
  else 
  {
  if (a[mid] > a[right])
  {
    return mid;
  }
  else if (a[left] < a[right])
  {
    return left;
  }
  else
  {
    return right;
  }
  }
}
int PartSort3(int* a, int left, int right)
{
    int midi = GetMidIndex(a, left, right);//得到中间值
  Swap(&a[midi], &a[left]);//让中间值与基准值交换,这样基准值就不是最大的也不是最小值了.
  int prev = left;//前指针
  int keyi = left;
  int cur = prev + 1;//后指针
  while (cur <= right)
  {
  if (a[cur] < a[keyi])
  {
    prev++;
    Swap(&a[prev], &a[cur]);
  }
  cur++;
  }
  Swap(&a[keyi], &a[prev]);
  return prev;
}
void QuickSort(int* a, int left, int right)
{
  if (left > right)
  {
  return;
  }
  // 小区间直接插入排序控制有序
  if (right - left + 1  <= 30)
  {
  InsertSort(a + left, right - left + 1);
  }
  else
  {
  int keyi = PartSort3(a, left, right);
  QuickSort(a, left, keyi - 1);
  QuickSort(a, keyi + 1, right);
  }
}

void QuickSortNonR(int* a, int left, int right)
{
  //通过栈来模拟实现我们的递归得到的区间,从而实现非递归.
  ST st;
  StackInit(&st);
  StackPush(&st, left);
  StackPush(&st, right);
  while (!StackEmpty(&st))
  {
  int end = StackTop(&st);//根据上面的入栈顺序来决定这里和下面的变量以及出栈顺序.
  StackPop(&st);
  int begin = StackTop(&st);
  StackPop(&st);
  int keyi = PartSort1(a, begin, end);
  if (begin < keyi - 1)//左半区间.
  {
    StackPush(&st, begin);//这个和下面那个if条件句里的顺序都不能乱.
    StackPush(&st, keyi - 1);
  }
  if (keyi + 1 < end)//右半区间.
  {
    StackPush(&st, keyi + 1);
    StackPush(&st, end);
  }
  }
  StackDestroy(&st);
}

//这个是子函数,整体思路请向下翻阅找到父函数.
void _MergeSort(int* a, int begin, int end, int* tmp)
{
  if (begin >= end)
  return;
  int mid = (begin + end) / 2;
  _MergeSort(a, begin, mid, tmp);
    //经历了上面的函数递归后前一个区间就只有两个数值了
  _MergeSort(a, mid + 1, end, tmp);
    //经历了上面两个函数的归并能保证下面的区间第一次只有两个值,再分成两部分就各自有序了(单个数字被看做有序)
  int begin1 = begin, end1 = mid;//将一个区间分为两个
  int begin2 = mid + 1, end2 = end;//同上
  int index = begin;//因为递归带来的头是不一样的所以用begin作为tmp内容的头部
    //下面开始归并
  while (begin1 <= end1 && begin2 <= end2)
  {
  if (a[begin1] < a[begin2])//用a内数值进行比较是因为
  {
    tmp[index] = a[begin1];
    begin1++;
    index++;
  }
  else
  {
    tmp[index] = a[begin2];
    begin2++;
    index++;
  }
  }
  while (begin2 <= end2)//将未归并完的数值传递过去
  tmp[index++] = a[begin2++];
  while (begin1 <= end1)//同上
  tmp[index++] = a[begin1++];
    //将tmp里的排好序的区间传递到a内,所以a内也会因为这个而部分有序
  memcpy(a + begin, tmp + begin, (end - begin + 1) * sizeof(int));
}
void MergeSort(int* a, int n)
{
    //大致思路:通过合并时会将两个有序数组合并成一个有序的数组来进行排序.
    //整体思路:通过递归将数组分为一个个的小区间(一个数字为有序),再通过一个个小区间合并为一个一个个较大的区     //间最后使整个区间有序即可.
  int* tmp = (int*)malloc(sizeof(int) * n);//为了防止原数组的值被覆盖而建立的临时变量
  assert(tmp);
  _MergeSort(a, 0, n - 1, tmp);//我们需要递归解决,建立一个子函数
  free(tmp);
}

void MergeSortNonR(int* a, int n)
{
  int* tmp = (int*)malloc(sizeof(int) * n);
  assert(tmp);
  int gap = 1;//用来控制区间空间
  while (gap < n)
  {
  for (int k = 0; k < n; k += 2 * gap)
  {
    int begin1 = k;
    int end1 = begin1 + gap - 1;
    int begin2 = k + gap;
    int end2 = begin2 + gap - 1;
    int index = begin1;
    if (end1 >= n)
    {
    end1 = n - 1;
    }
    if (begin2 >= n)//如果begin2越界了就使区间不存在
    {
    begin2 = end2 + 1;
    }
    if (end2 >= n)
    {
    end2 = n - 1;
    }
    //归并
    while (begin1 <= end1 && begin2 <= end2)//有一个序列为空就停止
    {
    if (a[begin1] < a[begin2])
    {
      tmp[index++] = a[begin1++];
    }
    else
    {
      tmp[index++] = a[begin2++];
    }
    }
    //将剩余数据放入tmp数组
    while (begin1 <= end1)
    {
    tmp[index++] = a[begin1++];
    }
    while (begin2 <= end2)
    {
    tmp[index++] = a[begin2++];
    }
  }
  memcpy(a, tmp, sizeof(int) * n);
  gap *= 2;
  }
  free(tmp);
}

void CountSort(int* a, int n)
{
  //下面得到我们的最大值和最小值
  int max = a[0], min = a[0];
  for (int i = 0; i < n; ++i)
  {
  if (a[i] > max)
    max = a[i];
  if (a[i] < min)
    min = a[i];
  }
  //找到数据的范围
  int range = max - min + 1;
  int* countArray = (int*)malloc(range * sizeof(int));
  assert(countArray);
  memset(countArray, 0, sizeof(int) * range);//初始化为0也可使用calloc函数
  //存放在相对位置，可以节省空间
  for (int i = 0; i < n; ++i)
  {
  countArray[a[i] - min]++;
  }
  //可能存在重复的数据，有几个存几个
  int index = 0;
  for (int i = 0; i < range; ++i)
  {
  while (countArray[i]--)
  {
    a[index++] = i + min;
  }
  }
}