面试官让你手撸代码，那这些基础，你必须掌握
冒泡排序
void swap(int array[], int i, int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } void BubbleSort1(int array[], int n) { for (int i = 0; i < n-1; i++) { for (int j = i + 1; j < n-1; j++) { if (array[i]>=array[j]) swap(array, j, i); //每次i后面的元素比array[i]小就交换。 } } }
快速排序
void quickSort(int s[], int l, int r) { if (l< r) { int i = l, j = r, x = s[l]; while (i < j) { while(i < j && s[j]>= x) // 从右向左找第一个小于x的数 j--; if(i < j) s[i++] = s[j]; while(i < j && s[i]< x) // 从左向右找第一个大于等于x的数 i++; if(i < j) s[j--] = s[i]; } s[i] = x; quickSort(s, l, i - 1); quickSort(s, i + 1, r); } }
归并排序
int Mid[Num]={0}; void Merge(int* s,int low,int mid,int up) { int a=low,b=mid+1; for(int i=low;i<=up;i++) Mid[i]=s[i]; for(int i=low;i<=up;i++) { if(a>mid) s[i]=Mid[b++]; else if(b>up) s[i]=Mid[a++]; else if(Mid[a]<=Mid[b]) s[i]=Mid[a++]; else s[i]=Mid[b++]; } } int Sort(int* s,int low,int up)//归并排序 { if(up<=low) return 0; else { int mid=(low+up)/2; Sort(s,low,mid); Sort(s,mid+1,up); Merge(s,low,mid,up); } }
单词翻转
#include<stdio.h> #include<stdlib.h> #include<iostream> #include<iomanip> #include<algorithm> using namespace std; int main(){ string s1;int k=0; getline(cin,s1); s1 = s1+" "; int len = s1.length(); for(int i=0;i<len;i++){ if(s1[i]==' '){ for(int j=i-1;j>=k;j--){ cout<<s1[j]; } cout<<" "; k=i+1; } } return 0; }
链表翻转
struct node{ int content; node *next; }; node* ReverseList(node* phead) { node *pre = NULL, *cur = phead, *next = NULL; while (cur->next) { next = cur->next; cur->next = pre; pre = cur; cur = next; } cur->next = pre; return cur; }
二分查找（精确查找）
int find(vector<int>& nums, int target) { int left = 0, right = nums.size(); while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1; else right = mid; } return -1; }
二分查找（小于查找）
int find(vector<int>& nums, int target) { int left = 0, right = nums.size(); while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] < target) left = mid + 1; else right = mid; } return right; }
二分查找（大于查找）
int find(vector<int>& nums, int target) { int left = 0, right = nums.size(); while (left < right) { int mid = left + (right - left) / 2; if (nums[mid] <= target) left = mid + 1; else right = mid; } return right; }
