java实现排序算法之选择排序（直接选择排序、堆排序）

常用的选择排序算法有两种：直接选择排序和堆排序。
一、直接选择排序(Straight Select Sorting) 也是一种简单的排序方法，它的基本思想是：第一次从R[0]~R[n-1]中选取最小值，与R[0]交换，第二次从R{1}~R[n-1]中选取最小值，与R[1]交换，....，
　　第i次从R[i-1]~R[n-1]中选取最小值，与R[i-1]交换，.....，第n-1次从R[n-2]~R[n-1]中选取最小值，与R[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的有序序列.
     直接选择排序是不稳定的。
首先定义一个数据包装类：

//定义一个数据包装类
public class DataWrap implements Comparable<DataWrap>  
{
	int data;
	String flag;
	public DataWrap(int data, String flag)
	{
		this.data = data;
		this.flag = flag;
	}
	public String toString()
	{
		return data + flag;
	}
	//根据data实例变量来决定两个DataWrap的大小
	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(java.util.Arrays.toString(data));
		}
	}
	public static void main(String[] args)
	{
		DataWrap[] data = {
			new DataWrap(21 , ""),
			new DataWrap(30 , ""),
			new DataWrap(49 , ""),
			new DataWrap(30 , "*"),
			new DataWrap(16 , ""),
			new DataWrap(9 , "")
		};
		System.out.println("排序之前：\n"
			+ java.util.Arrays.toString(data));
		selectSort(data);
		System.out.println("排序之后：\n" 
			+ java.util.Arrays.toString(data));
	}
}

对上面的算法改进，每次找到最小的数据的索引，减少交换的次数，提高算法效率：

public class SelectSort2
{
	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++ )
		{
			//minIndex永远保留本趟比较中最小值的索引
			int minIndex = i ;
			//第i个数据只需和它后面的数据比较
			for (int j = i + 1 ; j < arrayLength ; j++ )
			{
				//如果第minIndex位置的数据 > j位置的数据
				if (data[minIndex].compareTo(data[j]) > 0)
				{
					//将j的值赋给minIndex
					minIndex = j;
				}
			}
			//每趟比较最多交换一次
			if (minIndex != i)
			{
				DataWrap tmp = data[i];
				data[i] = data[minIndex];
				data[minIndex] = tmp;
			}
			System.out.println(java.util.Arrays.toString(data));
		}
	}
	public static void main(String[] args)
	{
		DataWrap[] data = {
			new DataWrap(21 , ""),
			new DataWrap(30 , ""),
			new DataWrap(49 , ""),
			new DataWrap(30 , "*"),
			new DataWrap(16 , ""),
			new DataWrap(9 , "")
		};
		System.out.println("排序之前：\n"
			+ java.util.Arrays.toString(data));
		selectSort(data);
		System.out.println("排序之后：\n" 
			+ java.util.Arrays.toString(data));
	}
}

二、堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征，使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
　　（1）用大根堆排序的基本思想
　　① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区
　　② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换，由此得到新的无序区R[1..n-1]和有序区R[n]，且满足R[1..n-1].keys≤R[n].key
　　③由于交换后新的根R[1]可能违反堆性质，故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换，由此得到新的无序区R[1..n-2]和有序区R[n-1..n]，且仍满足关系R[1..n-2].keys≤R[n-1..n].keys，同样要将R[1..n-2]调整为堆。
　　……
　　直到无序区只有一个元素为止。
　　（2）大根堆排序算法的基本操作：
　　① 初始化操作：将R[1..n]构造为初始堆；
　　② 每一趟排序的基本操作：将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换，然后将新的无序区调整为堆(亦称重建堆)。
　　注意：
　　①只需做n-1趟排序，选出较大的n-1个关键字即可以使得文件递增有序。
　　②用小根堆排序与利用大根堆类似，只不过其排序结果是递减有序的。堆排序和直接选择排序相反：在任何时刻堆排序中无序区总是在有序区之前，且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止
堆排序与直接选择排序的区别
　　直接选择排序中，为了从R[1..n]中选出关键字最小的记录，必须进行n-1次比较，然后在R[2..n]中选出关键字最小的记录，又需要做n-2次比较。事实上，后面的n-2次比较中，有许多比较可能在前面的n-1次比较中已经做过，但由于前一趟排序时未保留这些比较结果，所以后一趟排序时又重复执行了这些比较操作。
　　堆排序可通过树形结构保存部分比较结果，可减少比较次数。
    堆排序是不稳定的。
堆排序代码实现：

public class HeapSort
{
	public static void heapSort(DataWrap[] data) 
	{
		System.out.println("开始排序");
		int arrayLength = data.length;
		//循环建堆
		for (int i = 0; i < arrayLength - 1 ; i++ )
		{
			//建堆
			builMaxdHeap(data , arrayLength - 1 - i);
			//交换堆顶和最后一个元素
			swap(data , 0 , arrayLength - 1 - i);
			System.out.println(java.util.Arrays.toString(data));
		}
	}
	//对data数组从0到lastIndex建大顶堆
	private static void builMaxdHeap(DataWrap[] data , int lastIndex)
	{
		//从lastIndex处节点（最后一个节点）的父节点开始
		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节点的右子节点存在
				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两个索引处的元素
	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(21 , ""),
			new DataWrap(30 , ""),
			new DataWrap(49 , ""),
			new DataWrap(30 , "*"),
			new DataWrap(21 , "*"),
			new DataWrap(16 , ""),
			new DataWrap(9 , "")
		};
		System.out.println("排序之前：\n"
			+ java.util.Arrays.toString(data));
		heapSort(data);
		System.out.println("排序之后：\n" 
			+ java.util.Arrays.toString(data));
	}
}