java 树形选择排序_选择排序、树形排序、堆排序的java代码实现
时间: 2023-10-20 20:12:09 浏览: 27
选择排序 Java 代码实现:
```java
public static void selectionSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
```
树形排序 Java 代码实现:
```java
public static void treeSort(int[] arr) {
TreeNode root = new TreeNode(arr[0]);
for (int i = 1; i < arr.length; i++) {
root.insert(arr[i]);
}
root.traverseInOrder(arr);
}
private static class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
left = null;
right = null;
}
public void insert(int val) {
if (val < this.val) {
if (left == null) {
left = new TreeNode(val);
} else {
left.insert(val);
}
} else {
if (right == null) {
right = new TreeNode(val);
} else {
right.insert(val);
}
}
}
public void traverseInOrder(int[] arr) {
if (left != null) {
left.traverseInOrder(arr);
}
arr[index++] = val;
if (right != null) {
right.traverseInOrder(arr);
}
}
}
```
堆排序 Java 代码实现:
```java
public static void heapSort(int[] arr) {
int n = arr.length;
// build heap
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// extract elements one by one
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
private static void heapify(int[] arr, int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
```