【初阶数据结构】深度解析七大常见排序|掌握底层逻辑与原理（三）

void PartSort2(int* a, int left, int right)
{
  if (left >= right)
  {
    return;
  }
  int midi = GetMidi(a, left, right);//将首位大小取为不大也不小的数
  Swap(&a[midi], &a[left]);
  int keyi = a[left];
    
  int hole = left;
  int begin = left;
  int end = right;
  while (right > left)
  {
    while (a[right] >= keyi && right > left)//找小
    {
      right--;
    }
    a[hole] = a[right];//移数值
    hole = right;
    while (a[left] <= keyi && right > left)//找大
    {
      left++;
    }
    a[hole] = a[left];
    hole = left;
  }
  a[hole] = keyi;
  PartSort1(a, begin, hole - 1);
  PartSort1(a, hole + 1, end);
}

void PartSort3(int* a, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
    
    //编译器优化很厉害，可以不使用 
  if (end - begin + 1 <= 10)//小区间优化
  {
    InsertSort(a + begin, end - begin + 1);
  }
    
  int midi = GetMidi(a, begin, end);//将第一个元素大小取为不大也不小的数
  Swap(&a[midi], &a[begin]);
    
  int keyi = begin;
  int prev = begin;
  int cur = prev + 1;
    
  while (cur <= end)//等于也是要换的
  {
    if (a[cur] < a[keyi] && ++prev != cur)
    {
      //避免无效交换
      Swap(&a[prev], &a[cur]);
    }
      cur++;
  }
    
  Swap(&a[prev], &a[keyi]);
  keyi = prev;
  PartSort1(a, begin, keyi - 1);
  PartSort1(a, keyi + 1, end);
  return 0;
}

void MergeSort(int *a,int n) 
{
    int *tmp=(int *)malloc(sizeof(int)*n);
    if(tmp==NULL)
    {
        perror("malloc fail!");
        return 1;
    }
    _MergeSort(a,0,n-1,tmp);
    free(tmp)
        tmp=NULL;
}
void _MergeSort(int* a, int begin, int end, int* tmp)
{
  if (begin >= end)
  {
    return;
  }
  int mid = (begin + end) / 2;
  //[begin,mid][mid+1,end]
  _MergeSort(a, begin, mid, tmp);
  _MergeSort(a, mid + 1, end, tmp);//后序递归
  //左边有序 右边有效 合在一起-->合并有序数组问题
  int begin1 = begin;
  int begin2 =  1+ mid;
    
  int end1 = mid;
  int end2 = end;
    
  int i =begin;
  while (begin1 <= end1 && begin2 <= end2)
  {
    if (a[begin1] < a[begin2])
    {
      tmp[i++] = a[begin1++];
    }
    else
    {
      tmp[i++] = a[begin2++];
    }
  }//还有部分数据没有放入新数组中
  while (begin1 <= end1)
  {
    tmp[i++] = a[begin1++];
  }
  while (begin2 <= end2)
  {
    tmp[i++] = a[begin2++];
  }
  memcpy(a+begin, tmp+begin, sizeof(int) * (end - begin + 1));//可能是右边归并
}

void CountSort(int* a, int n)
{
  int min = a[0], max = a[0];
  for (int i = 1; i < n; i++)
  {
    if (a[i] < min)
      min = a[i];
    if (a[i] > max)
      max = a[i];
  }
  int range = max - min + 1;
  int* count = (int*)calloc(range, sizeof(int));
  if (count == NULL)
  {
    printf("calloc fail\n");
    return;
  }
  // 统计次数
  for (int i = 0; i < n; i++)
  {
    count[a[i] - min]++;
  }
    
  // 排序
  int i = 0;
  for (int j = 0; j < range; j++)
  {
    while (count[j]--)
    {
      a[i++] = j + min;//加回去
    }
  }
}