算法图解 - 第2章 选择排序

dbhllnr 2020-06-04

# 了解基本数据结构 - 数组和链表

数组:- 内存是连着的,元素不能随意添加存储。 
  - 优势:读取元素 (因为地址都是已知的)
  -运行时间: ...读取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));

相关推荐