堆排序代码：

　　思想：每次都取堆顶的元素，将其放在序列最后面，然后将剩余的元素重新调整为最小堆，依次类推，最终得到排序的序列。

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]

堆排序结果：

　　

计数排序代码：

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));    }}

计数排序结果：