顺序表-00016-旋转顺序表

/**
* @brief 功能：数组arr元素个数为n，整体向后移动k(非负数)个位置 \n
* @note 取出arr[n-1]处元素，对[0,n-1]处元素逐个右移，循环k次
*/
void xxx_rotate_01(int arr[], int n, int k)
{
	if (arr == NULL || n < 1 || k < 1)
	{
		return;
	}
	k = k % n;
	// 将表尾元素取出tmp,然后将所有元素依次向后移动1个位置
	// 再将取出的表尾元素放置表首元素位置。
	// 此为整体元素完成1次移动。重复上述操作，总共循环k次，即可
	for (int j = 0; j < k; ++j)
	{
		int tmp = arr[n - 1];
		for (int i = n - 1; i > 0; --i)
		{
			arr[i] = arr[i - 1];
		}
		arr[0] = tmp;
	}

}

/**
* @brief 功能：方法2 \n
* @note 将原数组的[0,n-k-1]的元素拷贝至新数组的[n-k,n-1]处
* @note 将原数组的[n-k,n-1]的元素拷贝至新数组的[0,n-k-1]处
* @note 再将处理完成的新数组元素拷贝至原数组
*/
void xxx_rotate_02(int arr[], int n, int k)
{
	{
		if (arr == NULL || k < 0)
		{
			return;
		}
		k = k % n;
		int* p = (int*)calloc(sizeof(int), n);
		if (p == NULL)
		{
			return;
		}
		for (int i = 0; i < k; ++i)
		{
			p[i] = arr[i + n - k];
		}
		for (int i = 0; i < n - k; ++i)
		{
			p[i + k] = arr[i];
		}
		for (int i = 0; i < n; i++)
		{
			arr[i] = p[i];
		}
		free(p);
		p = NULL;
	}
}

/**
* @brief 功能：方法3 \n
* @note 先将数组逆置,逆置后的[0,k-1]和[k,n-1]部分分别逆转
*/
void xxx_reverse(int arr[], int left, int right)
{
	if (arr == NULL)
	{
		return;
	}
	int tmp = 0;
	while (left < right)
	{
		tmp = arr[left];
		arr[left] = arr[right];
		arr[right] = tmp;
		left++;
		right--;
	}
}
void xxx_rotate_03(int arr[], int n, int k)
{
	if (arr == NULL || k < 0)
	{
		return;
	}
	k = k % n;
	xxx_reverse(arr, 0, n - 1);
	xxx_reverse(arr, 0, k - 1);
	xxx_reverse(arr, k, n - 1);
}