称多网站建设,电脑基础培训班哪里有,网站改版建设征求意见书,2022年国际十大新闻文章目录一、查找1. 无序表的顺序查找2. 折半查找3. 分块查找4. 二叉排序树BST5. 哈希表查找二、排序1. 不带哨兵的直接插入排序2. 带哨兵的直接插入排序3. 带哨兵、折半查找的直接插入排序4. 希尔排序5. 冒泡排序6. 快速排序7. 选择排序8. 堆排序9. 归并排序二叉树1. 递归先序…
文章目录一、查找1. 无序表的顺序查找2. 折半查找3. 分块查找4. 二叉排序树BST5. 哈希表查找二、排序1. 不带哨兵的直接插入排序2. 带哨兵的直接插入排序3. 带哨兵、折半查找的直接插入排序4. 希尔排序5. 冒泡排序6. 快速排序7. 选择排序8. 堆排序9. 归并排序二叉树1. 递归先序遍历2. 非递归先序遍历3. 递归中序遍历4. 非递归中序遍历5. 递归后序遍历6. 非递归后序遍历7. 广度遍历二叉树8. 深度遍历一、查找
1. 无序表的顺序查找
把待查关键字key存入表头哨兵从后向前逐个比较可免去查找过程中每一步都要检测是否查找完毕加快速度。
// 下标从1开始头节点为空
public static int sentrySearch(int[] arr, int target){arr[0] target;int index arr.length-1;while(arr[index] ! target){--index;}if(index 0) return -1;return index;
}空间复杂度O(1)时间复杂度O(n)平均查找长度ASL n1/ 2 2. 折半查找
首先将给定值key与表中中间位置的元素比较若相等则查找成功返回该元素的存储位置若不等则所需查找的元素只能在中间元素以外的前半部分或后半部分。
public static int Sort(int[] nums, int target){int low 0;int high nums.length;while(low high){mid (low high) / 2;if(target nums[mid]) return mid;if(target nums[mid]) high mid-1;if(target nums[mid]) low mid1;}return -1
}空间复杂度O(1)时间复杂度O(log2log_2log2n)平均查找长度ASL log2log_2log2n1 3. 分块查找
分块查找又称索引顺序查找它是顺序查找的一种改进方法将n个数据元素“按块有序”划分为m块mn。每一块中的数据元素不必有序但块与块之间必须“按块有序”即第1快中的任一元素的关键字都必须小于第2块中任一元素的关键字而第2块中任一元素又都小于第3块中的任一元素……
查找分两部分先对索引表进行二分查找或顺序查找以确定待查记录在哪一块中然后在已确定的快中用顺序法进行查找。
AllArgsConstructor
class IndexItem {public int index; //值比较的索引public int start; //开始位置public int length;//块元素长度(非空)
}public int indexSearch(int key){int[] mainList new int[]{22, 12, 13, 8, 9, 20, 33, 42, 44, 38, 24, 48,60, 58, 74, 49, 86, 53}IndexItem[] indexItemList new IndexItem[]{new IndexItem(22,1,6),new IndexItem(48,7,6),new IndexItem(86,13,6);}// 第一步查找在哪一块int index 0;for(;index indexItemList.length; index){if(indexItemList[index].index key ) break;} int num 0;for(int i0; iindex; i){num indexlist[i].length;}for(int inum; inumindexItemList.length; i){if(MainList[i] key) return i;}return -1;
}时间复杂度O(log(m)n/m)n个数据分成m块平均查找长度ASLASL折半查找ASL顺序查找log2log_2log2(m1) n/m1/2 4. 二叉排序树BST private static class BinaryTreeNode {int data;BinaryTree lchild;BinaryTree rchild;}public class BinarySearchTree {public static BinaryTreeNode serachBinaryTree(BinaryTreeNode btn, int key) {if (btn null) { // 树节点不存在返回return new BinaryTreeNode();} else if (key btn.data) { // 查找成功return btn;} else if (key btn.data) { // 关键字小于根节点查找左子树return serachBinaryTree(btn.lchild, key);} else { // 关键字大于根节点查找右子树return serachBinaryTree(btn.rchild, key);}}
}时间复杂度O(logn)空间复杂度O(1)平均查找长度ASL查找成功的平均查找长度、查找失败的平均查找长度 5. 哈希表查找 常用的哈希函数 直接地址法H(key)key或H(key)a*keyb除留余数法H(key) key mod p数字分析法可选取关键字的若干数位组成哈希地址原则是使得到的哈希地址尽量避免冲突。平方取中法取关键字平方后的中间几位为哈希地址 常用的处理冲突方法开发地址法有线性探查法和平方探查法链式地址法把所有的同义词用单链表链接起来的方法种方哈希表中每个单元中存放的不再是记录本身而是相应同义词单链表的头指针。 时间复杂度O(1)空间复杂度O(n) 二、排序
注意下标都是从1开始的
1. 不带哨兵的直接插入排序
public void InsertSort(int nums[]){int temp;for(int i2; inums.length; i){temp nums[i];int j i;while(nums[j]nums[j-1] j 1){nums[j] nums[j-1];}nums[j1] temp;}
}时间复杂度最差时间复杂度O(n2)、平均时间复杂度O(n2)空间复杂度O(1)稳定性稳定 2. 带哨兵的直接插入排序
public void InsertSort(int nums[]){for(int i2; inums.length; i){nums[0] nums[i];int j i;while(nums[j]nums[j-1]){nums[j] nums[j-1];}nums[j1] nums[0];}
}时间复杂度最差时间复杂度O(n2)、平均时间复杂度O(n2)空间复杂度O(1)稳定性稳定 3. 带哨兵、折半查找的直接插入排序
折半查找跟顺序查找的效率都是一样的因为将元素向后退的次数是一样的。
public void InsertSort(int nums[]){int low,high,mid;for(int i2;in;i){A[0]A[i];low1;highi-1;while(lowhigh){mid(lowhigh)/2;if(A[mid]A[0]) highmid-1; //可用A[0]也可用A[i]else lowmid1}for(int ji-1;jhigh1;--j) //注意这里只能用high不能用lowmidA[j1]A[j];A[high1]A[0];}
}时间复杂度最差时间复杂度O(n2)、平均时间复杂度O(n2)空间复杂度O(1)稳定性稳定 4. 希尔排序
先追求表中元素的部分有序再逐渐逼近全局有序。
public void ShellSort(int arr[], int gap){while(gap1){for(int i0; igap; i){for(int jigapl jarr.length; jgap){int temp arr[i];for(int k j-gap; kiarr[k]temp; k-gap){arr[kgap] arr[k];}arr[kgap] temp;}}}
}时间复杂度O(n1.3~2)空间复杂度O(1)稳定性不稳定 5. 冒泡排序
public static void BubbleSort(int nums[]){for(int i 1; i nums.length; i){boolean flag true;for(int j 0; jnums.length-i; j){if(arr[j] arr[j1]){int temp arr[j];arr[j] arr[j1];arr[j1] temp;flag false;}}if(flag) break;}
}时间复杂度最坏时间复杂度O(n2)、平均时间复杂度O(n2)空间复杂度O(1)稳定性稳定 6. 快速排序
public void quickSort(int[] nums, int left, int right){while(left right) return;int pivot a[left];int ileft;int jright;while(i j){while(pivot a[j] ij) j--;while(pivot a[i] ij) i;int temp a[i];a[i] a[j];a[j] temp;}a[left] a[i];a[i] pivot;quickSort(a,left,i-1);//对左边的子数组进行快速排序quickSort(a,i1,right);//对右边的子数组进行快速排序
}时间复杂度最差时间复杂度O(n2)、平均时间复杂度O(n2)空间复杂度O(log2n)~O(n)稳定性不稳定 7. 选择排序
public void SelectSort(int[] nums){for(int i0; inums.length; i){int temp i;for(int ji1; jnums.length; j){if(nums[j] nums[temp]) temp j;}int swap nums[i];nums[i] nums[temp];nums[temp] swap;}
}时间复杂度最差时间复杂度O(n2)、平均时间复杂度O(n2)空间复杂度O(1)稳定性稳定 8. 堆排序
堆排序分为两个过程输出堆顶、调整新堆
void HeadAdjust(int A[],int k,int len){ //调整指定根节点A[k]A[0]A[k];for(int ik*2;ilen;i*2){if(ilenA[i]A[i1]) i; //不管要不要交换先选出最大的子结点if(A[0]A[i]) break; //不用交换而且后面是一定调整好的了else{A[k]A[i]ki; //这里与A[K]A[0]相呼应其实也可以选择A[i]A[0]每次都交换}}A[k]A[0];
}void BuildMaxHeap(int A[],int len){ //从最后一个子树根节点开始调整调整全部根节点for(int ilen/2;i0;--i) HeadAdjust(A,i,len);
}void HeapSort(int A[],int len){BuildMaxHeap(A,len); //堆初始化for(ilen;i1;i--){ Swap(A[i],A[1]); //将最大值放在最后然后重新在指定位置调整HeapAdjuest(A,1,i-1) //截断最后一位并且重新从第一位调整}
}时间复杂度最差时间复杂度O(nlog2n)、平均时间复杂度O(nlog2n)空间复杂度O(1)稳定性不稳定 9. 归并排序
把两个或多个已经有序的序列合并成一个
public static int[] sort(int[] a,int low,int high){int mid (lowhigh)/2;if(lowhigh){sort(a,low,mid);sort(a,mid1,high);//左右归并merge(a,low,mid,high);}return a;}public static void merge(int[] a, int low, int mid, int high) {int[] temp new int[high-low1];int i low;int j mid1;int k0;// 把较小的数先移到新数组中while(imid jhigh){if(a[i]a[j]){temp[k] a[i];}else{temp[k] a[j];}}// 把左边剩余的数移入数组 while(imid){temp[k] a[i];}// 把右边边剩余的数移入数组while(jhigh){temp[k] a[j];}// 把新数组中的数覆盖nums数组for(int x0;xtemp.length;x){a[xlow] temp[x];}}时间复杂度最差时间复杂度O(nlog2n)、平均时间复杂度O(nlog2n)空间复杂度O(n)稳定性稳定 二叉树
1. 递归先序遍历
public static void preOrder(TreeNode root){if(root null) return;System.out.println(root.value);if(root.left ! null) PreOrder(root.left);if(root.right ! null) PreOrder(root.right);
}2. 非递归先序遍历
public static void preOrder(TreeNode root){StackTreeNode stack new StackTreeNode();while(root ! null || !stack.isEmpty()){while(root!null){ // 1. 下去的时候System.out.println(root.value); // 访问stack.push(root); // 入栈root root.left // 左孩子}if(!stack.isEmpty()){ // 2. 回来的时候root stack.pop(); // 出栈root root.right; // 右孩子}}
}3. 递归中序遍历
public static void midOrder(TreeNode root){if(root null) return;if(root.left ! null) PreOrder(root.left);System.out.println(root.value);if(root.right ! null) PreOrder(root.right);
}4. 非递归中序遍历
public static void minOrder(TreeNode root){StackTreeNode stack new StackTreeNode();while(root ! null || !stack.isEmpty()){while(root!null){ // 1. 下去的时候stack.push(root); // 入栈root root.left // 左孩子}if(!stack.isEmpty()){ // 2. 回来的时候root stack.pop(); // 出栈System.out.println(root.value); // 访问root root.right; // 右孩子}}
}5. 递归后序遍历
public static void postOrder(TreeNode root){if(root null) return;if(root.left ! null) PreOrder(root.left);if(root.right ! null) PreOrder(root.right);System.out.println(root.value);
}6. 非递归后序遍历
public void postorderTraversal(TreeNode root) {DequeTreeNode stack new LinkedListTreeNode();TreeNode prev null; // prev是指上一个遍历到的结点if (root null) return res;while (root ! null || !stack.isEmpty()) {while (root ! null) {stack.push(root);root root.left;}root stack.pop();// 要是没有右孩子或者右孩子已经看过了就打印根结点if (root.right null || root.right prev) {System.out.println(root.value);prev root; // 保留最近遍历过的一次结点root null; //这里设为null就是好好的把结点输出} // 右孩子不是空的并且上次prev没有走过的就push进栈。else{ stack.push(root);root root.right;}}
}7. 广度遍历二叉树
public static void bfs(TreeNode root){QueueTreeNode queue new LinkedListTreeNode();if(root null) return;queue.add(root);while(!queue.isEmpty()){TreeNode t queue.remove();System.out.println(root.value); if(t.left ! null) queue.add(t.left);if(t.right ! null) queue.add(t.right);}
}8. 深度遍历 public void dfs(TreeNode root){StackTreeNode stacknew StackTreeNode();if(rootnull)return list;//压入根节点stack.push(root);//然后就循环取出和压入节点直到栈为空结束循环while (!stack.isEmpty()){TreeNode tstack.pop();if(t.right!null)stack.push(t.right);if(t.left!null)stack.push(t.left);System.out.println(t.value);}
}
