视频医疗平台网站开发上海网站设计外包

当前位置： 首页 > news >正文

视频医疗平台网站开发,上海网站设计外包,店铺推广引流的方法,项目外包 网站开发归并排序 要将一个数组排序#xff0c;可以先将它分成两半分别排序#xff0c;然后再将结果合并#xff08;归并#xff09;起来。这里的分成的两半#xff0c;每部分可以使用其他排序算法#xff0c;也可以仍然使用归并排序#xff08;递归#xff09;。 我看《算法》…归并排序 要将一个数组排序可以先将它分成两半分别排序然后再将结果合并归并起来。这里的分成的两半每部分可以使用其他排序算法也可以仍然使用归并排序递归。 我看《算法》这本书里对归并算法有两种实现一种是“自顶向下”另一种是“自底向上”。这两种方法个人认为只是前者用了递归的方法后者使用两个 for 循环模拟了递归压栈出栈的算法本质上还是相同的如果理解错误还望大佬指出。 算法步骤 1、将要排序的序列分成两部分。 2、将两部分分别各自排序。然后再将两个已经排序好的序列“归并”到一起归并后的整个序列就是有序的。 3、将两个有序的序列归并的步骤 3.1、先申请一个空间大小足够容纳两个已经排序的序列。 3.2、设定两个指针最初位置分别为两个已经排序序列的起始位置。 3.3、比较两个指针所指向的元素选择相对小的元素放入到合并空间并移动指针到下一位置。 3.4、重复3.3 步骤。 归并排序比较重要的是“分治”思想和“归并”的操作。 归并操作是将两个“有序”的序列合并成一个有序的序列的方法。而这两个有序的序列又是根据“分治”思想将一个学列分割成的两部分将一个序列不断的分隔到最后就剩一个的时候他自然就是有序的。 public class MergeSort {public static void main(String[] args) {int[] nums {12,123,432,23,1,3,6,3,-1,6,2,6};;sort(nums,0,nums.length -1);System.out.printf(finish!);}public static void sort(int[] nums,int left,int right){if(left right){return;}// 递归的将左半边排序sort(nums,left,right - left / 2 - 1); // 递归的将右半边排序sort(nums,right - left / 2 ,right);// 此时左右半边都分别各自有序再将其归并到一起。// 如[1,9,10 , 3,7,8]merge(nums,left,right - left / 2,right);}// 此方法叫做原地归并将数组 nums 根据 mid 分隔开左右看作是两个数组。// 类似于 merge(int[] nums1,int[] nums2)将 nums1 和 nums2 归并public static void merge(int[] nums ,int left,int mid,int right){int i left,j mid;int[] temp_nums new int[nums.length];for(int key left ; key right; key)// 将原来数组复制到临时数组中。temp_nums[key] nums[key];for(int key i ; key right; key){if(i mid){nums[key] temp_nums[j];} else if (j right) {nums[key] temp_nums[i];} else if (temp_nums[i] temp_nums[j]) {nums[key] temp_nums[j];}else{nums[key] tempnums[i];}}}} 快速排序 快速排序是一种分治的排序算法它将一个数组分成两个子数组将两部分独立的排序 快速排序可能是应用最广泛的排序算法了。快速排序流行的原因是它实现简单、适用于各种不同的输入数据且在一般应用中比其他排序算法都要快得多。——《算法第四版》 算法步骤 从数列中挑出一个元素称为 基准pivot;所有元素比基准值小的摆放在前面所有元素比基准值大的摆在后面相同的数可以到任一边。这个称为分区partition操作。递归地recursive使用同样的方法把小于基准值元素的子数列和大于基准值元素的子数列排序 算法过程 1、给定一个乱序的数组 [5,1,4,6,2,66,34,8]2、选择第一个为基准数此时把第一个位置置空。两个指针left从左到右找比 piovt “大”的数right 从右向左找比 piovt “小”的数。 left right| | [,1,4,6,2,66,34,8]| piovt 53、right 从右向左-找比 piovt “小”的数 2。 left right| | [,1,4,6,2,66,34,8]| piovt 54、left从左到右-找到了比 piovt 大的数 6。 left right| | [,1,4,6,2,66,34,8]| piovt 55、此时将 left 和 right 上的数对调。 left right| | [_,1,4,2,6,66,34,8]| piovt 56、right 继续向左查找直到 left right。正常情况下要重复 4、5 步骤多次才会得到 left right 此时将 left 位置的数放到原来 piovt 位置上将 piovt 放到 left 位置上。 leftright| [2,1,4,5,6,66,34,8]- -| piovt 57、此时将整个数组根据 piovt 分割成两个部分左边都比 piovt 小右边都比 piovt 大。递归的处理左右两部分。 实现 public class QuickSort {public static void main(String[] args) {int[] nums {5,1,4,6,2,66,34,8,34,534,5};int[] sorted sort(nums,0 , nums.length - 1);System.out.println(finish!);}// 排序public static int[] sort(int[] nums , int left , int right){if(left right){ // 将 nums 以 mid 分成两部分// 左边的小于 nums[min]// 右边的大于 nums[min]int mid partition(nums,left,right);// 递归sort(nums,left,mid - 1);sort(nums,mid 1 ,right);}return nums;}public static int partition(int[] nums , int left , int right){//int pivot left;int i left , j right 1; // 左右两个指针int pivot nums[left]; // 基准数比他小的放到左边比他大的放到右边。while ( true ){// 从右向左找比 pivot 小的。while (j left nums[–j] pivot){if(j left){// 到头了break;}}// 先从左向右找比 pivot 大的。while (i right nums[ i] pivot ){if( i right){// 到头了break;}}if(i j ) break;// 交换 i 位置和 j 位置上的数// 因为此时 nums[i] pivot 并且 nums[j] pivotswap(nums,i , j);}// 由于 left 位置上的数是 pivot// 此时 i j 且 nums[i/j] 左边的数都小于 pivot , nums[i/j] 右边的数都大于 pivot。// 此时交换 left 和 j 位置上的数就是将 pivot 放到中间swap(nums,left,j);return j ;}// 交换数组中两个位置上的数public static void swap(int[] nums , int i1 , int i2){int n nums[i1];nums[i1] nums[i2];nums[i2] n;}} 堆排序 堆排序主要是利用“堆”这种数据结构的特性来进行排序它本质上类似于“选择排序”。都是每次将最大值或最小值找出来放到数列尾部。不过“选择排序”需要遍历整个数列后选出最大值可以到上面再熟悉下选择排序算法“堆排序”是依靠堆这种数据结构来选出最大值。但是每次重新构建最大堆用时要比遍历整个数列要快得多。 堆排序中用到的两种堆大顶堆和小顶堆 1、大顶堆每个节点的值都大于或等于其子节点的值在堆排序算法中一般用于升序排列 2、小顶堆每个节点的值都小于或等于其子节点的值在堆排序算法中一般用于降序排列 我们给树的每个节点编号并将编号映射到数组的下标就是这样 该数组从逻辑上是一个堆结构我们用公式来描述一下堆的定义就是 1、大顶堆arr[i] arr[2i1] arr[i] arr[2i2] 2、小顶堆arr[i] arr[2i1] arr[i] arr[2i2] 这里只要求父节点大于两个子节点并没有要求左右两个子节点的大小关系。 算法过程 1、将一个 n 长的待排序序列arr [0,……,n-1]构造成一个大顶堆。 2、此时数组的 0 位置也就是堆顶就是数组的最大值了将其与数组的最后一个数交换。 3、将剩下 n-1 个数重复 1和2 操作最终会得到一个有序的序列。 堆排序是“选择排序”的一种变体算法中比较难的地方是用数组构建“大顶堆”或“小顶堆”的过程。 实现堆排序前我们要知道怎么用数组构建一个逻辑上的最大堆这里会用到几个公式假设当前节点的序号是 i可以结合上图理解下下面的公式 1、左子节点的序号就是2i 1 2、右子几点的序号就是2i 2 3、父节点的序号就是(i-1) / 2 i不为0 public class HeapSort {static int temp ;public static void main(String[] args) {int[] nums {5,1,4,6,2,66,-1,34,-9,8};sort(nums);System.out.println(finish!);}public static void sort(int[] nums){// 第一步要先将 nums 构建成最大堆。for(int i (nums.length - 1) / 2 ; i 0; i– ){//从第一个非叶子结点从下至上从右至左调整结构maxHeapify(nums,i,nums.length);}// 遍历数组// j 是需要排序的数组的最后一个索引位置。for(int j nums.length - 1 ; j 0 ; j –){// 每次都调整最大堆堆顶nums[0]与数组尾的数据位置nums[j]。swap(nums,0,j);// 重新调整最大堆maxHeapify(nums,0,j);}}/*** 将 nums 从 i 开始的 len 长度调整成最大堆。* 注意此方法只适合调整已经是最大堆但是被修改了的堆或者只有三个节点的堆* len 需要计算到数组 nums 的多长的地方。* i 父节点在的位置。*/public static void maxHeapify(int[] nums,int i , int len){// 是从左子节点开始int key 2 * i 1;if(key len){// 说明没有子节点。return;}// key 1 是右子节点的位置。if(key 1 len nums[key] nums[key 1]){// 此时说明右节点比左节点大。// 此时只要将父节点跟 右子节 点比就行了。key 1;}if(nums[i] nums[key]){// 子节点比父节点大交换子父界节点的数据将父节点设置为最大。swap(nums,i,key);// 此时子节点上的数变了就要递归的再去计算子节点是不是最大堆。maxHeapify(nums,key,len);}}/*** 交换 i 和 j 位置的数据*/public static void swap(int[] nums,int i,int j){temp nums[i];nums[i] nums[j];nums[j] temp;} }