SpringCloudSpringBootuniappvueb2b2c微服务多商家入驻直播带货商城分销商城秒杀高并发电商之堆排序

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

推荐分布式微服务电商源码

1. 大顶堆&＃xff1a;每个节点的值都大于或等于其子节点的值&＃xff0c;在堆排序算法中用于升序排列&＃xff1b;
2. 小顶堆&＃xff1a;每个节点的值都小于或等于其子节点的值&＃xff0c;在堆排序算法中用于降序排列&＃xff1b;

堆排序的平均时间复杂度为 Ο(nlogn)。

1. 算法步骤

1. 创建一个堆 H[0……n-1]&＃xff1b;

2. 把堆首&＃xff08;最大值&＃xff09;和堆尾互换&＃xff1b;

3. 把堆的尺寸缩小 1&＃xff0c;并调用 shift_down(0)&＃xff0c;目的是把新的数组顶端数据调整到相应位置&＃xff1b;

4. 重复步骤 2&＃xff0c;直到堆的尺寸为 1。

2. 动图演示

代码实现

Javascript

实例

var len;    // 因为声明的多个函数都需要数据长度&＃xff0c;所以把len设置成为全局变量function buildMaxHeap(arr) {   // 建立大顶堆len &＃61; arr.length;for (var i &＃61; Math.floor(len/2); i >&＃61; 0; i--) {heapify(arr, i);}
}function heapify(arr, i) {     // 堆调整var left &＃61; 2 * i &＃43; 1,right &＃61; 2 * i &＃43; 2,largest &＃61; i;if (left < len && arr[left] > arr[largest]) {largest &＃61; left;}if (right < len && arr[right] > arr[largest]) {largest &＃61; right;}if (largest !&＃61; i) {swap(arr, i, largest);heapify(arr, largest);}
}function swap(arr, i, j) {var temp &＃61; arr[i];arr[i] &＃61; arr[j];arr[j] &＃61; temp;
}function heapSort(arr) {buildMaxHeap(arr);for (var i &＃61; arr.length-1; i > 0; i--) {swap(arr, 0, i);len--;heapify(arr, 0);}return arr;
}

Java

实例

public class HeapSort implements IArraySort {&＃64;Overridepublic int[] sort(int[] sourceArray) throws Exception {// 对 arr 进行拷贝&＃xff0c;不改变参数内容int[] arr &＃61; Arrays.copyOf(sourceArray, sourceArray.length);int len &＃61; arr.length;buildMaxHeap(arr, len);for (int i &＃61; len - 1; i > 0; i--) {swap(arr, 0, i);len--;heapify(arr, 0, len);}return arr;}private void buildMaxHeap(int[] arr, int len) {for (int i &＃61; (int) Math.floor(len / 2); i >&＃61; 0; i--) {heapify(arr, i, len);}}private void heapify(int[] arr, int i, int len) {int left &＃61; 2 * i &＃43; 1;int right &＃61; 2 * i &＃43; 2;int largest &＃61; i;if (left < len && arr[left] > arr[largest]) {largest &＃61; left;}if (right < len && arr[right] > arr[largest]) {largest &＃61; right;}if (largest !&＃61; i) {swap(arr, i, largest);heapify(arr, largest, len);}}private void swap(int[] arr, int i, int j) {int temp &＃61; arr[i];arr[i] &＃61; arr[j];arr[j] &＃61; temp;}}