昨天写了5大排序的交换排序，女朋友给我一个大大的赞，今天一天激情满满。下班了，有时间整理一下另外的排序算法，今晚就写写选择排序吧
二.选择排序（直接选择排序+堆排序）
1.直接选择排序
直接选择排序的核心思想是在无序序列中选择最大（小）值，然后和第一个值进行交换
根据比较类Comparator来判断是升序排列还是降序排列
当Comparator中的compare函数是 a > b ? 1 : (a < b ? -1 : 0)时，则是升序排列
compare函数是a > b ? -1 : (a < b ? 1 : 0)时，则是降序排列
直接选择排序的思路：
①整个数组都是无序区域
②从无序区域的最开始元素开始遍历
③找出无序区域最开始元素后的元素中的最小值
④最小值和无序区域最开始元素交换位置
⑤无序区域最开始元素加入到有序区域
⑥重复①~⑤
时间复杂度：O(n^2)
空间复杂度：O(1)
public static <T> void selectSort(T[] t, Comparator<? super T> comparator) {
int size = t == null ? 0 : t.length;
T temp = null;
for(int i = 0; i < size; i++) {
int k = i;
for(int j = size - 1; j > i; j--) {
if(comparator.compare(t[j], t[k]) < 0) k = j; // 相当于t[k]总是最小值
}
// 找出最小值后，和序列开始的值进行交换
temp = t[i];
t[i] = t[k];
t[k] = temp;
}
}
2.堆排序
根据比较类Comparator类判断是升序序列还是降序序列
若Comparator中的compare函数的返回值是 a > b ? 1 : (a < b ? -1 : 0)，则是升序序列
若compare函数的返回值是 a > b ? -1 : (a < b ? 1 : 0)，则是降序序列
堆排序的思路：
初始时把n个数的序列看成一棵顺序排列的二叉树，取出堆顶元素，然后再重新组成一棵新的二叉树
1.如何将排序序列组成一棵顺序排列的二叉树，即建立初始堆
①n个节点的完全二叉树，则最后一个节点是(int)n/2个节点的子节点
②从(int)n/2个节点为根的子树开始，使子树成为堆
③依次向前对各节点为根的子树进行筛选，使子树成为堆
④直到根节点为止，就建立了初始堆
2.取出堆顶元素后，二叉树结构已经被破坏，如何重新组成一棵新的顺序排列的二叉树
⑤取出堆顶元素，并将堆底元素送入堆顶(取巧了，将最后一个元素和堆顶元素交换)
⑥将根结点与左、右子树中较小元素的进行交换
⑦若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法⑥
⑧若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法⑥
⑨直到叶子节点为止，堆建成
时间复杂度：O(nlog2n)
空间复杂度：O(1)
public static <T> void heapSort(T[] t, Comparator<? super T> comparator) {
int size = t == null ? 0 : t.length;
/**********建立初始堆*************/
// 最后一个有孩子节点的位置 length / 2 - 1
for(int i = (size / 2 - 1); i >= 0; i--) {
adjustHeap(t, i, size, comparator);
}
/**********取出堆顶元素，并重新建立堆************/
// 从最后一个元素开始对序列进行调整
for(int i = size - 1; i > 0; i--) {
//交换堆顶元素t[0]和堆中最后一个元素
T temp = t[0];
t[0] = t[i];
t[i] = temp;
// 重新调整堆
adjustHeap(t, 0, i, comparator);
}
}
/**
* 调整t[position],根据comparator使其成为小(大)顶堆.即将对第position个结点为根的子树筛选
* @param t 待调整的堆数组
* @param position 待调整的数组元素的位置
* @param length 待调整的数组的长度
* @param comparator 比较类
* @date 2017年3月7日
*/
private static <T> void adjustHeap(T[] t, int position, int length, Comparator<? super T> comparator) {
T temp = t[position]; // 记录d待调整数组元素的值，即根节点的值
int child = 2 * position + 1; // 左孩子的位置
while(child < length) {
// 找出左孩子和右孩子中的较小(大)值
if(child + 1 < length && comparator.compare(t[child + 1], t[child]) > 0) {
child++;
}
// 如果左孩子和右孩子中的较小(大)值比根节点小(大)，则进行替换
if(comparator.compare(t[child], t[position]) > 0) {
t[position] = t[child]; // 将较小(大)值和根节点进行交换
position = child; // 重新设置position ,即待调整的下一个结点的位置
child = 2 * position + 1; // 重新设置左孩子的位置
} else {
break; // 如果当前待调整结点小(大)于它的左右孩子，则不需要调整，直接退出
}
t[position] = temp; // 将孩子节点设置成根节点
}
}
测试程序
disturbOrder(T[] t)请查看java算法-排序-交换排序
public static void main(String[] args) {
Integer[] numbers = new Integer[9999];
for(int i = 0; i < numbers.length; i++) {
numbers[i] = i;
}
disturbOrder(numbers);
long start2 = System.currentTimeMillis();
selectSort(numbers, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return a > b ? 1 : (a < b ? -1 : 0);
}
});
long end2 = System.currentTimeMillis();
System.out.println("选择排序耗时:" + (end2 - start2));
disturbOrder(numbers);
long start3 = System.currentTimeMillis();
heapSort(numbers, new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return a > b ? 1 : (a < b ? -1 : 0);
}
});
long end3 = System.currentTimeMillis();
System.out.println("堆排序耗时:" + (end3 - start3));
}