常见算法 谁践踏了优雅 2022-11-05 12:59 73阅读 0赞 ## 常见排序算法 ## ### 冒泡排序 ### public class BubbleSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝,不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); for (int i = 1; i < arr.length; i++) { // 设定一个标记,若为true,则表示此次循环没有进行交换,也就是待排序列已经有序,排序已经完成。 boolean flag = true; for (int j = 0; j < arr.length - i; j++) { if (arr[j] > arr[j + 1]) { int tmp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = tmp; flag = false; } } if (flag) { break; } } return arr; } } ### 选择排序 ### public class SelectionSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); // 总共要经过 N-1 轮比较 for (int i = 0; i < arr.length - 1; i++) { int min = i; // 每轮需要比较的次数 N-i for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[min]) { // 记录目前能找到的最小值元素的下标 min = j; } } // 将找到的最小值和i位置所在的值进行交换 if (i != min) { int tmp = arr[i]; arr[i] = arr[min]; arr[min] = tmp; } } return arr; } } ### 插入排序 ### public class InsertSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝,不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); // 从下标为1的元素开始选择合适的位置插入,因为下标为0的只有一个元素,默认是有序的 for (int i = 1; i < arr.length; i++) { // 记录要插入的数据 int tmp = arr[i]; // 从已经排序的序列最右边的开始比较,找到比其小的数 int j = i; while (j > 0 && tmp < arr[j - 1]) { arr[j] = arr[j - 1]; j--; } // 存在比其小的数,插入 if (j != i) { arr[j] = tmp; } } return arr; } } ### 快速排序 ### ###### 实现一 ###### public class QuickSort implements IArraySort { @Override public int[] sort(int[] sourceArray) throws Exception { // 对 arr 进行拷贝,不改变参数内容 int[] arr = Arrays.copyOf(sourceArray, sourceArray.length); return quickSort(arr, 0, arr.length - 1); } private int[] quickSort(int[] arr, int left, int right) { if (left < right) { int partitionIndex = partition(arr, left, right); quickSort(arr, left, partitionIndex - 1); quickSort(arr, partitionIndex + 1, right); } return arr; } private int partition(int[] arr, int left, int right) { // 设定基准值(pivot) int pivot = left; int index = pivot + 1; for (int i = index; i <= right; i++) { if (arr[i] < arr[pivot]) { swap(arr, i, index); index++; } } swap(arr, pivot, index - 1); return index - 1; } private void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } ###### 实现二 ###### public static int[] qsort(int arr[],int start,int end) { int pivot = arr[start]; int i = start; int j = end; while (i<j) { while ((i<j)&&(arr[j]>pivot)) { j--; } while ((i<j)&&(arr[i]<pivot)) { i++; } if ((arr[i]==arr[j])&&(i<j)) { i++; } else { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } if (i-1>start) arr=qsort(arr,start,i-1); if (j+1<end) arr=qsort(arr,j+1,end); return (arr); } public static void main(String[] args) { int arr[] = new int[]{ 3,3,3,7,9,122344,4656,34,34,4656,5,6,7,8,9,343,57765,23,12321}; int len = arr.length-1; arr=qsort(arr,0,len); for (int i:arr) { System.out.print(i+"\t"); } } /*//方式二*/ 更高效点的代码:(TextendsComparable和SortUtil都是自己封装的类,里面重写和实现了compareTo和swap方法) public <TextendsComparable<?superT>> T[] quickSort(T[] targetArr,int start,int end) { inti=start+1,j=end; T key=targetArr[start]; SortUtil<T> sUtil=new SortUtil<T>(); if(start==end)return(targetArr); /*从i++和j--两个方向搜索不满足条件的值并交换 * *条件为:i++方向小于key,j--方向大于key */ while(true) { while(targetArr[j].compareTo(key)>0)j--; while(targetArr[i].compareTo(key)<0&&i<j)i++; if(i>=j)break; sUtil.swap(targetArr,i,j); if(targetArr[i]==key) { j--; }else{ i++; } } /*关键数据放到‘中间’*/ sUtil.swap(targetArr,start,j); if(start<i-1) { this.quickSort(targetArr,start,i-1); } if(j+1<end) { this.quickSort(targetArr,j+1,end); } returntargetArr; } /*//方式三:减少交换次数,提高效率/*/ private<TextendsComparable<?superT>> voidquickSort(T[]targetArr,intstart,intend) { inti=start,j=end; Tkey=targetArr[start]; while(i<j) { /*按j--方向遍历目标数组,直到比key小的值为止*/ while(j>i&&targetArr[j].compareTo(key)>=0) { j--; } if(i<j) { /*targetArr[i]已经保存在key中,可将后面的数填入*/ targetArr[i]=targetArr[j]; i++; } /*按i++方向遍历目标数组,直到比key大的值为止*/ while(i<j&&targetArr[i].compareTo(key)<=0) /*此处一定要小于等于零,假设数组之内有一亿个1,0交替出现的话,而key的值又恰巧是1的话,那么这个小于等于的作用就会使下面的if语句少执行一亿次。*/ { i++; } if(i<j) { /*targetArr[j]已保存在targetArr[i]中,可将前面的值填入*/ targetArr[j]=targetArr[i]; j--; } } /*此时i==j*/ targetArr[i]=key;//应加判断 /*递归调用,把key前面的完成排序*/ this.quickSort(targetArr,start,i-1); /*递归调用,把key后面的完成排序*/ this.quickSort(targetArr,j+1,end); //两个递归应加判断 } ## 常见链表问题 ## ### 删除链表倒数第N个元素,并返回头结点 ### /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode dummy = new ListNode(0); dummy.next = head; ListNode first = dummy; ListNode second = dummy; // Advances first pointer so that the gap between first and second is n nodes apart for (int i = 1; i <= n + 1; i++) { first = first.next; } // Move first to the end, maintaining the gap while (first != null) { first = first.next; second = second.next; } second.next = second.next.next; return dummy.next; } } ### 环形链表 ### /** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public boolean hasCycle(ListNode head) { if (head == null || head.next == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (slow != fast) { if (fast == null || fast.next == null) { return false; } slow = slow.next; fast = fast.next.next; } return true; } } ## 二叉树 ## ### 二叉树的最大深度 ### > 本题思路:采用递归+广度优先搜索的方式进行求解。 > 步骤一:构建递归函数(局部变量存储每一层的节点list) > 步骤二:依取list的值,将新的子节点的值添加到newlist中,并返回+1. > 步骤三:开始新的递归函数(newlist),直到newlist为空,则返回总计数。 public class Solution { public int maxDepth(TreeNode root) { if(root == null) { return 0; } List<TreeNode> list = new ArrayList<TreeNode>(); list.add(root); int result = tree(list); return result; } public int tree(List<TreeNode> list) { if(list.size() == 0) { return 0; } List<TreeNode> dataList = new ArrayList<TreeNode>(); for(int i = 0;i < list.size();i++) { TreeNode tempNode = list.get(i); if(tempNode.left != null) { dataList.add(tempNode.left); } if(tempNode.right != null) { dataList.add(tempNode.right); } } return tree(dataList) + 1; } } ## 滑动窗口 ## ### 无重复字符的字长子串 ### public class Solution { public static int lengthOfLongestSubstring(String s) { int n = s.length(); Set<Character> set = new HashSet<>(); int result = 0, index = 0, move = 0; while (index < n && move < n) { //charAt:返回指定位置处的字符 if (!set.contains(s.charAt(move))) { set.add(s.charAt(move)); j++; result = Math.max(result, move - index); } else { set.remove(s.charAt(index)); index++; } } return result; } }
相关 常见算法 常见排序算法 冒泡排序 public class BubbleSort implements IArraySort { @Ove 谁践踏了优雅/ 2022年11月05日 12:59/ 0 赞/ 74 阅读
相关 常见排序算法 注:点进链接查看算法具体实现!!! -------------------- 插入排序 [直接插入排序][Link 1] [希尔排序][Link 2] - 怼烎@/ 2022年06月16日 09:10/ 0 赞/ 157 阅读
相关 常见排序算法 常见排序: ![这里写图片描述][SouthEast] 1、直接插入排序 在给定数组中,拿出一个数M,与前面的数相比较,如果M大于前面的数,位置不变,如果小于前面的 迷南。/ 2022年06月05日 05:51/ 0 赞/ 196 阅读
相关 常见加密算法及常见加密算法原理 加密算法和协议 对称加密 简介:加密和解密使用同一个密钥 常见的算法: \- DES:Data Encryption Standard; \- 3DES: 逃离我推掉我的手/ 2022年05月17日 09:44/ 0 赞/ 309 阅读
相关 常见排序算法 常见排序算法 排序问题作为算法基础的重要组成部分,代码实现方式多种多样,但其原理是基本一致的。常见的排序算法有: ①. 冒泡排序 ②. 选择排序 ③. 插入排序 偏执的太偏执、/ 2022年05月16日 07:28/ 0 赞/ 226 阅读
相关 php 常见算法 > 许多人都说 算法是程序的核心,一个程序的好于差,关键是这个程序算法的优劣。作为一个初级phper,虽然很少接触到算法方面的东西 。但是对于冒泡排序,插入排序,选择排序,快速 叁歲伎倆/ 2022年03月19日 03:54/ 0 赞/ 119 阅读
相关 常见排序算法 今天实在不想刷笔试题就把常见的排序手敲了一遍 -------------------- 1.选择排序 class ChoiceSort<T extends 约定不等于承诺〃/ 2022年01月15日 13:35/ 0 赞/ 227 阅读
相关 常见排序算法 稳定排序:假设在待排序的文件中,存在两个或两个以上的记录具有相同的关键字,在用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法是稳定的。(即原本a在b 墨蓝/ 2022年01月06日 03:01/ 0 赞/ 246 阅读
还没有评论,来说两句吧...