堆排序比我更狡猾

Question

我正在尝试实现基于数组的堆排序，它对前几个排序但不完全排序，我不明白为什么。这是我正在处理的内容：

public class HeapSort{

    static int[] numbers = new int[] { 0, 13, 8, 5, 10, 9, 15, 1, 2, 3, 6, 4, 12, 14, 7, 11 };
    static int[] array = new int[16];

    public static void main(String[] args) {

        for (int i = 0; i < 15; i++) {
            array[i] = numbers[i];
            if (i > 1)
                sort(i);
        }

        for (int i = 1; i < 15; i++) {
            System.out.println(array[i]);
        }

    }

    public static void sort(int i) {

        int parentLocation = i / 2;
        int childLocation = i;

        int parentValue = array[parentLocation];

        int childValue = array[childLocation];

            if (childValue < parentValue) {

                array[parentLocation] = childValue;
                array[childLocation] = parentValue;

                sort(parentLocation);

            }

    }

}

我确信我使用递归来回忆父级上的排序是错误的，但我不明白为什么？

TIA

Answer 1

This is heap_sort which uses heapify and max heap concepts. I coded as per the algorithm in "Intro to Algos" book. Have a look.

#include "stdafx.h"

#define LEFT(i)         (2 * (i))
#define RIGHT(i)        (((2 * (i)) + 1))
#define PARENT(i)       ((i) / 2))

void print_heap(int input[], int n)
{
    int i;
    printf("Printing heap: \n");
    for (i = 0; i < n; i++)
        printf("%d ", input[i]);
    printf("\n");
}

void swap_nodes(int *a, int *b)
{
    int tmp;
    tmp = *a;
    *a = *b;
    *b = tmp;
}


void max_heapify(int input[], int i, int n)
{
    int largest;
    int l = LEFT(i + 1) - 1; // Get 0 based array index
    int r = RIGHT(i + 1) - 1; // Get 0 based array index

    if (l < n && input[l] > input[i]) {
        largest = l;
    } else {
        largest = i;
    }

    if (r < n && input[r] > input[largest]) {
        largest = r;
    }

    if (largest != i) {
        swap_nodes(&input[i], &input[largest]);
        max_heapify(input, largest, n);
    }
}

void heapify(int input[], int n)
{
    for (int i = n/2; i >= 0; i--)
        max_heapify(input, i, n); 
}

void heap_sort(int input[], int n)
{
    heapify(input, n);

    for (int i = n - 1; i >= 1; i--) {
        swap_nodes(&input[0], &input[i]);
        n = n - 1;
        max_heapify(input, 0, n);
    }
}

int _tmain(int argc, _TCHAR* argv[])
{
    //int input[] = {6, 5, 3, 1, 8, 7, 4, 2};
    //int input[] = {4, 1, 3, 2, 16, 9, 10, 14, 8, 7};
    int input[] = {5, 3, 17, 10, 84, 19, 6, 22, 9, 1};
    //int input[] = {16, 14, 10, 8, 7, 9, 3, 2, 4, 1};


    int n = sizeof(input) / sizeof(input[0]);

    print_heap(input, n);
    heap_sort(input, n);
    print_heap(input, n);

    return 0;

}

Answer 2

我在 C# 中有这个最小堆实现，漂亮易于阅读。你的 impl 缺失了很多。比如堆化。看看它。希望有帮助。