堆排序
选择排序的基本思想是：每一趟（例如第i趟）在后面的 n-i+1 个待排序元素中选取关键字最小的元素，作为有序子序列的第i个元素，直到第 n-1 趟做完，待排序元素只剩下一个，就不用再选了。这里主要讲简单选择排序和堆排序（重点，面试中问到过）
一、简单选择排序
基本思想：假设排序表为 L[1....n] ，第i趟排序即从L[i,,,,n] 中选择关键字最小的元素与 L(i) 交换，每一趟排序可以确定一个元素的最终位置，这样经过 n-1 趟排序就可以使整个排序表有序。
public class SelectSort {
public void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i; // 记录最小元素位置
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j; // 更换最小元素位置
}
}
if (min != i) {
swap(arr, i, min); // 与第i个位置进行交换
}
}
}
private void swap(int[] arr, int i, int min) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
@Test
public void test() {
int[] arr = new int[] { 1, 10, 3, 8, 6, 7, 9 };
selectSort(arr);
System.out.println(Arrays.toString(arr));
}
}
空间效率为O(1)
元素移动次数很少，当表有序时移动次数为0，但比较的次数与表的次序无关，所以时间复杂度始终为O(n2)
不稳定的算法
二、堆排序
堆排序是一种树形选择排序方法，他的特点是：在排序过程中，将 L[1....n] 看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（最小）的元素。
堆的定义：n 个关键字序列 L[1...n] 称为堆，当且仅当该序列满足：
1、 L( i ) <= L( 2i ) 且 L( i ) <= L( 2i + 1) 或者 2、 L( i ) >= L( 2i ) 且 L( i ) >= L( 2i + 1) 其中 1 <= i <= n/2
满足第一种情况的堆称为小根堆（小顶堆） ，满足第二种情况的堆称为大根堆（大顶堆） 。显然，在大根堆中，最大元素存放在根节点中，且对任一非根结点，他的值小于或者等于双亲结点的值。小根堆的定义刚好相反，根结点是最小元素。堆经常被用来实现优先级队列。
大根堆示意图
堆排序的关键是构造初始堆，对初始序列建堆，就是一个反复筛选的过程。n 个结点的完全二叉树，最后一个结点是第 n/2 个结点的孩子。对第 n/2 个结点为根的子树进行筛选（对于大根堆：若根结点的关键字小于左右子女结点中关键字较大者，则交换），使该子树成为堆。之后向前依次对各结点为根的子树进行筛选，看该结点值是否大于其左右子节点的值，若不是，将左右子节点中较大值与之交换，交换之后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该节点为根的子树构成堆为止。反复利用上述调整堆的方法建堆，直到根节点。
自下往上逐步调整为大根堆
建立大根堆的算法 ，
public void buildMaxHeap(int[] arr, int len) {
// n个结点完全二叉树，最后一个节点是第n/2个节点的孩子
int mid = len;
for (int i = mid-1; i >= 0 ; i--) {
adjustDown(arr, i, len);
}
}
public void adjustDown(int[] arr, int k, int length) {
int temp = arr[k];
for (int i = 2*k+1; i <= length; i=i*2+1) {
if(i<length-1 && arr[i] < arr[i+1]) {
i++;
}
if(temp >= arr[i]) {
break;
}else {
arr[k] = arr[i];
k = i;
}
}
arr[k] = temp;
}
向下调整的时间与树的高度有关，为O( h )， 在元素个数为 n 的序列上建堆，其时间的复杂度为 O( n )，说明可以在线性时间内，将一个无序数组建成一个大顶堆。
public class HeapSort {
public void buildMaxHeap(int[] arr, int len) {
// n个结点完全二叉树，最后一个节点是第n/2个节点的孩子
int mid = len;
for (int i = mid-1; i >= 0 ; i--) {
adjustDown(arr, i, len);
}
}
public void adjustDown(int[] arr, int k, int length) {
int temp = arr[k];
for (int i = 2*k+1; i <= length; i=i*2+1) {
if(i<length-1 && arr[i] < arr[i+1]) {
i++;
}
if(temp >= arr[i]) {
break;
}else {
arr[k] = arr[i];
k = i;
}
}
arr[k] = temp;
}
@Test
public void test() {
int[] arr = new int[]{53, 17, 78, 9, 45, 65, 87, 32};
buildMaxHeap(arr, arr.length);
System.out.println(Arrays.toString(arr));
for (int i = arr.length-1; i > 0; i--) {
swap(arr, i);
// System.out.println(Arrays.toString(arr));
adjustDown(arr, 0, i-1);
}
System.out.println(Arrays.toString(arr));
}
private void swap(int[] arr, int i) {
int temp = arr[i];
arr[i] = arr[0];
arr[0] = temp;
}
}
* 空间复杂度：O(1)
* 时间复杂度：O(nlog2n)
* 不稳定的
相关阅读
堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。 算法分析 在学习堆排序之前我们要先
直接选择排序：思路（按升序）：第一轮要在位置0找到最小的元素，所以0要与（0+1）~length-1挨个比；第二轮要在位置1找到第二小的元素，所以1要与（1+