风靡全球的十大算法
作者 | George Dvorsky编译 | 深度学习这件小事1 排序算法 所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视，尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。 稳定的 冒泡排序（bubble sort） — O(n^2）鸡尾酒排序(Cocktail sort，双向的冒泡排序) — O(n^2）插入排序（insertion sort）— O(n^2)桶排序（bucket sort）— O(n); 需要 O(k) 额外空间计数排序(counting sort) — O(n+k); 需要 O(n+k) 额外空间合并排序（merge sort）— O(nlog n);需要 O(n) 额外空间原地合并排序— O(n^2)二叉排序树排序 （Binary tree sort） — O(nlog n)期望时间； O(n^2)最坏时间；需要 O(n) 额外空间鸽巢排序(Pigeonhole sort)— O(n+k); 需要 O(k) 额外空间基数排序（radix sort）— O(n·k); 需要 O(n) 额外空间Gnome 排序— O(n^2)图书馆排序— O(nlog n) withhigh probability，需要（1+)n额外空间不稳定的 选择排序（selection sort）— O(n^2)希尔排序（shell sort）— O(nlog n) 如果使用最佳的现在版本组合排序— O(nlog n)堆排序（heapsort）— O(nlog n)平滑排序— O(nlog n)快速排序（quicksort）— O(nlog n) 期望时间，O(n^2) 最坏情况；对于大的、乱数列表一般相信是最快的已知排序Introsort—O(nlog n)Patience sorting— O(nlog n+k) 最坏情况时间，需要额外的 O(n+ k) 空间，也需要找到最长的递增子串行（longest increasing subsequence）不实用的 ...