常用的选择排序方法有两种：直接选择排序和堆排序。
直接排序简单直观，但性能略差；
堆排序是一种较为高效的选择排序方法，但实现起来略微复杂。
直接选择排序
直接选择排序的思路很简单，它需要经过n-1趟比较。
- 第1趟比较：程序将记录定位在第1个数据上，拿第1个数据依次和它后面每个数据进行比较，如果第1个数据大于后面某个数据，交换它们……依此类推。经过第1趟比较，这组数据中最小的数据被选出，它被排在第1位。
- 第2趟比较：程序将记录定位在第2个数据上，拿第2个数据依次和它后面每个数据进行比较，如果第2个数据大于后面某个数据，交换它们……依此类推。经过第2趟比较，这组数据中第2小的数据被选出，它被排在第2位。
……
按此规则一共进行n-1趟比较，这组数据中第n-1小（第2大）的数据被选出，被排在第n-1位（倒数第1位）；剩下的就是最大的数据，它排在最后。
直接选择排序的优点是算法简单，容易实现。
直接选择排序的缺点是每趟只能确定一个元素，n个数组需要进行n-1趟比较。
封装的实体类
public class DataWrap implements Comparable<DataWrap>{
int data;
String flag;
public DataWrap(int data, String flag) {
this.data = data;
this.flag = flag;
}
@Override
public String toString() {
return data+flag;
}
@Override
public int compareTo(DataWrap dw) {
return this.data > dw.data ? 1 : (this.data == dw.data ? 0 : -1);
}
}
具体的算法与测试
public class SelectSort {
public static void selectSort(DataWrap[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
//依次进行n-1趟比较，第i趟比较将第i大的值选出，放在i位置上
for (int i = 0; i < arrayLength - 1; i++) {
//第i个数据只需要和它后面的数据比较
for (int j = i + 1; j < arrayLength; j++) {
//如果第i位置的数据 大于 j位置上的数据，就交换他们
if (data[i].compareTo(data[j]) > 0) {
DataWrap tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
}
System.out.println("第 "+i+" 趟后："+Arrays.toString(data));
}
}
/**
* 优化：
* 在一趟的排序过程中，记录最小数据的位置。当本趟比较完成时，如果第i位于minIndex不相等时，才交换位置
* @param data
*/
public static void selectSort2(DataWrap[] data) {
System.out.println("开始排序");
int arrayLength = data.length;
//依次进行n-1趟比较，第i趟比较将第i大的值选出，放在i位置上
for (int i = 0; i < arrayLength - 1; i++) {
//minIndex用于保留本趟比较中最小值的索引
int minIndex = i;
//第i个数据只需要和它后面的数据比较
for (int j = i + 1; j < arrayLength; j++) {
//如果第minIndex位置的数据 大于 j位置上的数据，将j的值赋给minIndex
if (data[minIndex].compareTo(data[j]) > 0) {
minIndex = j;
}
}
if (i != minIndex) {
DataWrap tmp = data[i];
data[i] = data[minIndex];
data[minIndex] = tmp;
}
System.out.println("第 "+i+" 趟后："+Arrays.toString(data));
}
}
public static void main(String[] args) {
DataWrap[] data = new DataWrap[]{
new DataWrap(21, ""),
new DataWrap(30, ""),
new DataWrap(49, ""),
new DataWrap(30, "*"),
new DataWrap(16, ""),
new DataWrap(9, "")
};
DataWrap[] data2 = Arrays.copyOf(data, data.length);
System.out.println("排序前："+Arrays.toString(data));
selectSort(data);
System.out.println("排序后："+Arrays.toString(data));
selectSort2(data2);
}
}
总结
直接选择排序，时间效率为O(n2)
交换时，只需要一个附加程序单元用于交换，其空间效率为：O(1)
30与30* 排序后，位置发生了变化，所以排序是不稳定的
堆排序
堆的概念
假设有n个数据元素的序列k0，k1，…，kn-1，当且仅当满足如下关系时，可以将这组数据称为小顶堆（小根堆）。
ki <= k2i+1且ki <= k2i+2（其中i=0, 2,…，(n-1)/2）
或者，满足如下关系时，可以将这组数据称为大顶堆（大根堆）。
ki >= k2i+1且ki >=k2i+2（其中i=0, 2,…，(n-1)/2）
对于满足小顶堆的数据序列k0，k1，…，kn-1，如果将它们顺序排成一棵完全二叉树，则此树的特点是：树中所有节点的值都小于其左右子节点的值，此树的根节点的值必然最小。反之，对于满足大顶堆的数据序列k0，k1，…，kn-1，如果将它们顺序排成一棵完全二叉树，则此树的特点是：树中所有节点的值都大于其左右子节点的值，此树的根节点的值必然最大。
通过上面介绍不难发现一点，小顶堆的仁义子树也是小顶堆，大顶堆的任意子树还是大顶堆
例：判断数据序列
9,30,49,46,58,79是否为堆，将其转换为一个完全二叉树
判断数据序列：93,82,76,63,58,67,55是否为堆，将其转换为一个完全二叉树
堆排序的关键在于建堆，它按如下步骤完成排序。
- 第1趟将索引0～n-1处的全部数据建大顶（或小顶）堆，就可以选择出这组数组中的最大（或最小）值。
- 将上一步所建的大顶（或小顶）堆的根节点与这组数据的最后一个节点交换，就使得这组数据中最大（或最小）值排在最后。
- 第2趟将索引0～n-2处的全部数据建大顶（或小顶）堆，就可以选择出这组数组中的最大（或最小）值。
将上一步所建的大顶（或小顶）堆的根节点与这组数据的倒数第2个节点交换，就使得这组数据中最大（或最小）值排在倒数第2位。
……- 第k趟将索引0～n-k处的全部数据建大顶（或小顶）堆，就可以选择出这组数组中最大（或最小）值。
- 将上一步所建的大顶（或小顶）堆的根节点与这组数据的倒数第k个节点交换，使得这组数据中最大（或最小）值排在倒数第k位。
通过上面介绍不难发现，堆排序的步骤就是重复执行以下2步。
（1）建堆；
（2）拿堆的根节点和最后一个节点交换。
由此可见，对于包含n个数据元素的数据组而言，堆排序需要经过n-1次建堆，每次建堆的作用就是选出该堆的最大值或最小值。因为堆排序的本质上依然是一种选择排序。
例如如下数据组：
9，79，46，30，58，49
建堆过程
-
先将其转换为完全二叉树，转换得到的完全二叉，如下图
将数据转换为完全二叉树 -
完全二叉树的最后一个非叶子节点，也就是最后一个节点的父节点。最后一个节点的索引为数组长度-1，也就是len-1，那么最后一个非叶子节点的索引应该是为（len-2)/2。也就是从索引为2的节点开始，如果其子节点的值大于它本身的值，则把它和较大子节点进行交换，即将索引2处节点和索引5处的元素交换。交换后的结果如下图
交换1次后的完全二叉树 - 向前处理前一个节点，也就是处理索引为1的节点，此时79>30、79>58，因此无须交换。
-
向前处理前一个节点，也就是处理索引为0的节点，此时 9<79、9<49，因此需要交换。应该拿索引0的节点和索引1的节点交换（9的两个子节点中，索引为1的节点的值较大），交换后的完全二叉树如下图
交换2次后的完全二叉树 -
如果某个节点和它的某个子节点交换后，该子节点又有子节点，系统还需再次对该子节点进行判断。例如，上图中索引 0的节点和索引 1的节点交换后，索引 1的节点还有子节点，因此程序必须再次保证索引1处节点的值大于等于其左、右子节点的值。因此还需要交换一次，交换后的大顶堆如下图
大顶堆建立完成
具体算法
public class HeapSort {
public static void heapSort(DataWrap[] data){
System.out.println("开始排序");
int arrryLength = data.length;
//循环建堆， 第0个节点没有父节点的所以可以少比较一次
for (int i = 0; i < arrryLength - 1; i++) {
//建堆
buildMaxdHeap(data, arrryLength - 1 - i);
//交换堆顶和最后一个元素
swap(data, 0, arrryLength - 1 - i);
System.out.println(Arrays.toString(data));
}
}
/**
* 对data数据从0到lastIndex建大顶堆
* @param data
* @param lastIndex
*/
private static void buildMaxdHeap(DataWrap[] data, int lastIndex){
//从lastIndex处节点（最后一个节点）的父节点开始，依次循环其前面的各个父节点
//说明： 不管lastIndex是左子树还是右子树， (lastIndex-1)/2 =(int)x，最后取整后，就是他的父节点
for (int i = (lastIndex - 1) / 2; i >= 0; i--) {
//k保存当前正在判断的节点
int k=i;
//如果当前k节点的子节点存在
while (k * 2 + 1 <= lastIndex) {
//k节点的左子节点的索引
int biggerIndex = 2 * k + 1;
//如果biggerIndex小于lastIndex，即biggerIndex+1
//代表k节点的右子节点存在（因为lastIndex是最后一个节点， biggerIndex<lastIndex，2k+2是k节点的右子节点，那么2k+2<=lastIndex）
if (biggerIndex < lastIndex) {
//如果右子节点的值较大
if (data[biggerIndex].compareTo(data[biggerIndex + 1]) < 0) {
//biggerIndex总是记录较大子节点的索引
biggerIndex++;
}
}
//如果k节点的值小于其他较大子节点的值
if (data[k].compareTo(data[biggerIndex]) < 0) {
//交换它们
swap(data, k, biggerIndex);
//将biggerIndex赋给k，开始while循环的下一次循环
//重新保证k节点的值大于其左、右子节点的值（重新建立此节点的堆）
k = biggerIndex;
}else{
break;
}
}
}
}
/**
* 交换data数组中i，j两个索引出的元素
* @param data
* @param i
* @param j
*/
private static void swap(DataWrap[] data, int i, int j){
DataWrap tmp = data[i];
data[i] = data[j];
data[j] = tmp;
}
public static void main(String[] args) {
DataWrap[] data = new DataWrap[]{
new DataWrap(21, ""),
new DataWrap(30, ""),
new DataWrap(49, ""),
new DataWrap(30, "*"),
new DataWrap(21, "*"),
new DataWrap(16, ""),
new DataWrap(9, "")
};
System.out.println("排序前：" + Arrays.toString(data));
heapSort(data);
System.out.println("排序后："+Arrays.toString(data));
}
}
总结
- 假设有n项数据，需要进行n-1次建堆，则其时间效率是O(log2n)
- 堆排序也只需要一个附加程序单元用于交换，其空间效率为O(1)
- 堆排序是不稳定的
