有哪些算法惊艳到了你？

欢迎大家来到IT世界,在知识的湖畔探索吧!

计算机科学撇开硬件领域不说，软件领域的算法应该算是高智商的部分了。

一些算法会让人恍然大悟、茅塞顿开、拍案叫绝。

有哪些算法会惊艳到你？

1 辗转相除法求最大公约数

辗转相除法又称欧几里得算法，是指用于计算两个非负整数的最大公约数。

应该是算法历史上最早的有记录的算法了。

int gcd(int a,int b){ return b==0 ? a : gcd(b,a%b); }

欢迎大家来到IT世界,在知识的湖畔探索吧!

2 Knuth 洗牌算法（Knuth-Shuffle）

等概率随机洗牌：

欢迎大家来到IT世界,在知识的湖畔探索吧!for(int i = n - 1; i >= 0 ; i -- ) swap(arr[i], arr[rand(0, i)]) // rand(0, i) 生成 [0, i] 之间的随机整数

动画：

3 只出现一次的数字

常规算法：

class Solution(object): def singleNumber(self, nums): hash_table = {} for i in nums: try: hash_table.pop(i) except: hash_table[i] = 1 return hash_table.popitem()[0]

使用异或：

欢迎大家来到IT世界,在知识的湖畔探索吧!class Solution(object): def singleNumber(self, nums): a = 0 for i in nums: a ^= i return a

动图：

4 求平方根

一般能想到的办法是:

① 调用系统库函数: sqrt()；

② 二分法逼近；

③ 牛顿迭代法；

在Quake游戏渲染引擎中, 求一个数的平方根的倒数的代码（3D变换过程中要涉及到大量的平方根翻转操作）：

float InvSqrt (float x){ float xhalf = 0.5f*x; int i = *(int*)&x; i = 0x5f3759df - (i>>1); x = *(float*)&i; x = x*(1.5f - xhalf*x*x); return x; }

其本质上也是使用了牛顿迭代法, 但是通过预先猜测的一个神奇数字 0x5f3759df, 来将迭代次数降到极限的一次 (另外通过整形数的移位来进一步加速)。

类似的, Quake3里的开方函数源代码:

