-
Notifications
You must be signed in to change notification settings - Fork 48
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
javaScript的数据结构与算法(七)——排序与搜索算法 #10
Labels
Comments
感谢楼主分享,个人感觉“1.3插入排序”部分还可以优化一下,按目前的代码,即时array[j-1] <= temp也会执行temp = array[i]和array[j] = temp两步,实际上这是没有必要的。 |
@goodluck2018 那你觉得应该优化成什么样?可以贴下代码哈。 |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1、排序
1.1、冒泡排序
冒泡排序比较任何两个相邻的项,如果第一个项比第二个大,则交换它们。元素项向上移动至正确的顺序,就好像气泡升至表面一样,冒泡排序因此得名。
1.2、选择排序
选择排序算法是一种原址比较排序算法。选择排序大致的思路是找到数据结构中的最小值并将其放在第一位,接着找到第二小的值并将其放在第二位,以此类推。
1.3、插入排序
插入排序每次排一个数组项,假定第一项已经排好序了,接着,它和第二项进行比较,如果第二项比第一项大则待在原位,否则插入到第一项之前,以此类推。
1.4、归并排序
归并排序是第一个可以被实际使用的排序算法,前面的三个排序算法的时间复杂度度为O(n²),但是这个归并排序性能不错,其时间复杂度为O(nlogⁿ)。归并排序是一种分治算法。其思想是将原始数组切分成较小的数组,直到每个小数组只有一个位置,接着将小数组归并成较大的数组,直到最后只有一个排序完毕的大数组。
1.5、快速排序
快速排序也许是最常用的排序算法了,它的时间复杂度为O(nlogⁿ),且它的性能通常比其他的复杂度O(nlogⁿ)的排序算法要好。和归并排序一样,快速排序也使用分治的方法,将原始数组分为较小的数组(但它没有像归并排序那样将他们分割开)。
2、搜索
2.1、顺序搜索
顺序或线性搜索是最基本的搜索算法。它的机制是,将一个数据结构中的元素和我们要找的元素做比较。顺序搜索是最低效的一种搜索算法。
2.2、二分搜索
这个算法要求被搜索的数据结构已排序。以下是该算法遵循的步骤:
选择数组的中间值
如果选中值是待搜索值,那么算法执行完毕。
如果待搜索值比选中值要小,则返回步骤1并在选中值左边的子数组中寻找。
如果待搜索值比选中值要大,则返回步骤1并在选中值右边的子数组中寻找。
The text was updated successfully, but these errors were encountered: