#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define Random(x) (rand()%x)
#define ARR_LENGHT 6
// 为了方便,第零位不考虑
//int arr[ARR_LENGHT] = { 0,0,0,0,0,0,0,0,0,0,0 };
int arr[ARR_LENGHT] = { 0,0,0,0,0,0 };
int hs_compare_times = 0, hs_move_times = 0;
int *key_word_loc;
int left(int i) { return 2 * i; }
int right(int i) { return 2 * i + 1; }
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
if (a == key_word_loc) {
hs_move_times++;
key_word_loc = b;
}
if (b == key_word_loc) {
hs_move_times++;
key_word_loc = a;
}
}
void max_heapify(int *a, int i) {
int l = left(i), r = right(i), largest;
// 左孩子是否比i大
if (l <= ARR_LENGHT && a[l] > a[i])
largest = l;
else
largest = i;
if (&a[l] == key_word_loc || &a[i] == key_word_loc) {
hs_compare_times++; /*------------只出现在两个地方 1/2----------------*/
printf("####%d\n", hs_compare_times);
}
// 右孩子是否比i大
if (r <= ARR_LENGHT && a[r] > a[largest])
largest = r;
if (&a[r] == key_word_loc) {
hs_compare_times++; /*------------只出现在两个地方 2/2----------------*/
printf("****%d\n", hs_compare_times);
}
// 如果i不比它所有的孩子大,就将i下降一位,继续执行max_heapify().
if (largest != i) {
swap(&a[largest], &a[i]);
max_heapify(a, largest);
}
}
void build_heap(int *arr) {
// 从 (ARR_LENGHT - 1) / 2 是最后一个节点
// 建堆是忽略了第零个,所以进行到 i = 1 即可,所以i > 0.
for (int i = (ARR_LENGHT - 1) / 2; i > 0; i--) {
max_heapify(arr, i);
}
}
// 删除的本质是将第一个赋上最小值。
// 总是删除第一个,arr_lenght是数组的长度。
void heap_remove(int *a) {
a[1] = INT_MIN;
build_heap(a);
}
// arr是原数组,arr_sort是排序后的数组
// 将arr的第1个赋给arr的第i个.
void heap_sort(int *arr, int *arr_sort) {
for (int i = 0; i < ARR_LENGHT - 1; i++) {
arr_sort[i] = arr[1];
heap_remove(arr);
}
}
int RunHeapSort() {
int choice, i;
int arr_sort[ARR_LENGHT - 1];
srand((unsigned)time(0));
printf("****************************************\n");
printf("已选择 堆排序\n");
printf("请选择输入模式:\n");
printf("1. 自动输入随机数\n");
printf("2. 手动输入数字\n");
printf("0. 返回上一级菜单\n");
printf("****************************************\n");
printf("请输入您的选择: ");
scanf("%d", &choice);
while (choice) {
switch (choice) {
case 1:
hs_compare_times = 0;
hs_move_times = 0;
printf("原顺序为:\n");
for (i = 1; i < ARR_LENGHT; i++) {
arr[i] = Random(100);
printf("%2d ", arr[i]);
}
putchar('\n');
printf("关键字为:%d\n", arr[1]);
key_word_loc = &arr[1];
build_heap(arr);
heap_sort(arr, arr_sort);
printf("排序后:\n");
for (i = ARR_LENGHT - 2; i >= 0; i--)
printf("%2d ", arr_sort[i]);
putchar('\n');
printf("比较了: %d\n", hs_compare_times);
printf("交换了: %d\n", hs_move_times * 3);
putchar('\n');
}
printf("请输入您的选择: ");
scanf("%d", &choice);
}
return 0;
}
我就写了一个堆排序,自增却会变成-2147483647,谁能帮我看看错在哪里.....
有几张截图。