常用算法模板

一、排序

1.快排

void quick_sort(int q[], int l, int r) { if(l>=r) return; int i = l-1, j=r+1, x=q[l+r>>1]; while(i<j) { do i++; while(q[i]<x); do j--; while(q[j]>x); if(i<j) swap(q[i], q[j]); } quick_sort(q, l, j), quick_sort(q, j+1, r); }

补充：快速选择算法（用于快速查找数组中第k大（小）的元素）

int quick_select(vector<int>& q, int l, int r, int k) { if(l>=r) return q[l]; int x=q[(l+r)>>1], i=l-1, j=r+1; while(i<j) { do i++; while(q[i]>x);//如果题目改成最小的第k个元素改变一下符号即可 do j--; while(q[j]<x); if(i<j) swap(q[i], q[j]); } if(j-l+1>=k) return quick_select(q, l, j, k); //判断是不是已经有k个数字大于基准了 else return quick_select(q, j+1, r, k-(j-l+1));//如果取后半部分，注意对于后面的k值已经改变了 } int findKthLargest(vector<int>& nums, int k) { return quick_select(nums, 0, nums.size()-1, k); }

2.标准库中的排序

sort方法包含头文件, sort(first_pointer, first_pointer+n, cmp)。

1).定义比较函数

int A[100]; bool cmp1(int a,int b)//int为数组数据类型 { return a>b;//降序排列 //return a<b;//默认的升序排列 } sort(A,A+100,cmp1);

2).更懒的方法

functional提供了一堆基于模板的比较函数对象，它们是：equal_to、not_equal_to、greater、greater_equal、less、less_equal。

//简单使用方法 sort(A,A+100,greater<int>());//降序排列 sort(A,A+100,less<int>());//升序排列

二、二分查找

1.整数二分

int binary_search(int[] nums, int target) { int left = 0, right = nums.length - 1; while(left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if(nums[mid] == target) { // 直接返回 return mid; } } // 直接返回 return -1; } int left_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { // 别返回，锁定左侧边界 right = mid - 1; } } // 最后要检查 left 越界的情况 if (left >= nums.length || nums[left] != target) return -1; return left; } int right_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { // 别返回，锁定右侧边界 left = mid + 1; } } // 最后要检查 right 越界的情况 if (right < 0 || nums[right] != target) return -1; return right; } 作者：labuladong 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/solution/er-fen-cha-zhao-suan-fa-xi-jie-xiang-jie-by-labula/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

三、二叉树遍历

1. 递归

1). 先序

void _PreOrder(PNode& pRoot) { if (pRoot) { cout << pRoot->_data << " "; //优先输出父节点 _PreOrder(pRoot->_LChild); _PreOrder(pRoot->_RChild); } } void PreOrder() { _PreOrder(_pRoot); cout << endl; }

2).中序

void _InOrder(PNode& pRoot) { if (pRoot) { _InOrder(pRoot->_LChild); //优先对左孩子递归 cout << pRoot->_data << " "; _InOrder(pRoot->_RChild); } } void InOrder() { _InOrder(_pRoot); cout << endl; }

3).后序

void _PostOrder(PNode& pRoot) { if (pRoot) { _PostOrder(pRoot->_LChild); //优先对子节点递归 _PostOrder(pRoot->_RChild); cout << pRoot->_data << " "; } } void PostOrder() { _PostOrder(_pRoot); cout << endl; }