javascript - 麻烦看下我根据自己理解写出的三种排序算法是否正确？？

问题描述

问 题

排序算法学习原文链接：链接描述

gif动图描述：
冒泡排序：链接描述
选择排序：链接描述
插入排序：链接描述

根据动图，我写出的代码（没有按照那个网址上的来，而是通过观察动图，得出的代码，正确性未知。不过结果是正确的）：

// 冒泡排序
function bubbleSort(arr , sortType){
    var sortTypeRange = ['asc' , 'desc'];
    var sortType = !contain(sortType , sortTypeRange) ? 'asc' : sortType;
    // 作为中间值，进行交换
    var cur  = null;
    for (var i = 0; i < arr.length; ++i)
        {
            for (var n = 0; n < arr.length; ++n)
                {
                    
                    if (sortType === 'asc' ? arr[n] > arr[n + 1] : arr[n] < arr[n + 1]) {
                        cur    = arr[n];
                        arr[n] = arr[n + 1];
                        arr[n + 1]   = cur;
                    }
                }
        }

    return arr;
}

// 选择排序
function selectionSort(arr , sortType){
    var sortTypeRange = ['asc' , 'desc'];
    var sortType = !contain(sortType , sortTypeRange) ? 'asc' : sortType;
    // 作为中间值，进行交换
    var cur  = null;

    for (var i = 0; i < arr.length; ++i)
        {
            cur = arr[i];
            for (var n = i + 1; n < arr.length; ++n)
                {
                    
                    if (sortType === 'asc' ? cur > arr[n] : cur < arr[n]) {
                        arr[i] = arr[n];
                        arr[n]   = cur;
                        cur    = arr[i];
                    }
                }
        }

    return arr;
}

// 插入排序
function insertSort(arr , sortType){
    var sortTypeRange = ['asc' , 'desc'];
    var sortType = !contain(sortType , sortTypeRange) ? 'asc' : sortType;
    var cur  = null;
    for (var i = 0; i < arr.length; ++i)
        {
            // 用来持续比较的值
            cur = arr[i];
            for (var n = Math.max(0 , i - 1) ; n >= 0; --n)
                {
                    // 自身对比时，跳出
                    if (n === i) {
                        break;
                    }

                    if (sortType === 'asc' ? cur < arr[n] : cur > arr[n]) {
                        arr[n + 1] = arr[n];
                        arr[n]     = cur;
                    } else {
                        break;
                    }
                }
        }
    
    return arr;
}

三种算法运行结果，随机数：10000 个，升序排序：

得出的结果是正确的，感觉自己写的也对。但毕竟是自己觉得，所以想要精通的算法的人看下，上面的代码是否正确？？即 标注的名称：冒泡排序 和实际的代码：冒泡排序代码 是否对应？不会说标注了冒泡排序 ，然后冒泡排序代码 却 用的不是冒泡排序的算法，那就不好了....

麻烦大神看下...，谢谢

解决方案

冒泡有点问题。每一趟都已经把最大的挪到最后一位了，里层循环应该是for (var n = 0; n < arr.length-i; ++n)

---

算法的复杂度一般是指最坏的情况。总的来说选择排序是比冒泡效率高的因为选择排序每趟只需交换一次数。冒泡的swap比选择排序更频繁。选择排序是看准了直接swap一下。选择的逻辑是每次在数组中找最小（大）的放到另一个数组的最后一个，这样无论数组是什么样子的都要遍历需要排列的数组直到只有最后一个，所以，第一个数字要遍历n遍，第二个n-1……一直到1.无论初始序列是什么样的排列方式，选择排序都得经过N(N-1)/2次比较。

算法的实际执行这也要看你随机生成的数据，比如你随机的数据里面有大量数据都已经是排好序的，那冒泡排序的时候两个数比较就不用进入交换的过程，这样排序时间就很短。大量数据已经排好的情况下冒泡很快。然后应该用相同的数据来测试两种算法啊。控制变量嘛。另外你这里的选择排序感觉写错了...。选择排序是每一趟找到最小的放到最前面。我自己写了下加测试希望能帮到你，在纸上画图会对理解算法很有帮助。

var array1 = [];
var array2 = [];
for (var i = 0;i < 10000; i++) {
    var item = Math.floor(Math.random()*10000);
    array1.push(item);
    array2.push(item);
} 


function test1(func){
    var start = new Date().getTime();//起始时间
    func(array1);//执行待测函数
    var end = new Date().getTime();//接受时间
    console.log(array1);
    console.log("selectionSort " + (end - start)+"ms");//返回函数执行需要时间
}

function test2(func){
    var start = new Date().getTime();//起始时间
    func(array2);//执行待测函数
    var end = new Date().getTime();//接受时间
    console.log(array2);
    console.log("bubbleSort " + (end - start)+"ms");//返回函数执行需要时间
}


var swap = function(array, index1, index2){
        var aux = array[index1];
        array[index1] = array[index2];
        array[index2] = aux;
};

function selectionSort(array){
        var length = array.length,
            indexMin;

        for (var i=0; i<length-1; i++){
            indexMin = i;
            for (var j=i; j<length; j++){
                if(array[indexMin]>array[j]){
                    indexMin = j;
                }
            }
            if (i !== indexMin){
                swap(array, i, indexMin);
            }
        }
};

    function BubbleSort (array){
        var length = array.length;

        for (var i=0; i<length; i++){
            for (var j=0; j<length-1-i; j++ ){
                if (array[j] > array[j+1]){
                    swap(array, j, j+1);
                }
            }
        }

    };

    test1(selectionSort);
    test2(BubbleSort);

ps: 你说的那本书我翻过，不是那么友好。推荐学习javascript数据结构与算法这本书，或者可以找一些其他的讲数据结构与算法的经典好书，因为数据结构与算法与语言无关~重要的是思想。(大话数据结构什么的也不错)望采纳答案。祝好。

这篇关于javascript - 麻烦看下我根据自己理解写出的三种排序算法是否正确？？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！