排序算法
冒泡排序
简单选择排序
直接插入排序
希尔（shell）排序
快速排序
归并排序
堆排序
堆排序
堆
堆就是可以被看作一颗完全二叉树的数组对象 换句话说：堆是用数组表示的完全二叉树 将完全二叉树按照层序遍历放入数组中，就形成了堆
对应数组为 为了计算方便，从索引1开始存放。由此我们可以找到如下规律
如果一个结点的位置为k，则它的父结点的位置为[k/2]，且它的左右子结点的位置则分别为2k和2k+1。规定堆的每个结点都大于等于它的两个子结点。并没有规定两子节点的大小关系（数组长度-1）/2是分界点，他的左边全是叶子节点。
排序原理
这里做升序排序，用大顶堆
构造堆；得到堆顶元素，这个值就是最大值；交换堆顶元素和数组中的最后一个元素，此时所有元素中的最大元素已经放到合适的位置；对堆进行调整，重新让除了最后一个元素的剩余元素中的最大值放到堆顶；重复2~4这个步骤，直到堆中剩一个元素为止。
以数组[8, 4, 5, 7, 1, 3, 6, 4]为例
初始化堆
进一步排序
Java代码
import java
.util
.Arrays
;
public class HeapSort {
private static int[] arr
;
public static void sort(int[] a
){
arr
= new int[a
.length
+1];
CreateHeap(a
,arr
);
for(int i
= arr
.length
-1;i
>1;i
--){
int temp
= arr
[i
];
arr
[i
] = arr
[1];
arr
[1] = temp
;
sink(arr
,1,i
-1);
}
System
.arraycopy(arr
,1,a
,0,a
.length
);
}
private static void CreateHeap(int[] a
,int[] arr
){
System
.arraycopy(a
,0,arr
,1,a
.length
);
for(int i
= (arr
.length
-1)/2;i
>0;i
--){
sink(arr
,i
,arr
.length
-1);
}
}
private static void sink(int[] arr
,int i
,int range
){
while(2*i
<=range
){
int max
= i
*2;
if(2*i
+1<=range
){
if(arr
[2*i
+1]>arr
[2*i
]){
max
= 2*i
+1;
}
}
if(arr
[max
]>arr
[i
]){
int temp
= arr
[max
];
arr
[max
] =arr
[i
];
arr
[i
] = temp
;
}
i
= max
;
}
}
public static void main(String
[] args
) {
int[] a
= {8, 4, 5, 7, 1, 3, 6, 4, 5, 9};
sort(a
);
System
.out
.println(Arrays
.toString(a
));
}
}
算法复杂度
堆排序的时间复杂度是O(N*lgN)
假设被排序的数列中有N个数。遍历一趟的时间复杂度是O(N)，需要遍历多少次呢？ 堆排序是采用的二叉堆进行排序的，二叉堆就是一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。最多是多少呢？由于二叉堆是完全二叉树，因此，它的深度最多也不会超过lg(2N)。因此，遍历一趟的时间复杂度是O(N)，而遍历次数介于lg(N+1)和lg(2N)之间；因此得出它的时间复杂度是O(N*lgN)。
空间复杂度是O(N)，因为使用了一个辅助数组。
稳定性
不稳定 在构造完初始堆后的排序，是将堆顶元素和数组末尾元素交换，这会导致相等的数据顺序发生改变。 例：初始堆为3，3，1时，可以自己试一下
