#include<stdio.h>
#include<stdlib.h>
void chiocesort(int arr[]) {
	for (int i = 0; i < 29; i++) {
		int index = i;
		for (int j = i; j < 30; j++) {
			if (arr[j] < arr[index]){
				index = j;
			}
		}
		int temp = arr[i];
		arr[i] = arr[index];
		arr[index] = temp;
		for (int k = 0; k < 30; k++) {
			printf("%d ", arr[k]);
		}
		printf("\n");
	}
}
void adjustHeap(int arr[], int n, int root) {
    int parent = root;       
	int child = root * 2 + 1;
	while (child < n) {
		if ((child + 1) < n && arr[child] < arr[child + 1]) {
			child++;
		}
		if (arr[parent] < arr[child]) {
			int temp = arr[parent];
			arr[parent] = arr[child];
			arr[child] = temp;
			parent = child;
			child = parent * 2 + 1;
		}
		else 
		{
			break;
		}
	}
}
// 堆排序（升序）
void heapSort(int arr[], int n) {
	//建堆
	printf("建堆过程\n");
    for (int i = n / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, n, i);
		for (int k = 0; k < 30; k++) {
			printf("%d ", arr[k]);
		}
		printf("\n");
    }
	printf("调整过程\n");
	for (int i = n - 1; i >= 0; i--) {
		int temp = arr[i];
		arr[i] = arr[0];
		arr[0] = temp;
		adjustHeap(arr, i, 0);
		for (int k = 0; k < 30; k++) {
			printf("%d ", arr[k]);
		}
		printf("\n");
	}
}
int main() {
	int arr[30];
	int arr1[30];
	printf("原始数组\n");
	for (int i = 0; i < 30; i++) {
		arr1[i] = rand() % 100;
		arr[i] = arr1[i];
		printf("%d ",arr[i]);
	}
	printf("\n");
	printf("选择排序\n");
	chiocesort(arr);
	printf("\n");
	printf("heap\n");
	heapSort(arr1, 30);
	return 0;
}