数据结构

使用快速排序算法（升序）完善此程序。（注：截图为快速排序一趟后的结果，详见源代码）。请在/******start******/和/******end******/之间添加代码。

分数: 70

请勿频繁操作

#include <stdio.h>
#define N 10

void input(int a[], int n);
void output(int a[], int n);
int sort(int a[], int low, int high);
void quicksort(int a[], int low, int high);

int main(void)
{
	int a[N];
	input(a, N);
	quicksort(a, 0, N);
	output(a, N);
	return 0;
}

void input(int a[], int n)
{
	int i;
	printf("Input:\n");
	for (i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
}

void output(int a[], int n)
{
	int i;
	printf("Output:\n");
	for (i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void quicksort(int a[], int low, int high)
{
	int pivotloc;		/*枢轴下标*/
	
	/*注：该排序算法跑一趟。如果将下面3行注释取消，即为完全排序算法*/
	//if (low < high)
	{
		pivotloc = sort(a, low, high);
		//quicksort(a, low, pivotloc - 1);		/*递归将前半部分元素继续快速排序*/
		//quicksort(a, pivotloc + 1, high);
	}
}

int sort(int a[], int low, int high)
{
	int pivotkey; 

	pivotkey = a[low];
	/******start******/
	
	/******end******/ 
}

#include <stdio.h>
#define N 10

void input(int a[], int n);
void output(int a[], int n);
int sort(int a[], int low, int high);
void quicksort(int a[], int low, int high);

int main(void)
{
	int a[N];
	input(a, N);
	quicksort(a, 0, N);
	output(a, N);
	return 0;
}

void input(int a[], int n)
{
	int i;
	printf("Input:\n");
	for (i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
}

void output(int a[], int n)
{
	int i;
	printf("Output:\n");
	for (i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void quicksort(int a[], int low, int high)
{
	int pivotloc;		/*枢轴下标*/
	
	/*注：该排序算法跑一趟。如果将下面3行注释取消，即为完全排序算法*/
	//if (low < high)
	{
		pivotloc = sort(a, low, high);
		//quicksort(a, low, pivotloc - 1);		/*递归将前半部分元素继续快速排序*/
		//quicksort(a, pivotloc + 1, high);
	}
}

int sort(int a[], int low, int high)
{
	int pivotkey; 

	pivotkey = a[low];
	/******start******/
	int i = low, j = high;
    while (i < j)
    {
        while (i < j && a[j] >= pivotkey)
        {
            j--;
        }
        a[i] = a[j];
        while (i < j && a[i] <= pivotkey)
        {
            i++;
        }
        a[j] = a[i];
    }
    a[i] = pivotkey;
    return i;
	/******end******/ 
}

使用堆排序算法（升序，建大堆顶）完善此程序。（注：截图为堆排序初始化后的大堆顶结果，详见源代码）

分数: 50

请勿频繁操作

#include <stdio.h>
#define N 10

void input(int a[], int n);
void output(int a[], int n);
void sort(int a[], int n);
void heapadjust(int a[], int loc, int n);

int main(void)
{
	int a[N];
	input(a, N);
	sort(a, N);
	output(a, N);
	return 0;
}

void input(int a[], int n)
{
	int i;
	printf("Input:\n");
	for (i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
}

void output(int a[], int n)
{
	int i;
	printf("Output:\n");
	for (i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void sort(int a[], int n)
{
	int i;
	//int temp; 
	
	//将原始序列初始化为大堆顶 
	for (i = (n-1)/2; i >= 0; i--)
	{
		heapadjust(a, i, n-1); 
	} 
	/* 
	//本段程序是交换第一个和当前最后一个，然后再调整为堆，取消注释则是完整排序算法
	for (i = n - 1; i >= 1; i--)
	{
	temp = a[0];
	a[0] = a[i];
	a[i] = temp;
	heapadjust(a, 0, i-1); 
	} 
	*/ 
}

void heapadjust(int a[], int loc, int n)
{
	/******start******/
	
	/******end******/
}

#include <stdio.h>
#define N 10

void input(int a[], int n);
void output(int a[], int n);
void sort(int a[], int n);
void heapadjust(int a[], int loc, int n);

int main(void)
{
	int a[N];
	input(a, N);
	sort(a, N);
	output(a, N);
	return 0;
}

void input(int a[], int n)
{
	int i;
	printf("Input:\n");
	for (i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
	}
}

void output(int a[], int n)
{
	int i;
	printf("Output:\n");
	for (i = 0; i < n; i++)
	{
		printf("%d ", a[i]);
	}
	printf("\n");
}

void sort(int a[], int n)
{
	int i;
	//int temp; 
	
	//将原始序列初始化为大堆顶 
	for (i = (n-1)/2; i >= 0; i--)
	{
		heapadjust(a, i, n-1); 
	} 
	/* 
	//本段程序是交换第一个和当前最后一个，然后再调整为堆，取消注释则是完整排序算法
	for (i = n - 1; i >= 1; i--)
	{
	temp = a[0];
	a[0] = a[i];
	a[i] = temp;
	heapadjust(a, 0, i-1); 
	} 
	*/ 
}

void heapadjust(int a[], int loc, int n)
{
	/******start******/
    int temp = a[loc];
    int child = 2*loc+1;
    while(child <= n)
    {
        if(child+1 <= n && a[child] < a[child+1])
        {
            child++;
        }
        if(temp >= a[child])
        {
            break;
        }
        a[loc] = a[child];
        loc = child;
        child = 2*loc+1;
    }
    a[loc] = temp;
	/******end******/
}