上一篇总结了交换排序的冒泡排序和快速排序。这一篇要总结的是选择排序，选择排序分为直接选择排序和堆排序，主要从以下几点进行总结。
1、直接选择排序及算法实现
2、堆排序及算法实现
1、直接选择排序及算法实现直接选择排序(Straight Select Sort) 是一种简单的排序方法，它的基本思想是：通过length-1 趟元素之间的比较，从length-i+1个元素中选出最小的元素，并和第i个元素交换位置。直接选择排序的最坏时间复杂度为O(n2)，平均时间复杂度为O(n2)
下图展示了直接选择排序的过程。
1-1、示意图
SelectionSort.Java
public class SelectionSort {
public static void main(String[] args) {
int[] list = {9, 1, 2, 5, 7, 4, 8, 6, 3, 5};
System.out.println("************直接选择排序************");
System.out.println("排序前：");
display(list);
System.out.println("");
System.out.println("排序后：");
selectionSort(list);
display(list);
}
/**
* 直接选择排序算法
*/
public static void selectionSort(int[] list) {
// 要遍历的次数（length-1次）
for (int i = 0; i < list.length - 1; i++) {
// 将当前下标定义为最小值下标
int min = i;
// 遍历min后面的数据
for (int j = i + 1; j <= list.length - 1; j++) {
// 如果有小于当前最小值的元素，将它的下标赋值给min
if (list[j] < list[min]) {
min = j;
}
}
// 如果min不等于i，说明找到真正的最小值
if (min != i) {
swap(list, min, i);
}
}
}
/**
* 交换数组中两个位置的元素
*/
public static void swap(int[] list, int min, int i) {
int temp = list[min];
list[min] = list[i];
list[i] = temp;
}
/**
* 遍历打印
*/
public static void display(int[] list) {
System.out.println("********展示开始********");
if (list != null && list.length > 0) {
for (int num :
list) {
System.out.print(num + " ");
}
System.out.println("");
}
System.out.println("********展示结束********");
}
}
测试结果：
堆排序(Heap Sort) 利用堆（一般为大根堆）进行排序的方法。它的基本思想是：将待排序的元素构造成一个大根堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将它与数组的末尾元素进行交换，此时末尾元素就是最大值），然后将剩余的length-1 个元素重新构造成一个大根堆，这样就会得到length个元素中的次大值。如此反复执行，便能得到一个有序的序列。
堆是具有下列性质的完全二叉树：每个节点的值都大于或等于其左右孩子节点的值，称为大根堆；每个节点的值都小于或等于其左右孩子节点的值，称为小根堆。
堆排序的最坏时间复杂度为O(n*log2n)，平均时间复杂度为O(n*log2n)
2-1、示意图图一：
图二：
图三：
图四：
图五：
图六：
HeapSort.java