double sqrt( double x ) { float y; float delta; float maxError; if( x <= 0 ) { return 0; } // initial guess y = x / 2; // refine maxError = x * 0.001; do { delta = ( y * y ) - x; y -= delta / ( 2 * y ); } while( delta > maxError || delta < -maxError ); return y; }

5 KMP字符串匹配算法

三个人共同写出来的一个关于字符串匹配的算法。一个算法由三个人来写，肯定有其惊艳之处，事实也确实如此。字符串匹配的Brute Force方法其时间复杂度需要O(m*n)(如果主串和子串的长度分别为m、n的话)，但KMP宣称只需要O(m+n)，主串比较指针不回撤，从子串本身的找前缀和后缀的规律（用一个数组来表示）。

/ * 求出一个字符数组的next数组 * @param t 字符数组 * @return next数组 * T: ABCFEDABCFTYGFHTABCDEFHMI * P: ABCDEFG */ public static int[] getNextArray(char[] t) { int[] next = new int[t.length]; next[0] = -1; next[1] = 0; int k; for (int j = 2; j < t.length; j++) { k=next[j-1]; while (k!=-1) { if (t[j - 1] == t[k]) { next[j] = k + 1; break; } else { k = next[k]; } next[j] = 0; //当k==-1而跳出循环时，next[j] = 0，否则next[j]会在break之前被赋值 } } return next; } / * 对主串s和模式串t进行KMP模式匹配 * @param s 主串 * @param t 模式串 * @return 若匹配成功，返回t在s中的位置（第一个相同字符对应的位置），若匹配失败，返回-1 */ public static int kmpMatch(String s, String t){ char[] s_arr = s.toCharArray(); char[] t_arr = t.toCharArray(); int[] next = getNextArray(t_arr); int i = 0, j = 0; while (i<s_arr.length && j<t_arr.length){ if(j == -1 || s_arr[i]==t_arr[j]){ i++; j++; } else j = next[j]; } if(j == t_arr.length) return i-j; else return -1; }

动画：

6 快速排序

图书馆管理员大妈看见两个志愿者需要把还回来的一堆书按顺序入架，提示说：“你先在这堆书里拉出一本来，把比它号小的扔到一边，比它大的扔到另一边，然后剩下两堆继续这样整，这样排的快！”

从数列中挑出一个元素，称为 “基准”（pivot）。

重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

demo code:

#include <iostream> // Quick Sort using namespace std; int Partition(int r[],int low,int high) // 划分函数，和基准元素交换，易于理解 { int i=low,j=high,pivot=r[low]; // 基准元素 while(i<j) { while(i<j && r[j]>pivot) // 向左扫描 j--; if(i<j) swap(r[i++],r[j]); // r[i]和r[j]交换后i+1右移一位 while(i<j && r[i]<=pivot) // 向右扫描 i++; if(i<j) swap(r[i],r[j--]); // r[i]和r[j]交换 后j-1左移一位 } return i; // 返回最终划分完成后基准元素所在的位置 } void QuickSort(int R[],int low,int high)// 实现快排算法 { int mid; if(low<high) { mid=Partition(R,low,high); // 基准位置 QuickSort(R,low,mid-1); // 左区间递归快排 QuickSort(R,mid+1,high); // 右区间递归快排 } } int main() { int arr[] = {3,5,8,1,2,9,4,7,6}; // 从小到大快速排序 int n = sizeof(arr) / sizeof(int); QuickSort(arr,0,n-1); cout<<"排序后的序列为："<<endl; for(int i=0;i<n;i++) cout<<arr[i]<<" " ; cout<<endl; system("pause"); return 0; }

7 蒙特卡洛随机算法(Monte Carlo)

蒙特卡洛方法可用于近似计算圆周率：让计算机每次随机生成两个0到1之间的数，看以这两个实数为横纵坐标的点是否在单位圆内。生成一系列随机点，统计单位 圆内的点数与总点数，（圆面积和正方形面积之比为PI:4，PI为圆周率），当随机点取得越多时，其结果越接近于圆周率（然而准确度仍有争议：即使取10 的9次方个随机点时，其结果也仅在前4位与圆周率吻合）。

demo code:

#include <stdio.h> #include <stdlib.h> #include <time.h> #define N  // Rand from 0.0 to 1.0 inline double rand01() { return rand()*1.0/RAND_MAX; } int main() { srand((unsigned)time(NULL)); double x,y; int M = 0; for(int i = 0;i < N;i++) { x = rand01(); y = rand01(); if(x*x+y*y<1) M++; } double pi = (double)4*M/N; printf("%lf\n", pi); getchar(); }

8 求幂次方

8.1 最简单的想法，就是写一个 for 循环累乘：

public double myPow(double x, int n) { if (x == -1) { if ((n & 1) != 0) { return -1; } else { return 1; } } if (x == 1.0) return 1; if (n == -) { return 0; } double mul = 1; if (n > 0) { for (int i = 0; i < n; i++) { mul *= x; } } else { n = -n; for (int i = 0; i < n; i++) { mul *= x; } mul = 1 / mul; } return mul; }

8.2 利用递归

public double powRecursion(double x, int n) { if (n == 0) { return 1; } //偶数的情况 if ((n & 1) == 0) { double temp = powRecursion(x, n / 2); return temp * temp; } else { //奇数的情况 double temp = powRecursion(x, n / 2); return temp * temp * x; } } public double myPow(double x, int n) { if (x == -1) { if ((n & 1) != 0) { return -1; } else { return 1; } } if (x == 1.0f) return 1; if (n == -) { return 0; } double mul = 1; if (n > 0) { mul = powRecursion(x, n); } else { n = -n; mul = powRecursion(x, n); mul = 1 / mul; } return mul; }

8.3 利用迭代：

public double myPow(double x, int n) { if (x == -1) { if ((n & 1) != 0) { return -1; } else { return 1; } } if (x == 1.0f) return 1; if (n == -) { return 0; } double mul = 1; if (n > 0) { mul = powIteration(x, n); } else { n = -n; mul = powIteration(x, n); mul = 1 / mul; } return mul; } public double powIteration(double x, int n) { double ans = 1; //遍历每一位 while (n > 0) { //最后一位是 1，加到累乘结果里 if ((n & 1) == 1) { ans = ans * x; } //更新 x x = x * x; //n 右移一位 n = n >> 1; } return ans; }

9 布隆过滤器BloomFilter

32位无符号int型能表示的最大值是，所有的ip都在这个范围内，我们可以用一个bit位来表示某个ip是否出现过，如果出现过，就把代表该ip的bit位置为1，那么我们最多需要个bit就可以表示所有的ip了。举个例子比如10.0.0.1转换成int是，那么把长度为的bit数组的第个位置置为1即可，当有ip访问时，只需要检查该标志位是否为1就行了。

public void set(int value){ int byteIndex = value / 8; // 位于第几个字节 int bitIndex = value % 8; // 位于第几个字节的第几个位 byte[byteIndex] = byte[byteIndex] | 1 << (7 - bitIndex) } public boolean isHash(int value){ int byteIndex = value / 8; int bitIndex = value % 8; return byte[byteIndex] & 1 << (7 - bitIndex) > 0 }

9 希尔排序

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；

按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

demo code:

#include <stdio.h> #define SIZE 10 void ShellSort(int* a, int len) { int j,temp; int x=0; // 中间步骤数量 for(int r=len/2; r>=1; r/=2) // 分组数量：n/2、n/4、n/8…， { // 相邻两组元素分别比较 for(int i=r; i<len; i++) { temp = a[i]; j=i-r; while(j>=0 && temp < a[j]) { a[j+r] = a[j]; j-=r; // 按条件回溯到前面的组（非相邻组）对应的元素 } a[j+r] = temp; // 下标=j+r=i（无交换）或i-nr(有交换) } x++; printf("第%d步排序结果（r=%d）：",x,r); for(int h=0; h<len; h++) { printf("%d ",a[h]); } printf("\n"); } } void main() { int i; int arr[SIZE] = {8,9,1,7,2,3,5,4,6,0}; printf("排序前：\n"); for(i=0; i<SIZE; i++) printf("%d ", arr[i]); printf("\n"); ShellSort(arr,SIZE); printf("排序后：\n"); for(i=0; i<SIZE; i++) printf("%d ", arr[i]); printf("\n"); getchar(); }

10 归并排序

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；

设定两个指针，最初位置分别为两个已经排序序列的起始位置；

比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；

重复步骤 3 直到某一指针达到序列尾；

将另一序列剩下的所有元素直接复制到合并序列尾。

demo code:

#include <stdio.h> #define MaxSize 7 int num[] = {6,4,3,7,5,1,2}; int n = sizeof num / sizeof *num; void mergeSort(int[], int, int); void printArr(int num[],int n); int static mergeFuncCalledSize = 0; // 调试用 void merge(int A[], int lo, int mid, int hi) { //A[lo……mid] and A[mid+1……hi] are sorted ascending; //merge the pieces so that A[lo……hi] are sorted ascending int T[MaxSize]; int i = lo; // to subscript the first part of A : A[lo……mid] int j = mid + 1; // to subscript the second part of A : A[mid+1……hi] int k = lo; // and k to subscript T while (i <= mid || j <= hi) { if (i > mid) // A[lo……mid] part is already processed, T[k++] = A[j++];// then process the surplus of A[mid+1……hi] else if (j > hi) // A[mid+1……hi] part is already processed, T[k++] = A[i++];// then process the surplus of A[lo……mid] else if (A[i] < A[j]) // sorted ascending ,the smaller is process preferentially T[k++] = A[i++]; else T[k++] = A[j++]; } for (j = lo; j <= hi; j++) A[j] = T[j]; mergeFuncCalledSize++; // 调试用 printArr(A,n); // 调试用 } int main() { printArr(num,n); mergeSort(num, 0, n-1); printArr(num,n); printf("临时数组T在栈区被开辟了%d次！\n",mergeFuncCalledSize); printf("排序的数组元素的个数：%d\n",n); printf("要避免临时数组T在栈区重复分配内存空间，可以声明为局部static\n"); getchar(); return 0; } void mergeSort(int A[], int lo, int hi) { void merge(int[], int, int, int); if (lo < hi) { //list contains at least 2 elements int mid = (lo + hi) / 2; //get the mid-point subscript mergeSort(A, lo, mid); //sort first half mergeSort(A, mid + 1, hi); //sort second half merge(A, lo, mid, hi); //merge sorted halves } } void printArr(int num[],int n) { for (int h = 0; h < n; h++) printf("%d ", num[h]); printf("\n\n"); }

11 堆排序

创建一个堆 H[0……n-1]；

把堆首（最大值）和堆尾互换；

把堆的尺寸缩小 1，并调用 shift_down(0)，目的是把新的数组顶端数据调整到相应位置；

重复步骤 2，直到堆的尺寸为 1。

demo code:

#include <stdio.h> #include <stdlib.h> // 分类 -------------- 内部比较排序 // 数据结构 ---------- 数组 // 最差时间复杂度 ---- O(nlogn) // 最优时间复杂度 ---- O(nlogn) // 平均时间复杂度 ---- O(nlogn) // 所需辅助空间 ------ O(1) // 稳定性 ------------ 不稳定 void Swap(int A[], int i, int j) { int temp = A[i]; A[i] = A[j]; A[j] = temp; } void Heapify(int A[], int i, int size) // 从A[i]向下进行堆调整 { int left_child = 2 * i + 1; // 左孩子索引 int right_child = 2 * i + 2; // 右孩子索引 int max = i; // 选出当前结点与其左右孩子三者之中的最大值 if (left_child < size && A[left_child] > A[max]) max = left_child; if (right_child < size && A[right_child] > A[max]) max = right_child; if (max != i) { Swap(A, i, max); // 把当前结点和它的最大(直接)子节点进行交换 Heapify(A, max, size); // 递归调用，继续从当前结点向下进行堆调整 } } int BuildHeap(int A[], int n) // 建堆，时间复杂度O(n) { int heap_size = n; for (int i = heap_size / 2 - 1; i >= 0; i--) // 从每一个非叶结点开始向下进行堆调整 Heapify(A, i, heap_size); return heap_size; } void HeapSort(int A[], int n) { int heap_size = BuildHeap(A, n); // 建立一个最大堆 while (heap_size > 1) { // 堆（无序区）元素个数大于1，未完成排序 // 将堆顶元素与堆的最后一个元素互换，并从堆中去掉最后一个元素 // 此处交换操作很有可能把后面元素的稳定性打乱， // 所以堆排序是不稳定的排序算法 Swap(A, 0, --heap_size); Heapify(A, 0, heap_size); // 从新的堆顶元素开始向下进行堆调整，时间复杂度O(logn) } } int main() { int A[] = {5,2,7,3,6,1,4};// 从小到大堆排序 int n = sizeof(A) / sizeof(int); HeapSort(A, n); printf("堆排序结果："); for (int i = 0; i < n; i++) { printf("%d ", A[i]); } printf("\n"); system("pause"); return 0; } //output:堆排序结果：1 2 3 4 5 6 7

12 睡眠排序

根据CPU的调度算法实现的，对一组数据进行排序，不能存在负数值，这个数是多大，那么就在线程里睡眠它的10倍再加10，不是睡眠和它的数值一样大的原因是，当数值太小时，误差太大，睡眠的时间不比输出的时间少，那么就会存在不正确的输出结果。

13 猴子排序

随机打乱数组，检查是否排好序，若是，则输出，否则再次打乱，再检查…最佳情况O(n)，平均O(n*n!)，最坏可执行直到世界的尽头。

一个有趣的理论：一只猴子随机敲打打字机键盘，如果时间足够长，总是能打出特定的文本，比如莎士比亚全集。^_^

14 面条排序

首先去买一捆面条，我喜欢手擀面。找到数组中最大和最小的两个数(O(n))，让最大的数对应一根很长的面条，最小的数对应一根很短的面条。
重新遍历数组，每遇到一个数，就取一根面条，把它切成这个数对应的长度，可以得到n根面条。
这里的数与面条长度的对应可以用一个严格递增的函数来映射。
接下来，一手握住这n根面条，稍微用力，别握太紧，在平放的桌面上直立着放下，让所有的面条底端接触到桌面。另一只手平行于桌面，从面条上方缓慢往下移动，每当这只手碰到一根面条，移走它，并把对应的数输出到结果数组中，直到移走全部面条。

12 二分搜索

二分搜索可以实现O(log2n)的时间效率：

#include<iostream> // 二分查找的递归与非递归实现 using namespace std; // 分治法，可分，可合，子问题有独立性 int bisoLoop(int arr[], int len, int findData) { if(arr==NULL || len <=0) return -1; int start = 0; int end = len-1; while(start<=end) { int mid = start+(end-start)/2; if(arr[mid] == findData) return mid; else if(findData < arr[mid]) end = mid-1; else start = mid+1; } return -1; } // 递归有自调用的问题，需要将start和end写在参数列表中 // 来标记和动态变更搜索范围的开始和结束 int bisoRecurs(int arr[], int findData, int start, int end) { if(arr==NULL || start>end) return -1; int mid = start+(end-start)/2; if(arr[mid] == findData) return mid; else if(findData < arr[mid]) bisoRecurs(arr, findData, start, mid-1); else bisoRecurs(arr, findData, mid+1, end); } void main() { int arr[] = {1,2,3,4,5,6,7,8,9}; int len = sizeof(arr)/sizeof(arr[0]); int index = bisoLoop(arr,len,6); int index2 = bisoRecurs(arr,6,0,len-1); cout<<index<<endl; cout<<index2<<endl; system("pause"); } /* 5 5 */

13 其它提到的算法：

Hufmman编码

Dijkstra最短路径

遗传算法

RSA 非对称加密

FFT，快速傅里叶变换

神经网络一系列算法

红黑树（堆是将数据组织成二叉树，树的上下层之间形成顺序，红黑树也是将数组组织成二叉树，但以树的左右子树之间形成顺序，且左右子树之间考虑适当平衡。）

并查集

地精排序

不算惊艳，但也有趣的算法：

// 一个变量遍历2维数组 a[9][9]; i = 81; while(i --){ proc( a[ i / 9 ][ i % 9 ] ) } // 不引入第三变量交换两个int的值 a = a + b b = a - b a = a - b

Integer的bitCount函数，用来计算一个int整数的二进制补码表示中1的个数。和下面这个代码相比，&1，移位，即便是x &= x – 1都弱爆了。特别是函数里的第一行，用的是减号，花了好长时间才理解清楚。

 / * Returns the number of one-bits in the two's complement binary * representation of the specified {@code int} value. This function is * sometimes referred to as the <i>population count</i>. * * @param i the value whose bits are to be counted * @return the number of one-bits in the two's complement binary * representation of the specified {@code int} value. * @since 1.5 */ public static int bitCount(int i) { // HD, Figure 5-2 i = i - ((i >>> 1) & 0x); i = (i & 0x) + ((i >>> 2) & 0x); i = (i + (i >>> 4)) & 0x0f0f0f0f; i = i + (i >>> 8); i = i + (i >>> 16); return i & 0x3f; } 

ref

https://www.zhihu.com/question/