驱动调度-采用电梯调度算法排列出磁盘请求响应次序

题目描述：要求输入一个柱面访问请求序列以及当前磁头所在柱面号和移动方向，输出采用电梯调度算法时移动臂响应的柱面访问序列

输入格式： 程序要求输入3行，以回车符号作为分隔第1行是2个整数n、m，之间用空格隔开，n表示当前磁头所在的柱面号；m表示第二行输入m个数第2行是m个整数，数之间以空格作为分隔，表示柱面访问请求序列第3行是数字 -1 或 1，当为 -1 时表示移动臂向柱面号减小方向移动，当为 1 时表示移动臂向柱面号增大方向移动

输出格式： 输出m个整数，数之间以空格作为分隔，采用电梯调度算法时移动臂响应的柱面访问序列。

设计思路

将要访问的柱面号排好序；
找到当前磁头所在的柱面号在序列中的位置；
以这个位置为基准，对前半部分和后半部分的柱面号依照磁头访问的方向重新排序。

代码部分

排序算法

使用快速排序

int sort(int A[], int k, int m, int d)		
//A是待排序列；k是开始索引；
//m是结束索引；d表示正序(1)还是倒序(-1)
{
	int i, a;
	i = k;
	a = d * A[k];
	for (int j = k + 1; j <= m; j++)
	{
		if (d * A[j] <= a)
		{
			i++;
			if (i != j)
			{
				int tmp;
				tmp = A[i];
				A[i] = A[j];
				A[j] = tmp;
			}
		}
	}
	int tmp;
	tmp = A[k];
	A[k] = A[i];
	A[i] = tmp;
	return i;
}

void quick_sort(int A[], int k, int m, int d)
{
	if (k < m)
	{
		int i;
		i = sort(A, k, m, d);
		quick_sort(A, k, i - 1, d);
		quick_sort(A, i + 1, m, d);
	}
}

SCAN算法

void SCAN(int n, int m, int A[], int d)	
//n表示当前磁头所在的柱面号；m表示第二行输入m个数
//A是访问序列；d是访问方向
{
	quick_sort(A, 0, m - 1, -d);
	int i;
	for (i = 0; -d*A[i] < -d*n; i++);
	quick_sort(A, 0, i-1, d);
}

当d为-1时，要求移动臂向柱面号减小的方向移动，因此先将序列升序排列，再将前半部分（比n小的数按照降序排序）。反之，当d为1时，先将序列降序排列，再将前半部分（比n大的数按照升序排序）。

主程序部分

int main()
{	
	int n, m;
	scanf_s("%d %d", &n, &m);
	int *A;
	A = (int*)malloc(sizeof(int) * m);
	for (int i = 0; i < m; i++)
		scanf_s("%d", &A[i]);
	printf("\n");
	int d;
	scanf_s("%d", &d);
	SCAN(n, m, A, d);
	for (int i = 0; i < m; i++)
		printf("%d ", A[i]);
	return 0;
}

测试样例

样例1：

输入：

15 10
24 38 2 110 43 36 5 11 6 180  
-1

输出：

11 6 5 2 24 36 38 43 110 180

样例2：