算法图解 - 第2章 选择排序
# 了解基本数据结构 - 数组和链表
数组:- 内存是连着的,元素不能随意添加存储。
- 优势:读取元素 (因为地址都是已知的)
-运行时间: ...读取O(1) 地址已知,读取很快
...插入O(n) 插入元素,需将后面的元素都向后或向前移动一位
...删除O(n) 删除元素后,后面的元素都向前移
eg:(几个朋友相约一起看电影,坐会了后,又突然来了个朋友,可是连着的位置有人,就只能重新找个所有人能坐的位置了)
链表:- 链表中的元素可存储在内存的任何地方。
- 链表的每个元素都存储了下一个元素的地址,从而使一系列随机的内存地址串在一起。
- 优势:插入元素 (因为地址只能找到了前一个,就能找到下一个)
-运行时间: ...读取O(n) 不知道地址
...插入O(1) 只需修改前一个元素指向的地址即可
...删除O(1) 只需修改前一个元素指向的地址即可
eg:(寻宝游戏,到了一个目的后,有纸条写着下一个目的地的地址) --(相对于看电影时分开来坐)
访问方式:- 顺序访问 和 随机访问
- 链表只支持顺序访问
# 选择排序
每次选出剩余元素中最大的或者最小放在最终排序的对应位置
eg:歌曲排序,播放次数越多的靠前。 每次找到播放次数最多的放在表中。找第一个需n次,找第二个需n-1次,以此直到找到最后一个
#选择排序 总结
- 需要检查的元素数越来越少
- 随后检查的元素数依次为n - 1, n – 2, …, 2和1。平均每次检查的元素数为1/2 × n,因此运行时间为O(n × 1/2 × n)。
但大O表示法省略诸如1/2这样的常数,因此简单地写作O(n × n)或O(n²)。
- 运行时间: O(n*n) = O(n²)
#补充
基本思想:
在a[1]-a[n-1]中选择最小的元素和a[0]交换;
在a[2]-a[n-1]中选择最小的元素和a[1]交换;
……
在a[i]-a[n-1]中选择最下的元素和a[i-1]交换;
以此类推。。。。。。
算法步骤:
循环比较:
第一轮:将a[0]和a[1]-a[n-1]中的每个元素依次比较,若出现a[0]>a[j],则将两者进行交换;由此可以将数组中最小的元素放到a[0];
第二轮:将a[1]和a[2]-a[n-1]中的每个元素依次比较。同样若出现a[1]>a[j],则将两者交换,由此将倒数第二小的元素放到a[1];
依次类推。。。
/** * @method: selectionSort * @des: 选择排序 - 将数组按从小大大排序 * @param {type} * @return: */ function selectSort(arr) { var len = arr.length; var temp; //比较的轮数 for (var i = 0; i < len ; i++) { //每轮比较的次数 for (var j = i + 1; j < len; j++) { // arr[i] > arr[j] 将其交换,将小的放在arr[i] if (arr[i] > arr[j]) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } // arr[i] console.log(temp,arr[i],arr[j]); } } return arr; } var list = [6, 89, 30, 20, 8, 49, 5]; console.log(selectSort(list));
相关推荐
要知道时间复杂度只是描述一个增长趋势,复杂度为O的排序算法执行时间不一定比复杂度为O长,因为在计算O时省略了系数、常数、低阶。实际上,在对小规模数据进行排序时,n2的值实际比 knlogn+c还要小。