话不多说！程序员必学的十大算法( 四 ) _为什么

堆排序就是把堆顶的元素与最后一个元素交换，交换之后破坏了堆的特性，我们再把堆中剩余的元素再次构成一个大顶堆，然后再把堆顶元素与最后第二个元素交换….如此往复下去，等到剩余的元素只有一个的时候，此时的数组就是有序的了。
为方便理解我还准备了动图：

文章插图
如果还是不懂的话我还给你准备了优质的文章讲解：堆排序是什么鬼？
代码如下：
1public class Head {
2 // 堆排序
3 public static int[] headSort(int[] arr) {
4 int n = arr.length;
5 //构建大顶堆
6 for (int i = (n - 2) / 2; i >= 0; i--) {
7 downAdjust(arr, i, n - 1);
8 }
9 //进行堆排序
10 for (int i = n - 1; i >= 1; i--) {
11 // 把堆顶元素与最后一个元素交换
12 int temp = arr[i];
13 arr[i] = arr[0];
14 arr[0] = temp;
15 // 把打乱的堆进行调整，恢复堆的特性
16 downAdjust(arr, 0, i - 1);
17 }
18 return arr;
19 }
20
21 //下沉操作
22 public static void downAdjust(int[] arr, int parent, int n) {
23 //临时保存要下沉的元素
24 int temp = arr[parent];
25 //定位左孩子节点的位置
26 int child = 2 * parent + 1;
27 //开始下沉
28 while (child <= n) {
29 // 如果右孩子节点比左孩子大，则定位到右孩子
30 if(child + 1 <= n && arr[child] < arr[child + 1])
31 child++;
32 // 如果孩子节点小于或等于父节点，则下沉结束
33 if (arr[child] <= temp ) break;
34 // 父节点进行下沉
35 arr[parent] = arr[child];
36 parent = child;
37 child = 2 * parent + 1;
38 }
39 arr[parent] = temp;
40 }
41}
性质：1、时间复杂度：O(nlogn) 2、空间复杂度：O(1) 3、非稳定排序 4、原地排序
8、计数排序
计数排序是一种适合于最大值和最小值的差值不是不是很大的排序。
基本思想：就是把数组元素作为数组的下标，然后用一个临时数组统计该元素出现的次数，例如 temp[i] = m, 表示元素 i 一共出现了 m 次。最后再把临时数组统计的数据从小到大汇总起来，此时汇总起来是数据是有序的。
为方便理解我还准备了动图：

文章插图
如果还是不懂的话我还给你准备了优质的文章讲解：什么是计数排序？
代码如下：
1public class Counting {
2 public static int[] countSort(int[] arr) {
3 if(arr == null || arr.length < 2) return arr;
4
5 int n = arr.length;
6 int max = arr[0];
7 // 寻找数组的最大值
8 for (int i = 1; i < n; i++) {
9 if(max < arr[i])
10 max = arr[i];
11 }
12 //创建大小为max的临时数组
13 int[] temp = new int[max + 1];
14 //统计元素i出现的次数
15 for (int i = 0; i < n; i++) {
16 temp[arr[i]]++;
17 }
18 int k = 0;
19 //把临时数组统计好的数据汇总到原数组
20 for (int i = 0; i <= max; i++) {
21 for (int j = temp[i]; j > 0; j--) {
22 arr[k++] = i;
23 }
24 }
25 return arr;
26 }
27}
性质：1、时间复杂度：O(n+k) 2、空间复杂度：O(k) 3、稳定排序 4、非原地排序
注：K表示临时数组的大小，下同
优化一下
上面的代码中，我们是根据 max 的大小来创建对应大小的数组，假如原数组只有10个元素，并且最小值为 min = 10000，最大值为 max = 10005，那我们创建 10005 + 1 大小的数组不是很吃亏，最大值与最小值的差值为 5，所以我们创建大小为6的临时数组就可以了。
也就是说，我们创建的临时数组大小 (max - min + 1)就可以了，然后在把 min作为偏移量。优化之后的代码如下所示：
1public class Counting {
2 public static int[] sort(int[] arr) {
3 if(arr == null || arr.length < 2) return arr;
4
5 int n = arr.length;
6 int min = arr[0];
7 int max = arr[0];
8 // 寻找数组的最大值与最小值
9 for (int i = 1; i < n; i++) {
10 if(max < arr[i])
11 max = arr[i];
12 if(min > arr[i])
13 min = arr[i];
14 }
15 int d = max - min + 1;
16 //创建大小为max的临时数组
17 int[] temp = new int[d];
18 //统计元素i出现的次数
19 for (int i = 0; i < n; i++) {
20 temp[arr[i] - min]++;
21 }
22 int k = 0;
23 //把临时数组统计好的数据汇总到原数组
24 for (int i = 0; i < d; i++) {