排序——堆排序

2019/08/30 15:30

1. 算法步骤
创建一个堆 H[0……n-1]；

public int[] sort(int[] sourceArray) throws Exception {
// 对 arr 进行拷贝，不改变参数内容
int[] arr = Arrays.copyOf(sourceArray, sourceArray.length);

int len = arr.length;

buildMaxHeap(arr, len);

for (int i = len - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0, len);
}
return arr;
}

private void buildMaxHeap(int[] arr, int len) {
for (int i = (int) Math.floor(len / 2); i >= 0; i--) {
heapify(arr, i, len);
}
}

private void heapify(int[] arr, int i, int len) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int largest = i;

if (left < len && arr[left] > arr[largest]) {
largest = left;
}

if (right < len && arr[right] > arr[largest]) {
largest = right;
}

if (largest != i) {
swap(arr, i, largest);
heapify(arr, largest, len);
}
}

private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

参考

https://blog.csdn.net/u013384984/article/details/79496052

https://blog.csdn.net/qq_36183935/article/details/80234259

0
0 收藏

0 评论
0 收藏
0