江苏龙网

  1. 首页 > 资讯 > 科技 > >

排序算法|面试官：手撕十大排序算法，你会几种？( 四 )


堆排序（Heap Sort）堆排序是指利用堆这种数据结构所设计的一种排序算法 。 堆积是一个近似完全二叉树的结构 ， 并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点 。 堆排序可以说是一种利用堆的概念来排序的选择排序 。 分为两种方法：

  • 大顶堆：每个节点的值都大于或等于其子节点的值 ， 在堆排序算法中用于升序排列；
  • 小顶堆：每个节点的值都小于或等于其子节点的值 ， 在堆排序算法中用于降序排列；
堆排序的平均时间复杂度为 O(n log n) 。
（1）算法步骤
步骤1：将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆 ， 此堆为初始的无序区；步骤2：将堆顶元素R[1]与最后一个元素R[n]交换 ， 此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]&lt=R[n]；步骤3：由于交换后新的堆顶R[1]可能违反堆的性质 ， 因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆 ， 然后再次将R[1]与无序区最后一个元素交换 ， 得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn) 。 不断重复此过程直到有序区的元素个数为n-1 ， 则整个排序过程完成；
（2）过程演示
排序算法|面试官：手撕十大排序算法，你会几种？
本文插图

（3）代码实现

public class HeapSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝 ， 不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length) int len = arr.length buildMaxHeap(arr, len) for (int i = len - 1 i &gt 0 i--) { swap(arr, 0, i) len-- heapify(arr, 0, len) } return arr } private void buildMaxHeap(int[] arr, int len) { for (int i = (int) Math.floor(len / 2) i &gt= 0 i--) { heapify(arr, i, len) } } private void heapify(int[] arr, int i, int len) { int left = 2 * i + 1 int right = 2 * i + 2 int largest = i if (left &lt len &amp&amp arr[left] &gt arr[largest]) { largest = left } if (right &lt len &amp&amp arr[right] &gt arr[largest]) { largest = right } if (largest != i) { swap(arr, i, largest) heapify(arr, largest, len) } } private void swap(int[] arr, int i, int j) { int temp = arr[i] arr[i] = arr[j] arr[j] = temp }}
计数排序（Counting Sort） 计数排序 的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中 。 作为一种线性时间复杂度的排序 ， 计数排序要求输入的数据必须是有确定范围的整数 。

计数排序是一种稳定的排序算法 。 计数排序使用一个额外的数组C ， 其中第i个元素是待排序数组A中值等于i的元素的个数 。 然后根据数组C来将A中的元素排到正确的位置 。 它只能对整数进行排序 。
（1）算法步骤
步骤1：找出待排序的数组中最大和最小的元素；步骤2：统计数组中每个值为i的元素出现的次数 ， 存入数组C的第i项；步骤3：对所有的计数累加（从C中的第一个元素开始 ， 每一项和前一项相加）；步骤4：反向填充目标数组：将每个元素i放在新数组的第C(i)项 ， 每放一个元素就将C(i)减去1；
（2）过程演示
排序算法|面试官：手撕十大排序算法，你会几种？
本文插图

（3）代码实现

public class CountingSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝 ， 不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length) int maxValue = http://news.hoteastday.com/a/getMaxValue(arr) return countingSort(arr, maxValue) } private int[] countingSort(int[] arr, int maxValue) { int bucketLen = maxValue + 1 int[] bucket = new int[bucketLen] for (int value : arr) { bucket[value]++ } int sortedIndex = 0 for (int j = 0 j < bucketLen j++) { while (bucket[j] > 0) { arr[sortedIndex++] = j bucket[j]-- } } return arr } private int getMaxValue(int[] arr) { int maxValue = arr[0] for (int value : arr) { if (maxValue < value) { maxValue = value } } return maxValue }}


推荐阅读


上一篇：青年|红萝卜生产用上无人机械

下一篇：老王撩机|华为Mate40“PK”iPhone12，2020年下半年最强王者之争