- it
- Java实现堆排序
堆排序
public class HeapSort {
public static void heapSort(int[] arr
) {
if (arr
== null
|| arr
.length
< 2) {
return;
}
for (int i
= 0; i
< arr
.length
; i
++) {
heapInsert(arr
, i
);
}
int heapsize
= arr
.length
;
swap(arr
, 0, --heapsize
);
while (heapsize
> 0) {
heapify(arr
, 0, heapsize
);
swap(arr
, 0, --heapsize
);
}
}
public static void heapify(int[] arr
, int index
, int heapsize
) {
int left
= index
* 2 + 1;
while (left
< heapsize
) {
int bigindex
= left
+ 1 < heapsize
&& arr
[left
+ 1] > arr
[left
] ? left
+ 1 : left
;
bigindex
= arr
[bigindex
] > arr
[index
] ? bigindex
: index
;
if (bigindex
== index
) {
break;
}
swap(arr
, bigindex
, index
);
index
= bigindex
;
left
= index
* 2 + 1;
}
}
public static void heapInsert(int[] arr
, int index
) {
while (arr
[index
] > arr
[(index
- 1) / 2]) {
swap(arr
, index
, (index
- 1) / 2);
index
= (index
- 1) / 2;
}
}
public static void swap(int[] arr
, int i
, int j
) {
int tmp
= arr
[i
];
arr
[i
] = arr
[j
];
arr
[j
] = tmp
;
}
public static void main(String
[] args
) {
int[] arr
= { 2, 3, 6, 1, 8, 5, 5, 6, 0 };
heapSort(arr
);
for (int i
= 0; i
< arr
.length
; i
++) {
System
.out
.println(arr
[i
]);
}
}
}
