欢迎大家来到IT世界,在知识的湖畔探索吧!

算法思想

将待排序的序列构成一个大顶堆，然后拿出堆顶，将剩余的数列构成一个大顶堆。以此类推,最终得到一个有序数列

算法实现

• PHP实现

<?php

function hsort(&$arr, $len) {
	$idx = $len - 1;
	for ($i = 0; $i < floor($len / 2); $i ++) {
		buildHeap($arr, $i; $idx);
	}

	while($idx > 0) {
		list($arr[0], $arr[$idx]) = [$arr[$idx], $arr[0]];
		$idx --;
		buildHeap($arr, 0, $idx);
	}
}

function buildHeap(&$arr, $low, $high) {
	while($low * 2 + 1 <= $high) {
		$j = $low * 2 + 1;

		if ($j < $high && $arr[$j] < $arr[$j + 1]) {
			$j ++;
		}

		if ($arr[$low] > $arr[$j]) {
			break;
		}
		list($arr[$low], $arr[$j]) = [$arr[$j], $arr[$low]];

		$low = $j;
	}
}
$arr = [13,1, 7,11, 5, 3, 9, 8];
$res = mergeSort($arr);
print_r($res);

欢迎大家来到IT世界,在知识的湖畔探索吧!

• Java实现

欢迎大家来到IT世界,在知识的湖畔探索吧!public static void main(String[] args)
    {
        int [] arr = {13,1, 7,11, 5, 3, 9};
        hsort(arr, arr.length);
        System.out.println(Arrays.toString(arr));
    }
public static void hsort(int[] array, int len)
    {
        int idx = len - 1;

        for (int i = 0; i < len / 2; i ++) {
            buildHeap(array, i, idx);
        }
        while (idx > 0) {
            int tmp = array[0];
            array[0] = array[idx];
            array[idx] = tmp;
            idx --;
            buildHeap(array, 0, idx);
        }
    }
public static void buildHeap(int[] array, int low, int high)
    {
        while (low * 2 + 1 <= high) {
            int j = low * 2 + 1;
            if (j < high && array[j] < array[j + 1]) {
                j ++;
            }
            if (array[j] < array[low]) {
                break;
            }
            int tmp = array[low];
            array[low] = array[j];
            array[j] = tmp;
            low = j;
        }
    }

• Python实现

def buildHeap(lists, low, high):
    while low * 2 + 1 <= high:
        j = low * 2 + 1
        if j < high and lists[j] < lists[j + 1]:
            j += 1
        if lists[j] < lists[low]:
            break
        lists[low], lists[j] = lists[j], lists[low]
        low = j


def hsort(lists, length):
    idx = length - 1
    for x in range(math.floor(length / 2)):
        buildHeap(lists, x, idx)
    while idx > 0:
        lists[0], lists[idx] = lists[idx], lists[0]
        idx -= 1
        buildHeap(lists, 0, idx)


if __name__ == '__main__':
    # app.run(debug=True)
    arr = [13, 1, 7, 11, 5, 3, 9]
    hsort(arr, len(arr))
    for i in range(len(arr)):
        print("%d" % arr[i])

• Go实现

欢迎大家来到IT世界,在知识的湖畔探索吧!func main() {
	arr := []int{13, 1, 7, 11, 5, 3, 9}
	hsort(arr, len(arr))
	fmt.Println(arr)
}

func hsort(arr []int, len int) {
	idx := len - 1
	for i := 0; i < len/2; i++ {
		buildHeap(arr, i, idx)
	}
	for idx > 0 {
		arr[0], arr[idx] = arr[idx], arr[0]
		idx--
		buildHeap(arr, 0, idx)
	}
}

func buildHeap(arr []int, low, high int) {
	for low*2+1 <= high {
		j := low*2 + 1
		if j < high && arr[j] < arr[j+1] {
			j++
		}
		if arr[j] < arr[low] {
			break
		}
		arr[j], arr[low] = arr[low], arr[j]
		low = j
	}
}