临沂做网站需要多少钱,wordpress分类信息导航,威海做网站优化,七牛云cdn配置wordpress目录
1、请简述数据结构八大排序算法的思路。
2、常用排序算法手写
冒泡排序#xff1a;
选择排序#xff1a;
快速排序#xff1a;
归并排序#xff1a;
堆排序#xff1a;
3、额外再加一个二分查找吧 1、请简述数据结构八大排序算法的思路。
冒泡排序#xff…目录
1、请简述数据结构八大排序算法的思路。
2、常用排序算法手写
冒泡排序
选择排序
快速排序
归并排序
堆排序
3、额外再加一个二分查找吧 1、请简述数据结构八大排序算法的思路。
冒泡排序将相邻元素之间的比较和交换使得每一轮比较后最大的元素能够到达数组的末尾。重复这个过程直到整个数组有序。
选择排序在每一轮中找到数组中最小的元素并将其与当前轮的第一个元素交换位置。重复这一操作使得每一轮过后都有一个元素被放到了正确的位置上。
插入排序将数组分为已排序部分和未排序部分每次从未排序部分取出一个元素插入到已排序部分的正确位置上。
希尔排序首先确定一个间隔序列按此间隔将数组元素分组并进行插入排序。随后逐渐缩小间隔并重复排序过程直到间隔为1。
快速排序选一个基准元素通过一趟排序将整体数据分割成两部分基准元素左边的数据比基准元素小右边的数据比基准元素大然后再按此方法对这两部分数据分别进行快速排序递归进行直至完成。
归并排序先将数组分成两半分别对这两半进行排序然后将它们合并成一个有序数组。重复递归这一操作直至数组有序
堆排序将待排序的序列构造成一个大顶堆此时整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换此时末尾就为最大值。然后将剩余n-1个序列重新构造成一个堆这样会得到n个元素中的次大值。重复以上操作。
计数排序对输入数据中的每个元素进行计数确定每个元素出现的次数然后利用计数结果将元素放到输出序列的正确位置上。
2、常用排序算法手写
冒泡排序
将相邻元素之间的比较和交换使得每一轮比较后最大的元素能够到达数组的末尾。重复这个过程直到整个数组有序。时间复杂度On^2
代码
public static void sort(int[] arr) {for(int j0;jarr.length;j) {for(int i0;iarr.length-1-j;i) {if(arr[i]arr[i1]) {int temparr[i];arr[i] arr[i1];arr[i1]temp;}}}}
选择排序
在每一轮中找到数组中最小的元素并将其与当前轮的第一个元素交换位置。重复这一操作使得每一轮过后都有一个元素被放到了正确的位置上。 时间复杂度Onlogn
代码
public static void simpleswap(int[] arr) {for(int i0; iarr.length; i) { //负责遍历索引int index i ;//index负责找最小的索引for(int ji1; jarr.length; j) { //负责找剩余元素中的最小值if(arr[j]arr[index]) {index j;}}//每找到一次就与前面的交换一次if(i ! index){int temp arr[index];arr[index] arr[i];arr[i] temp;}}
}
快速排序
选一个基准元素通过一趟排序将整体数据分割成两部分基准元素左边的数据比基准元素小右边的数据比基准元素大然后再按此方法对这两部分数据分别进行快速排序递归进行直至完成。
时间复杂度Onlogn
代码
public static void quicksort(int[] arr,int left,int right) {//递归出口if(leftright) {return;}//定义变量保存基准数int basearr[left];//定义j游标指向最右边int jright;//定义i游标指向最左边int ileft;while(i!j) {//j从后往前找比基准数小的while(arr[j]baseij) {j--;}//i从前往后找比基准数大的while(arr[i]baseij) {i;}//i、j两数都停下交换位置int temparr[i];arr[i]arr[j];arr[j]temp;}//i和j相等跳出循环//交换基数和ij相遇位置的数据arr[left]arr[i];arr[i]base;//排序基准数的左边quicksort(arr,left,i-1);//排序基准数的右边quicksort(arr,i1,right);}
归并排序
先将数组分成两半分别对这两半进行排序然后将它们合并成一个有序数组。重复递归这一操作直至数组有序。时间复杂度Onlogn
底层逻辑先拆分拆到不能再拆分然后进行合并合并的时候进行排序 代码
public class MergeSort {public static void main(String[] args) {int[] nums new int[] { 9, 8, 7, 6, 5, 4, 3, 2, 10 };int[] newNums mergeSort(nums, 0, nums.length - 1);System.out.println(Arrays.toString(newNums));}public static int[] mergeSort(int[] nums, int left, int right) {if (left right)//已经拆分彻底拆分递归的终止条件return new int[] { nums[left] };//拆分int mid left (right - left) / 2;int[] leftArr mergeSort(nums, left, mid); //左有序数组int[] rightArr mergeSort(nums, mid 1, right); //右有序数组int[] newNum new int[leftArr.length rightArr.length]; //新有序数组//合并将拆分的数按大小放到新有序数组里面int m 0, i 0, j 0;while (i leftArr.length j rightArr.length) {newNum[m] leftArr[i] rightArr[j] ? leftArr[i] : rightArr[j];}while (i leftArr.length)newNum[m] leftArr[i];while (j rightArr.length)newNum[m] rightArr[j];return newNum;}
}
堆排序
利用完全二叉树构建大顶堆此时整个序列的最大值就是堆顶的根节点。
将堆顶元素与堆底元素进行交换此时堆底元素就为最大值。
然后将剩余n-1个序列重新构造成一个大顶堆。重复以上操作。
时间复杂度Onlogn
大顶堆父节点的值大于等于其左右孩子的值 等价于 arr[i]arr[2i1] arr[i]arr[2i2]
流程图示 构建大顶堆 堆顶元素与堆底元素交换堆底元素不再参与构建剩下的再次重新构建大顶堆、交换
这一次重新构建时直接让parent指向堆顶元素再判断即可 java代码 public class 堆排序 {public static void main(String[] args) {// TODO Auto-generated method stubint[] arr {5,7,4,2,0,3,1,6};//1、构建大顶堆for(int iarr.length-1;i0;i--) {//从下往上每个节点以此判断为大顶堆从length-1节点到0节点adjust(arr,i,arr.length);}System.out.println(Arrays.toString(arr));//输出第一次构建的大顶堆//2、堆顶堆底元素交换,除堆底外其余元素继续构建大顶堆for(int jarr.length-1;j0;j--) {int temparr[j];arr[j]arr[0];arr[0]temp;//System.out.println(Arrays.toString(arr));//剩余元素继续构建大顶堆adjust(arr,0,j);//parent游标直接指向堆顶元素即可最后一个元素不再参与构建//System.out.println(Arrays.toString(arr));}System.out.println(Arrays.toString(arr));}public static void adjust(int[] arr,int parent,int length) {int child parent*21;//定义左孩子while(childlength) {//如果有孩子节点int rchildchild1;//定义右孩子//这部分单纯为了让child指向最大childif(rchildlength arr[child]arr[rchild]) {//如果有右孩子且右孩子比较大child;//child指向较大的孩子节点(右孩子节点)}//如果父节点小于其孩子节点if(arr[parent]arr[child]) {int temparr[parent];arr[parent]arr[child];arr[child]temp;//父子结点交换后parent指向childparentchild;child2*parent1;//再次进行循环比较}else {//如果该parent没有孩子节点或者父节点大于孩子节点直接返回此节点判断完毕break;}}}}3、额外再加一个二分查找吧
时间复杂度Ologn
代码
public class 二分查找 {public static void main(String[] args) {// TODO Auto-generated method stubint[] arr {3,45,56,57,67,88};System.out.println(search(arr,11));}public static int search(int[] arr,int target) {int left 0;int right arr.length-1;while(leftright) {int middle (leftright)/2;if(targetarr[middle]) {System.out.println(找到了);return middle;}else if(targetarr[middle]){rightmiddle-1;}else {leftmiddle1;}}System.out.println(没有这个数据);return -1;}}
