选择排序和插入排序--学习笔记

2018-06-24 02:09:02来源:未知 阅读 ()

新老客户大回馈,云服务器低至5折

插入排序和选择排序--学习笔记

  从《算法导论》学习了插入排序,选择排序是在课后练习出现的,代码用javascript编写。

  首先,了解一下插入排序和选择排序。类似玩扑克游戏,如下图(摘自《算法导论》-- 插入排序的附图):

  

  插入排序和选择排序就像两个不同习惯的人:一个人喜欢一张一张地摸牌(插入排序),而另一个人则喜欢等发牌员发完牌拿在手上一起调整(选择排序)。

插入排序

  插入排序类似于一张一张地摸牌,其中,在手上的牌已经排序,而在桌子上的牌则是待排序的牌,因此,第一张牌肯定是已排序的,循环应该从第二张牌开始。

  《算法导论》中插入排序过程附图:

  

  其中,灰色为已排序部分,黑色为正在排序(刚摸到的牌),白色为未排序(还在桌面的牌)。可初步设计为,外层循环控制待比较的未知元素个数,而内层循环则为当前正在排序的元素(当前元素)与其前面的元素逐一比较。

  js代码:

 1 var s = [5, 4, 3, 2, 1];
 2 var insertSort = function(array) {
 3     var key;    //记录当前排序元素(摸到的牌)
 4     var j;
 5     for(var i = 1; i < array.length; i++) {
 6         key = array[i];
 7         j = i - 1;
 8         while(j >= 0 && key < array[j]) {
 9             array[j+1] = array[j];
10             j--;
11         }
12         array[j+1] = key;    //在合适的位置,用当前排序的元素替换
13     }
14     return array;
15 };
16 insertSort(s);
17 console.log(insertSort(s));
18 //=>[ 1, 2, 3, 4, 5 ]

 算法用一个for循环和一个嵌套的while循环实现。需要注意的是,while循环内部调整当前元素之前的元素的位置,但while循环结束时得到的数组并没有包含原数组的所有元素,而是在第12行的时候将当前元素(摸到的牌)替换。

  修改代码观察算法过程:

var s = [5, 4, 3, 2, 1];
var insertSort = function(array) {
    var key;    //记录当前排序元素(摸到的牌)
    var j;
    for(var i = 1; i < array.length; i++) {
        key = array[i];
        j = i - 1;
        while(j >= 0 && key < array[j]) {
            array[j+1] = array[j];
            j--;
        }
        console.log(array);
        array[j+1] = key;    //在合适的位置,用当前排序元素替换
        console.log(array);
    }
};
insertSort(s);
//=>[ 5, 5, 3, 2, 1 ]  //整个while循环结束时
    [ 4, 5, 3, 2, 1 ]  //下一个for循环开始前
    [ 4, 4, 5, 2, 1 ]
    [ 3, 4, 5, 2, 1 ]
    [ 3, 3, 4, 5, 1 ]
    [ 2, 3, 4, 5, 1 ]
    [ 2, 2, 3, 4, 5 ]
    [ 1, 2, 3, 4, 5 ]

 

选择排序

  选择排序类似于,在桌子上抓起一把牌(不知道有没有排序),把牌摊开后,从里面选出最小(或最大)的一张牌,然后与左边第一张牌交换(不同的地方是正常人给牌排序时一般直接插入而不是交换);接着从剩下的牌中找出第二小的牌,与左边第二张牌交换;...直到找出n - 1张较小的牌交换,则成功排序。

代码:

 1 var s = [5, 2, 1, 6, 8, 7, 4, 3];
 2 var selectSort = function(array) {
 3     var temp, flag;  //flag记录剩下元素中"最小"数的下标
 4     for(var i = 0; i < array.length - 1; i++) {
 5         flag = i;
 6         for(var j = i; j < array.length; j++) {
 7             if(array[j] <= array[flag]) {
 8                 flag = j;
 9             } 
10         }
11         temp = array[i];
12         array[i] = array[flag];
13         array[flag] = temp;    //交换
14     }
15 };
16 selectSort(s);
17 console.log(s);
18 //=>[ 1, 2, 3, 4, 5, 6, 7, 8 ]

修改代码显示排序过程:

var s = [5, 2, 1, 6, 8, 7, 4, 3];
var selectSort = function(array) {
    var temp, flag;
    for(var i = 0; i < array.length - 1; i++) {
        flag = i;
        for(var j = i; j < array.length; j++) {
            if(array[j] <= array[flag]) {
                flag = j;
            } 
        }

        temp = array[i];
        array[i] = array[flag];
        array[flag] = temp;

        console.log(array);
    }
};
selectSort(s);
console.log(s);
//=>[ 1, 2, 5, 6, 8, 7, 4, 3 ]
    [ 1, 2, 5, 6, 8, 7, 4, 3 ]
    [ 1, 2, 3, 6, 8, 7, 4, 5 ]
    [ 1, 2, 3, 4, 8, 7, 6, 5 ]
    [ 1, 2, 3, 4, 5, 7, 6, 8 ]
    [ 1, 2, 3, 4, 5, 6, 7, 8 ]
    [ 1, 2, 3, 4, 5, 6, 7, 8 ]
    [ 1, 2, 3, 4, 5, 6, 7, 8 ]

   可见,每次外层for循环都能找出一个“最小”数,并与前面适合位置的数进行交换。

----------------------------------------------------------------------------------------------------------

  因为笔者还处在学习阶段,文中出现很多不规范或者错误之处,还望各位看官赐教。

  另外,十分感谢《算法导论》。

  注:本文为个人学习随笔,仅供个人学习,如有雷同,敬请原谅!

标签:

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:jsAnim简单使用教程

下一篇:渐进式Web应用(PWA)入门教程(下)