以前在学校只专注于研究感兴趣的技术，开发一些乱七八糟的项目，几乎没刷过题，现在面试笔试被各种毒打。现在开始亡羊补牢。只记录算法或思路，不记录题目，不间断更新，顺便重拾C++
文章目录
- 前言
- @[TOC](文章目录)
- 排序算法
- 冒泡排序
- 选择排序
- 插入排序
- 希尔排序
- 归并排序
- 快速排序
- 一些题型解题思路
- 统计素数（或者叫质数）个数
- 数组中3数最大乘积
- 判断链表是否有环
void BubbleSort(int arr[], int len)
{
for (int i = 0; i < len; i++) {
//因为第len - i后面的元素是已经排好了，所以每次只需要遍历 0 到 len - 1 - i 个元素
for (int j = 0; j < len - 1 - i; j++) {
//若当前元素大于下一个元素，则交换
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
选择排序
void SelectSort(int arr[], int len)
{
for (int i = 0; i < len; i++) {
int minIndex = i;
//从元素下一个开始往后找最小的
for (int j = i + 1; j < len; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
//将当前下标的元素与最小元素交换
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
插入排序
void InsertSort(int arr[], int len)
{
//第一个不用排，从1开始
for (int i = 1; i < len; i++) {
int cur = arr[i];//先拿出要进行插入的元素
int insertIndex = 0;//下面循环中如果一直找不到可以插的位置，直到循环结束，说明目前它最小，就插到第一个元素的位置
//往前找有没有还可以插入的地方,同时把排好的元素向后移动
for (int j = i - 1; j >= 0; j--) {
if (cur < arr[j]) {
arr[j + 1] = arr[j];//当前选择的元素比排好的小，排好的元素后移
} else {
insertIndex = j + 1;//插入位置为当前与cur比较的元素的前面
break;
}
}
arr[insertIndex] = cur;
}
}
希尔排序
//希尔排序 使数据逐渐变得有序，最后在比较有序的数据里进行插入排序，减少插入排序时移动元素的次数
void ShellSort(int arr[],int len)
{
int gap = len / 2;
while (gap > 0)
{
//外面一层循环次数为数组的组数，里面一层为每组的元素个数
for (int i = gap; i < len; i++) {
int cur = arr[i];//先拿出要进行插入的元素
int insertIndex = i - gap;//下面循环中如果一直找不到可以插的位置，直到循环结束，说明目前它最小，就插到第一个元素的位置
//往前找有没有还可以插入的地方,同时把排好的元素向后移动,
//不过希尔排序需要跨步，把一个数组看成若干个交错在一起的数组，gap就是跨的距离，直到gap = 1，就变成普通插入排序
for (int j = i - gap; j >= 0; j -= gap) {
if (cur < arr[j]) {
arr[j + gap] = arr[j];//当前选择的元素比排好的小，排好的元素后移
} else {
insertIndex = j + gap;//插入位置为当前与cur比较的元素的前面
break;
}
}
arr[insertIndex] = cur;
}
gap /= 2;
}
}
归并排序
//将数组start到mid 和 mid+1到end进行合并
void MergeArr(int arr[], int start, int mid, int end, int temArr[])
{
int i = start, j = mid + 1, k = 0;
//比较长度相同部分
while (i <= mid && j <= end) {
if (arr[i] < arr[j])
temArr[k++] = arr[i++];
else
temArr[k++] = arr[j++];
}
//i超出部分
while (i <= mid) {
temArr[k++] = arr[i++];
}
//j超出部分
while (j <= end) {
temArr[k++] = arr[j++];
}
for (int i = 0; i < k; i++)
arr[start + i] = temArr[i];
}
void RecursionMergeSort(int arr[], int start, int end, int temArr[])
{
if (start >= end) return;//结束递归的条件
//排序两边的数组
int mid = (start + end) / 2;
RecursionMergeSort(arr, start, mid, temArr);
RecursionMergeSort(arr, mid + 1, end, temArr);
//将排好的数组合并
MergeArr(arr, start, mid, end, temArr);
}
//归并排序
void MergeSort(int arr[],int len)
{
int* temArr = (int*)malloc(len * sizeof(int));
RecursionMergeSort(arr, 0, len - 1, temArr);
}
快速排序
void Swap(int arr[], int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
//快速排序 前后指针法
void QuckSort(int arr[], int start, int end)
{
if (start >= end) return; //递归结束条件
//取第一个元素为基准
int key = arr[start];
int prev = start;
int latter = prev + 1;
while (latter <= end) {
//若后面的值比key小，交换到前面去，不要交换第一个位置，交换完成后latter后移
if (arr[latter] < key) {
Swap(arr, ++prev, latter);
}
latter++;
}
//当latter越界后prev所在的位置就是数列中比key小的最后那个数，交换它们
Swap(arr, start, prev);
//继续排序左右两边 prev所指的key不用继续排列了
QuckSort(arr, start, prev - 1);
QuckSort(arr, prev + 1, end);
}
一些题型解题思路
统计素数（或者叫质数）个数
//暴力方式
bool isPrimer(int n)
{
//i * i <= n不能是i * i < n，如果n能被i整除也不是素数，例如9，如果仅仅是小于号就判断为素数了
for (int i = 2; i * i <= n; i++) {
if (n % i == 0) return false;
}
return true;
}
int PrimerCount(int n)
{
if (n < 2) return 0;
if (n == 2) return 1;
int count = 1;//2算一个
for (int i = 3; i <= n; i+=2) {
if (isPrimer(i)) count++;
}
return count;
}
//埃筛法
int PrimerCountAS(int n)
{
if (n < 2) return 0;
int count = 0;
bool *isPrimer = new bool[n + 1];
memset(isPrimer, true, n * sizeof(bool));
for (int i = 2; i <= n; i++) {
if (isPrimer[i]) {
count++;
//查找i的倍数并标记不是素数
for (int j = i + i; j <= n; j += i) {
isPrimer[j] = false;
}
}
}
delete[] isPrimer;
return count;
}
数组中3数最大乘积
同符号直接取最大前3个数相乘，有正有负则保证结果为正的前提下，取绝对值最大的3个判断链表是否有环
双指针算法，慢指针每次位移一个位置，快指针比慢指针快一步，每次位移两个位置。 如果进入到环，因为指针比较快会迟早从后面追上慢指针。 当快指针==慢指针，代表有环，但快指针为null或它的下一个为null，则遍历结束，没有环。 另一个方法： 每次遍历到一个节点的时候，给它标上一个下标，当发现下一个节点被标记过，则有环
