堆排序——ANSI C实现

墨蓝 2022-05-18 00:05 157阅读 0赞

typedef int ElementType;

/* 利用中间变量的交换算法 */
    void Swap(ElementType *a, ElementType *b) {
    	ElementType temp;
    	temp = *a;
    	*a = *b;
    	*b = temp;
    }

/*
     * 在控制台打印数组（整数）
     *
     * */
    void PrintArray(int *arr, int size) {
    	printf("Array: ");
    	for (int i = 0; i < size; i++)
    		printf("%d ", arr[i]);
    	printf("\n");
    }

/*
     * 生成随机数数组
     *
     * */
    int *GetRandomArray(int size, int max) {
    	// 检查参数
    	if (size <= 0)
    		return NULL ;
    
    	// 申请空间
    	int *array = (int *) malloc(size * sizeof(int));
    
    	// 以当前时间为种子生成随机数
    	srand(clock());
    	for (int i = 0; i < size; i++) {
    		array[i] = rand() % max;
    	}
    
    	return array;
    }

/*
     * 在一个二叉树中筛选最大的结点
     *
     * 输入参数1：待排数组
     * 输入参数2：待排数组尺寸
     * 输入参数3：root，根结点下标
     *
     * */
    void RootSelect(ElementType *arr, int size, int root) {
    	if (root < size) {
    		// 计算左孩子与右孩子的下标
    		int left = 2 * root + 1;
    		int right = 2 * root + 2;
    
    		// 若左、右子结点都存在，且左子结点最大，则根结点与左子结点交换
    		if (left < size && right < size && arr[left] > arr[root]
    				&& arr[left] >= arr[right]) {
    			Swap(arr + root, arr + left);
    
    			// 判定左子树是否符合堆的定义
    			if (!IsHeap(arr, size, left)) {
    				RootSelect(arr, size, left);
    			}
    		}
    
    		// 若左、右子结点都存在，且右子结点最大，则根结点与右子结点交换
    		else if (left < size && right < size && arr[right] > arr[root]
    				&& arr[right] >= arr[left]) {
    			Swap(arr + root, arr + right);
    
    			// 判断右子树是否符合堆的定义
    			if (!IsHeap(arr, size, right)) {
    				RootSelect(arr, size, right);
    			}
    		}
    
    		// 若只有左子结点存在，且左子结点最大，则根结点与左子结点交换
    		else if (left < size && right >= size && arr[left] > arr[root]) {
    			Swap(arr + root, arr + left);
    
    			// 判定左子树是否符合堆的定义
    			if (!IsHeap(arr, size, left)) {
    				RootSelect(arr, size, left);
    			}
    		}
    	}
    }

/*
     * 判定一个结点与其左右子结点是否符合堆的定义
     *
     * 输入参数1：待排数组
     * 输入参数2：待排数组尺寸
     * 输入参数3：root，根结点下标
     *
     * 输出类型：0，不是堆；1，是堆；-1，出错
     *
     * */
    int IsHeap(ElementType *arr, int size, int root) {
    	// 检查输入参数
    	if (arr == NULL || size == 0 || root >= size)
    		return -1;
    
    	if (root < size) {
    		// 计算左孩子与右孩子的下标
    		int left = 2 * root + 1;
    		int right = 2 * root + 2;
    
    		// 若根结点小于左子结点，则不满足堆定义
    		if (left < size && arr[root] < arr[left])
    			return 0;
    
    		// 若根结点小于右子结点，则不满足堆定义
    		if (right < size && arr[root] < arr[right])
    			return 0;
    	}
    
    	return 1;
    }

ElementType *Sort(ElementType *arr, int size) {
    	// 检查参数，若arr为NULL或size为0，则说明是空表，返回NULL
    	if (arr == NULL || size <= 0)
    		return NULL;
    
    	for (int i = size - 1; i >= 0; i--) {
    		// 调整堆
    		for (int j = i; j >= 0; j--) {
    			RootSelect(arr, i + 1, j);
    		}
    
    		// 将堆顶结点与最后一个结点交换
    		Swap(arr, arr + i);
    	}
    
    	return arr;
    }

int main() {
    
    	int size = 10;
    	int max = 300;
    	int *array = GetRandomArray(size, max);
    	printf("Original ");
    	PrintArray(array, size);
    	Sort(array, size);
    	printf("Sorted   ");
    	PrintArray(array, size);
    
    	return 0;
    }