数据结构排序——计数排序和排序总结（附上912. 排序数组讲解）

void CountSort(int* a, int n)
{
  //先找最大最小，确定范围
  int max = a[0], min = a[0];
  for (int i = 1; i < n; i++)
  {
    if (a[i] > max)
    {
      max = a[i];
    }
    if (a[i] < min)
    {
      min = a[i];
    }
  }
  int range = max - min + 1;
  int* count= (int*)calloc(sizeof(int) * range);
  if (count == NULL)
  {
    perror("malloc fail");
    return;
  }
  //开始想count中累加了
  for (int i = 0; i < n; i++)
  {
    count[a[i] - min]++;
  }
  //赋值覆盖
  int a_index = 0;
  for (int i = 0; i < range; i++)
  {
    for (int j = 0; j < count[i]; j++)
    {
      a[a_index] = i + min;
      a_index++;
    }
  }
}
int main()
{
  int a[] = { 2,4,1,7,9 };
  CountSort(a, 5);
  for (int i = 0; i < 5; i++)
  {
    printf("%d ", a[i]);
  }
  return 0;
}

void Swap(int* x, int* y)
{
  int tmp = *x;
  *x = *y;
  *y = tmp;
}
int GetMid(int* a,int left, int right)//找中间的
{
  // a[left]      a[mid]           a[right]
  int mid = left+(rand()%(right-left));
  if (a[left] < a[mid])
  {
    if (a[mid] < a[right])
    {
      return mid;
    }
    else if (a[left] > a[right])  // mid是最大值
    {
      return left;
    }
    else
    {
      return right;
    }
  }
  else // a[left] > a[mid]
  {
    if (a[left] < a[right])
    {
      return left;
    }
    else if (a[mid] < a[right])
    {
      return right;
    }
    else
    {
      return mid;
    }
  }
}
void QuickSort(int* a, int left, int right)
{
  if (left >= right)
  {
    return;
  }
  int begin = left;
  int end = right;
  int mid = GetMid(a, left, right);
  Swap(&a[mid], &a[left]);
  int cur = left + 1;
  int key = a[left];//储存一下，后面比较来用，用a[left]会被替代
  while (cur <= right)
  {
    if (a[cur] < key)
    {
      Swap(&a[cur], &a[left]);
      cur++;
      left++;
    }
    else if (a[cur] == key)
    {
      cur++;
    }
    else
    {
      Swap(&a[cur], &a[right]);
      right--;
    }
  }
  QuickSort(a, begin, left - 1);
  QuickSort(a, right + 1, end);
}
int* sortArray(int* nums, int numsSize, int* returnSize) {
    srand(time(0));
    QuickSort(nums,0,numsSize-1);
    *returnSize=numsSize;
    return nums;
}