关于华大18年专注seo服务网站制作应用开发,西安大雁塔在哪个区,陕西省建设工会网站,高端品牌网站建设案例归并排序不使用递归
使用一个变量#xff0c;使其按照1、2、4、8递增#xff0c;控制左右两边1个元素、2个元素、4个元素等元素的合并
完全二叉树
完全二叉树 要不全是满的#xff0c;要不叶子节点出现在最后一层#xff0c;只要出现了叶子节点#xff0c;后面的都是叶子…归并排序不使用递归
使用一个变量使其按照1、2、4、8递增控制左右两边1个元素、2个元素、4个元素等元素的合并
完全二叉树
完全二叉树 要不全是满的要不叶子节点出现在最后一层只要出现了叶子节点后面的都是叶子节点完全二叉树可以用数组下标从0-7来表示依据以下公式计算左节点、右节点和父节点对于任意节点 i 左节点 2*i1右节点 2*i2父节点 (i-1)/2
堆
堆完全二叉树
大根堆
在完全二叉树上每一个子树的最大值都是头节点
小根堆
在完全二叉树上每一个子树的最小值都是头节点
堆的插入和删除操作是O(logn),构建堆的操作是O(n)
堆的存储方式不是链式存储而是顺序存储。左孩子下标是 2*parent 1;右孩子下标是2 * parent2
优先队列比如最大优先队列让最大的元素出队即使最大元素不在队头他仍然是第一个出队因为它优先级最高。优先队列的底层是使用大根堆来实现的。每一次入队操作就是堆的插入操作每一次出队操作就是删除堆顶点
因为二叉堆的上浮和下沉的时间复杂度都是O(logn),因此优先队列的入队和出队的时间复杂度也是O(logn)
例子 加入元素数组下标从0到7按照输入的顺序加入到数组中没加入一个数组根据公式i-1/ 2来判定他的父节点的位置然后与父节点做比较如果大于父节点则和父节点的位置交换。每加入一个元素那么heapsize1。heapsize用于指定堆的大小。返回最大值将大根堆的最顶端和最末尾的元素相互交换然后将heapsize-1返回最顶端的数值。末尾元素移到最顶端之后需要找到它的左右两个孩子节点做比较如果有比它还大的孩子节点就进行交换。依此类推。数组扩容如果原始只分配一个字节动态加入元素进行数组扩容。那么需要logN次数的扩容最后需要拷贝N个数到扩容完成后的数组中因此代价是 N*logN如果取平均最后代价是logN
完整代码
heapsort方法适用于 将元素插入数组一个一个往里面放heapify 适用于如果将元素弹出的时候将最小的元素放在顶端看其是否下降还不是很了解 这个代码的含义
package class02;import java.util.Arrays;
import java.util.PriorityQueue;public class Code03_HeapSort {public static void heapSort(int[] arr) {if (arr null || arr.length 2) {return;}for (int i 0; i arr.length; i) { // O(N)heapInsert(arr, i); // O(logN)}// for(int i arr.length -1; i 0; i--) {// heapify(arr, i, arr.length);// }int heapSize arr.length;swap(arr, 0, --heapSize);while (heapSize 0) { // O(N)heapify(arr, 0, heapSize); // O(logN)swap(arr, 0, --heapSize); // O(1)}}// arr[0 ... index-1]已经是堆了某个数现在处在index位置往上继续移动public static void heapInsert(int[] arr, int index) {while (arr[index] arr[(index - 1) / 2]) {swap(arr, index, (index - 1) / 2);index (index - 1) / 2;}}// 某个数在index位置能否往下移动public static void heapify(int[] arr, int index, int heapSize) {int left index * 2 1; // 左孩子的下标while (left heapSize) { // 下方还有孩子的时候// 两个孩子中谁的值大把下标给largestint largest left 1 heapSize arr[left 1] arr[left] ? left 1 : left;// 父和较大的孩子之间谁的值大把下标给largestlargest arr[largest] arr[index] ? largest : index;if (largest index) {break;}swap(arr, largest, index);index largest;left index * 2 1;}}public static void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}// for testpublic static void comparator(int[] arr) {Arrays.sort(arr);}// for testpublic static int[] generateRandomArray(int maxSize, int maxValue) {int[] arr new int[(int) ((maxSize 1) * Math.random())];for (int i 0; i arr.length; i) {arr[i] (int) ((maxValue 1) * Math.random()) - (int) (maxValue * Math.random());}return arr;}// for testpublic static int[] copyArray(int[] arr) {if (arr null) {return null;}int[] res new int[arr.length];for (int i 0; i arr.length; i) {res[i] arr[i];}return res;}// for testpublic static boolean isEqual(int[] arr1, int[] arr2) {if ((arr1 null arr2 ! null) || (arr1 ! null arr2 null)) {return false;}if (arr1 null arr2 null) {return true;}if (arr1.length ! arr2.length) {return false;}for (int i 0; i arr1.length; i) {if (arr1[i] ! arr2[i]) {return false;}}return true;}// for testpublic static void printArray(int[] arr) {if (arr null) {return;}for (int i 0; i arr.length; i) {System.out.print(arr[i] );}System.out.println();}// for testpublic static void main(String[] args) {int index -1;System.out.println(index / 2);int testTime 500000;int maxSize 100;int maxValue 100;boolean succeed true;for (int i 0; i testTime; i) {int[] arr1 generateRandomArray(maxSize, maxValue);int[] arr2 copyArray(arr1);heapSort(arr1);comparator(arr2);if (!isEqual(arr1, arr2)) {succeed false;break;}}System.out.println(succeed ? Nice! : Fucking fucked!);int[] arr generateRandomArray(maxSize, maxValue);printArray(arr);heapSort(arr);printArray(arr);}}比较器的使用
实质重载比较运算符比较器可以应用在特殊标准的排序上比较器可以应用在特殊标准的排序结构上自己定义比较规则 类似 C运算符号重载比如定义一个学生结构体包含学生的名字、年龄和id通过结构的年龄的比较进行排序
堆排序的扩展题目
已知一个几乎有序的数组几乎有序是指如果将数组排好顺序的话每个元素的移动距离不超过k并且k相对于数组来说比较小。请选择一个合适的排序算法针对这个数据进行排序思路使用一个大小为 k1 的内存空间主要目的是要小根堆先将k1个元素放入申请的内存空间每次放入都需要进行一次调整此时0位置的元素是最小的元素然后将0位置元素弹出再将新的元素插入申请的空间进行调整。每弹出一个首元素再插入一个新的元素整体调整 每个数进入一次弹出一次N*logk
