堆排序代码：
思想：每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最小堆，依次类推，最终得到排序的序列。
import java.util.Arrays; /**
* 思路：首先要知道大顶堆和小顶堆，数组就是一个堆，每个i节点的左右孩子是2i+1和2i+2
* 有了堆，将其堆化：从(n/2)-1个元素开始向下修复，将每个节点修复为小（大）顶堆
* 修复完成后，数组具有小（大）顶堆的性质
* 按序输出：小顶堆可以对数组逆序排序，每次交换堆顶和末尾元素，对堆顶进行向下修复，这样次小元素又到堆顶了
*
* 时间复杂度：堆化：一半的元素修复，修复是单分支的，所以整体堆化为nlgn/2
* 排序：n个元素都要取出，因此调整n次，每次调整修复同上是lgn的，整体为nlgn
* 空间复杂度：不需要开辟辅助空间
* 原址排序
* 稳定性
*
*/
public class HeapSort { static void sort(int []A){
// 堆排序第一步： 先对A进行堆化
makeMinHeap(A);
for(int x = A.length-1;x>=0;x--){
// 堆排序第二步： 把堆顶，0号元素和最后一个元素对调
swap(A, 0, x);
// 堆排序第三步：缩小堆的范围，对堆顶元素进行向下调整
MinHeapFixDown(A, 0, x);
}
} static void makeMinHeap(int[] A){
int n = A.length;
for(int i = n/2-1;i>=0;i--){
MinHeapFixDown(A,i,n);
}
} private static void MinHeapFixDown(int[] A, int i, int n) {
// 找到左右孩子
int left = 2 * i + 1;
int right = 2 * i + 2 ;
// 左孩子已经越界，i就是叶子节点
if (left>=n) {
return ;
}
// min 指向了左右孩子中较小的那个
int min = left;
if (right>=n) {
min = left;
}else {
if (A[right]<A[left]) {
min = right;
}
}
// 如果A[i]比两个孩子都要小，不用调整
if (A[i]<=A[min]) {
return ;
}
// 否则，找到两个孩子中较小的，和i交换
int temp = A[i];
A[i] = A[min];
A[min] = temp;
// 小孩子那个位置的值发生了变化，i变更为小孩子那个位置，递归调整
MinHeapFixDown(A, min, n);
} private static void swap(int[] A, int p, int bigger) {
int temp = A[p];
A[p] = A[bigger];
A[bigger] = temp; } public static void main(String[] args) {
int arr[] = new int[10];
for(int i=0;i<10;i++){
arr[i] = (int) ((Math.random()+1)*10);
} System.out.println("排序前："+Arrays.toString(arr));
sort(arr);
System.out.println("排序后："+Arrays.toString(arr));
} }
堆排序结果：
计数排序代码：
import java.util.Arrays; /**
* 计数排序
* 思路：开辟新的空间，空间大小为max(source)+1
* 扫描source，将value作为辅助空间的下标，用辅助空间的该位置元素记录value的个数
* 如 9 7 5 3 1，helper的空间就为10
* 依次扫描，value为9，将helper[9]++，以此类推，完成之后，再去遍历helper
* 如果该位(index)的值为0，说明index不曾在source中出现
* 如果该位(index)的值为 1，说明出现了1次，为2说明出现了两次
* 时间复杂度：扫描一次source，扫描一次helper，复杂度为N+K
* 空间复杂度：如果source里面有个元素较大的，那么开辟的辅助空间较大
* 非原址排序
* 稳定性：相同元素不会出现交叉，非原址都是拷来拷去
* 如果要优化一下空间，可以求出minOf(source),那么helper的长度为(max-min)+1,这样就能短点
* 计数有缺陷，数据较为密集或范围较小时，适用。
*/
public class CountSort { static void sort(int []source){
int max = source[0];
for (int i = 1; i < source.length; i++) {
if (source[i]>max) {
max = source[i];
}
}
int []helper = new int[max+1];
for(int e:source){
helper[e]++;
}
int current = 0; // 数据回填的位置
for (int i = 1; i < helper.length; i++) {
while(helper[i]>0){
source[current++] = i;
helper[i]--;
}
}
} // 保证排序稳定性的版本
public static void sort2(int[] source) {
int max = source[0];
for (int i = 1; i < source.length; i++) {
if (source[i]>max) {
max = source[i];
}
}
int []helper = new int[max+1];
for (int e : source) {
helper[e]++;
}
for (int i = 1; i < helper.length; i++) {
helper[i] += helper[i - 1];
}
int len = source.length;
int[] target = new int[len];
for (int i = len - 1; i >= 0; i--) {
target[helper[source[i]] - 1] = source[i];
helper[source[i]]--;
}
System.arraycopy(target, 0, source, 0, len);
} public static void main(String[] args) {
int arr[] = new int[10];
for(int i=0;i<10;i++){
arr[i] = (int) ((Math.random()+1)*10);
}
System.out.println("排序前："+Arrays.toString(arr));
sort2(arr);
System.out.println("排序后："+Arrays.toString(arr));
} }
计数排序结果：