# 1. 简单选择排序
也就是每次选择从下标`i`开始到后面的所有序列中的最小值的下标，然后将最小值下标和当前的`i`下标进行交换。也就是每次都放置到最终有序的位置。显然时间复杂度为`O(n^2)`。代码如下：
~~~
public void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min_idx = i;
for (int j = i + 1; j < arr.length; j++) {
if (arr[min_idx] > arr[j]) {
min_idx = j;
}
}
swap(arr, min_idx, i);
}
}
~~~
# 2. 堆排序
~~~
public void heapSort(int[] arr) {
for (int i = 0; i < arr.length; i++) {
heapInsert(arr, i);
}
int size = arr.length - 1;
swap(arr, size, 0);
while (size > 0) {
size--;
heapify(arr, 0, size);
swap(arr, 0, size);
}
}
private void heapify(int[] arr, int i, int size) {
int left = i * 2 + 1;
while (left < size) {
int largest = left + 1 < size && arr[left] < arr[left + 1] ? left + 1 : left;
largest = arr[i] > arr[largest] ? i : largest;
if (largest == i) {
break;
}
swap(arr, i, largest);
i = largest;
left = i * 2 + 1;
}
}
private void heapInsert(int[] arr, int index) {
while (arr[index] > arr[(index - 1) / 2]) {
swap(arr, index, (index - 1) / 2);
index = (index - 1) / 2;
}
}
~~~
