快速排序算法和二分搜索算法
算法主要分为排序算法、搜索算法、图算法。图算法我用得不多,没有发言权,本文就不说了。
排序算法中最快的是快速排序算法,搜索算法中最快的是二分搜索算法。我也最喜欢这2 个算法。
因为,它们是使用递归实现的,代码简洁清晰,效率又非常高。
根据我的理解,算法的本质就是数学。根据输入和设定的目标,采用有限的步骤实现输出。通常,使用计算机实现的算法,都会用到循环,这样才能发挥计算机高速运算的优势。
循环和递归是等效的,这已经被科学家所证明。数学上没有循环,只有递归的概念,因此使用递归代替循环表示算法有很多好处:
1, 递归的代码要比循环简洁很多,也优雅很多。
2, 递归的代码可以用数学方式建模,可以从数学角度验证其正确性。
很多函数式语言甚至没有循环的概念和关键字,强迫你使用递归来实现循环。如,ErLang 。
递归也有一些缺点,递归使用栈来保存函数地址和参数、返回值,而栈是有一定大小的,过多的递归调用可能会造成栈溢出。
但是,递归算法会容易转变为循环。我更欣赏递归的简洁,除非真的出现栈溢出的问题,我是不会使用循环的。
二分搜索算法
理论:
二分搜索算法用于针对已排序的集合进行搜索。
它的原理是:
1, 找到排序数组的中间元素,如果它匹配目标值,那么就返回它在数组中的索引。
2, 如果没有找到,那么判断中间值比目标值大还是小,
如果中间值比目标值大,那么就对第一个元素到middle-1 的元素递归这个过程。
如果中间值比目标值小,那么就对middle+1 到最后一个元素。
3, 如果结束的索引小于开始的索引,返回-1 ,表示没有找到。
4, 如果子集合有2 个元素,那么各自比较。因为Java 的整数除法会舍弃小数,如果数组只有2 个元素,那么middle 值一直都是第一个元素。
经过上述的递归过程,最终将返回匹配元素的索引,或者是-1 ,表示找不到。
二分搜索算法之所以速度快,是因为它每次可以把数组切分成两半,每次递归调用都能去除一半数据,而不用匹配每一个数据。下面是代码,逻辑清楚,代码简单。
/** * @param array * @param start * @param end * 这是最后一个元素的索引,第一次调用应该是array.length - 1 * @param value * @return */ public static int binarySearch(int[] array, int start, int end, int value) { int middle = (start + end) / 2; if (end < start) { return -1; } if (end == (start + 1)) { if (array[start] == value) { return start; } else if (array[end] == value) { return end; } } else if (array[middle] == value) { return middle; } else if (value > array[middle]) { return binarySearch(array, middle + 1, end, value); } else if (value < array[middle]) { return binarySearch(array, start, middle - 1, value); } return -1; }
上述代码稍加改变,就可以排序任意类型。如使用泛型,然后加上对Comparable 接口的实现,即可。
快速排序算法
二分搜索算法确实非常快,但是它只能用于已排序数组。如果数组未排序呢,该怎么办呢?简单,先用快速排序算法进行排序,然后再用二分搜索进行搜索。
先排序再搜索,要比匹配每一个元素快得多。搜索引擎,数据库索引也都使用了对数据集合的排序技术,这样搜索数据才会快速。
最慢,也是最容易想到的排序算法是插入排序算法:
1, 遍历数组,找出最小的元素,把它放到第一个元素。
2, 循环查找未排序的数组,直到整个数组排序。
这需要2 个嵌套的循环,意味着它的效率是O(n^2);
之所以插入排序的效率如此之地,是因为要找出整个数组中最小的数据,需要遍历整个数组的元素。
而插入排序聪明就聪明在它不查找整个数组最小、次小… 的元素,而是每次仅仅把小于某个元素的值移到一边,通过迭代最终自动实现排序。这就大大节约了排序所需的计算步骤。
快速排序算法的理论:
1, 如果S 中的元素个数是0 或者1 ,那么返回。
2, 选取S 中的任一元素v ,称为中心点。
3, 将S 集合中的元素分为2 个部分:L={ 小于pivot 的元素+ pivot } 和R={ 大于或者等于pivot 的元素} 。
4, 返回L 和R 。
我们使用Java 使用的是就地排序的方式,因此不需要返回值。
因为Java 是一种可以修改变量的语言,用函数式语言的术语来说,就是有“副作用”。我们利用这个副作用直接修改作为参数的Array ,不需要返回值
/** * 快速排序,有副作用 从小到大 * * @param array * @param start * @param end * 这是最后一个元素的索引,第一次调用应该是array.length - 1 */ public static void quickSort(int[] array, int start, int end) { // 有可能造成start>end 因为递归调用时j+1 ,可能引起j 比end 还大1 。 另外如果数组是空的,或者输入错误也会出现这种情况 if (end <= start) { return; } else { // 取中间元素为中心点,然后移到最右边 int sign = (start + end) / 2; int tmp = array[end]; array[end] = array[sign]; array[sign] = tmp; int j = start; for (int i = start; i <= end - 1; i++) { // 小于的元素和标记互换,等于的不能互换,否则会形成死循环 if (array[i] < array[end]) { tmp = array[i]; array[i] = array[j]; array[j] = tmp; j = j + 1; } } // 把标记元素和第一个>= 它的元素位置互换,这样数组就分成2 个部分,一个部分比中心值小,一个部分比中心值大。 tmp = array[j]; array[j] = array[end]; array[end] = tmp; quickSort(array, start, j); quickSort(array, j + 1, end); } }
》》Java 的Arrays 类也使用快速排序算法进行排序。但它的代码写得像天书一样。
》》提高快速排序算法执行效率的主要方法是对中心点进行检测,希望选中的中心点有更大的概率是整个数组的中值。
》》我的实现中简单的选择数组中间的值作为中心点,一般来说这样的选择效率还是不错的。
》》注意上面的一项实现技术,我们使用把中心数据元素移到数组最后的方式实现了数组的就地比较。这是比较常用的技术,把数据移到数组的最前面或者最后面,方便比较数据。
》》另外,我的Java 快速排序代码使用了“副作用”,而在纯函数式语言,如Haskell,ErLang 中是没有“副作用”的,也就是说变量不可以重新赋值。此时就需要返回值,每次都创建新的子数组。但函数式语言的数组处理功能很强,也会做很多性能优化,因此函数式语言实现快速排序代码更加简单,没有“副作用”,也更加数学化。
》》JDK使用二分搜索和快速排序算法实现搜索和排序,足见上述两个算法的性能优势。
本人博客已搬家,新地址为:http://yidao620c.github.io/
相关推荐
本项目用C++中实现了冒泡排序、插入排序、堆排序、希尔排序、归并排序、基数排序、选择排序、桶排序、快速排序
选择排序 冒泡排序 插入排序 合并排序 快速排序算法原理及代码实现 不同排序算法时间效率的经验分析方法 验证理论分析与经验分析的一致性 当面临巨大数据量的排序的时候,还是优先选择合并排序算法和快速排序算法。...
可能是最快的算法alpha-blend汇编源代码,排序算法数据结构.doc
最快的排序算法 腾讯算法面试题:64匹马8个跑道需要多少轮才能选出最快的四匹(详解)?,排序算法数据结构
当k值较小时,计数排序效率非常高,快于任何比较排序算法。然而,当k值较大时,计数排序需要占用大量额外空间,这成为其主要的缺点。此外,计数排序只能用于非负整数的排序,对于包含负数或浮点数的数组,需要先进行...
多目标规划的概念是 1961年由美国数学家查尔斯和库柏首先提出的。多目标最优化思想,最早是在1896年由法国经济学家V.帕雷托提出来的。他从政治经济学的角度考虑把本质上是不可比较的许多目标化成单个目标的最优化...
不稳定的排序算法:快速排序、希尔排序、堆排序、选择排序(简简记记::快快些些选选堆堆) 所需辅助空间最多:归并排序 所需辅助空间最少:堆排序 平均速度最快:快速排序 当n较大,则应采用时间复杂度为O(nlogn)的...
快速排序是非常流行、应用非常广泛的排序算法,而且实现简单,适用于各种不同的输入数据,在一般应用中比其他排序算法都要快很多。快速排序是基于分治思想的原地排序的排序算法,将长度为N的数组排序所需时间和NlgN...
快速排序算法是在所有数量级为(o(nlogn))的排序算法中其平均性能最好
这是简单的快速排序和加入各种改进算法的后的代码都有,比如快排入栈操作等
该源文件包括三种排序算法,实现效率教高,代码量也不大
1、用代码实现排序的8个排序算法(直接插入、希尔、冒泡、快速、简单选择、堆、二路归并、基数)。 2、在众多排序方法中,简单地断言哪种方法最好是很困难的。应根据具体应用的需求综合考虑选择排序方法。所以将用...
快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为...
当k值较小时,计数排序效率非常高,快于任何比较排序算法。然而,当k值较大时,计数排序需要占用大量额外空间,这成为其主要的缺点。此外,计数排序只能用于非负整数的排序,对于包含负数或浮点数的数组,需要先进行...
本程序比较了六种常见排序算法的速度、比较次数和赋值次数,使用MFC框架界面,直观易用。 提供源代码和EXE文件。
快速排序(Quicksort)是对冒泡排序的一种改进。在实际中最常用的一种排序算法,速度快,效率高。就像名字一样,快速排序是最优秀的一种排序算法。这是快速排序算法代码,可直接用
3. 什么时候最快 当输入的数据已经是正序时(都已经是正序了,我还要你冒泡排序有何用啊)。 4. 什么时候最慢 当输入的数据是反序时(写一个 for 循环反序输出数据不就行了,干嘛要用你冒泡排序呢,我是闲的吗)。 5...
| 二分图匹配(匈牙利算法 DFS 实现) 11 | 二分图匹配(匈牙利算法 BFS 实现) 11 | 二分图匹配(HOPCROFT-CARP 的算法) 11 | 二分图最佳匹配(KUHN MUNKRAS 算法 O(M*M*N)) 11 | 无向图最小割 O(N^3) 12 |...