数据结构排序——计数排序和排序总结（附上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;
}