选择排序是一种简单直观的排序算法，其基本原理如下：对于给定的一组记录，经过第一轮比较后得到最小的记录，然后将该记录的位置与第一个记录的位置交换；接着对不包括第一个记录以外的其他记录进行第二次比较，得到最小记录并与第二个位置记录交换；重复该过程，知道进行比较的记录只剩下一个为止。
5.2.复杂度分析从简单选择排序的过程来看，它最大的特点是交换移动数据次数相当少，这样就节约了相应的时间。分析它的时间复杂度发现，无论是最好最差情况，其比较次数都是一样多，第 i 趟排序需要进行 n-i 次关键字比较，此时需要比较次，对于交换次数而言，当最好的时候，交换0次，最差的时候，也就是初始降时，交换次数为 n-1 次，基于最终的时间排序与交换次数总和，因此，总的时间复杂度依然为
尽管与冒泡排序同为
package MySort;
import java.util.Arrays;
public class MySortTest6 {
public static void main(String[] args) {
// 原始数据
int[] data = { 1, 3, 6, 2, 4, 8, 9, 5, 12 };
// 3.选择排序:直接选择排序
System.out.println("直接排序：\t" + Arrays.toString(chooseSort(data)));
}
// 3.选择排序:直接选择排序
private static int[] chooseSort(int[] data) {
// 循环次数
for (int i = 0; i < data.length; i++) {
// 逐个比较
for (int j = i + 1; j < data.length; j++) {
if (data[i] > data[j]) {
int temp = data[i];
data[i] = data[j];
data[j] = temp;
}
}
}
return data;
}
}
6.堆排序 6.1.基本思想 堆排序就是利用堆（假设利用大顶堆）进行排序的方法。它的基本思想是，将待排序的序列构造成一个大顶堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的 n-1 个序列重新构造成一个堆，这样就会得到 n 个元素中次大的值。如此反复执行，便能得到一个有序序列了。
堆排序的实现需要解决的两个关键问题：
（1）将一个无序序列构成一个堆。
（2）输出堆顶元素后，调整剩余元素成为一个新堆。
堆排序的实现：
① 初始化操作：将R[1..n]构造为初始堆；
②每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。
注意：
①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
堆排序的运行时间主要耗费在初始构建堆和在重建堆时反复筛选上。在构建对的过程中，因为我们是完全二叉树从最下层最右边的非终端节点开始构建，将它与其孩子进行比较和若有必要的互换，对每个非终端节点来说，其实最多进行两次比较和互换操作，因此整个构建堆的时间复杂度为O(n)。
在正式排序时，第i次取堆顶记录重建堆需要用O(logi)的时间（完全二叉树的某个节点到根节点的距离为），并且需要取n-1次堆顶记录，因此，重建堆的时间复杂度为O(nlogn)。
所以总体来说，堆排序的时间复杂度为O(nlogn)，由于堆排序对原始记录的状态并不敏感，因此它无论是最好、最坏和平均时间复杂度均为O(nlogn)。这在性能上显然要远远好过于冒泡、简单选择、直接插入的时间复杂度了。
空间复杂度上，它只有一个用来交换的暂存单元，也非常的不错。不过由于记录的比较与交换是跳跃式进行的，因此堆排序也是一种不稳定的排序方法。
另外，由于出事构建堆所需要的比较次数比较多，因此，他并不适合待排序序列个数较少的情况。
package MySort;
import java.util.Arrays;
public class MySortTest7 {
public static void main(String[] args) {
int[] data = { 1, 3, 6, 2, 4, 8, 9, 5, 12 };
// 3.选择排序:堆排序
System.out.println("堆排序：\t" + Arrays.toString(heapSort(data)));
}