쌓 기 정렬 - ANSI C 구현

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("
");
}

/*
 *        
 *
 * */
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;
}