使用JS实现三种基本的排序算法以及三种算法的比较

wh469012917 发布于2019-08-20 19:09 / 558人阅读

摘要：介绍排序算法是算法中最常见的算法之一，我这里要介绍的是排序算法中的三种基本算法冒泡排序选择排序插入排序，在文章的后面我会对三种算法的速度进行对比。

1.介绍

排序算法是算法中最常见的算法之一，我这里要介绍的是排序算法中的三种基本算法：冒泡排序、选择排序、插入排序，在文章的后面我会对三种算法的速度进行对比。

2.冒泡排序

冒泡排序其名来源与其算法实现，会使得数组中的元素一个个从数组一端漂到另一端而故这样命名。下面我们实现的是对数组就行升序排列的冒泡：

function bubbleSort(arr){
    if(!arr instanceof Array){
        return;
    }
    if(arr.length == 0 || arr.length == 1){
        return arr;
    }
    for(let outer = arr.length; outer >= 2; outer--){
        for(let inner = 0; inner <= outer - 1; inner++){
            if(arr[inner] > arr[inner + 1]){
                let temp = arr[inner];
                arr[inner] = arr[inner + 1];
                arr[inner + 1] = temp;    
            }
        }
    }
    return arr;
}

3.选择排序

选择排序我们也需要用到嵌套循环，算法思路如下：
从数组的第一个元素开始，将第一个元素逐个与其他元素比较，检查完所有元素后，最小的元素会放到最前面。然后从第二个元素继续，重复这一过程，直到进行到数组倒数第二个元素，排序并完成了。

外循环从数组的第一个元素移动到倒数第二个元素；内循环从第二个数组元素移动到最后一个元素，查找比当前外循环所指向的元素小的元素。每次内循环迭代后，数组中最小的值都会被赋值到合适的位置。

function selectionSort(arr){
    if(!arr instanceof Array){
        return;
    }
    if(arr.length == 0 || arr.length == 1){
        return arr;
    }
    let min;
    for(let outer = 0; outer <= arr.length - 2; outer++){
        min = outer;
        for(let inner = outer + 1; inner <= arr.length - 1; inner++){
            if(arr[inner] < arr[min]){
                min = inner;
            }
        }
         let temp = arr[outer];
         arr[outer] = arr[min];
         arr[min] = temp;
    }
    return arr;
}

4.插入排序

插入排序有两个循环。外循环将数组元素挨个移动，而内循环则对外循环中选中的元素及它后面的那个元素进行比较。如果外循环中选中的元素比内循环中选中的元素小，那么数组元素会向右移动，为内循环中的这个元素腾出位置。

function insertionSort(arr){
    if(!arr instanceof Array){
        return;
    }
    if(arr.length == 0 || arr.length == 1){
        return arr;
    }
    let temp,inner;
    for(let outer = 0; outer < arr.length; outer++){
        temp = arr[outer];
        inner = outer;
        while(inner > 0 && (arr[inner - 1] >= temp)){
            arr[inner] = arr[inner - 1];
            --inner;
        }
        arr[inner] = temp;
    }
    return arr; 
}

5.三种排序算法速度的比较

首先我们实现一个生成随机数组的函数：

function createArr(n){
    let arr = [];
    if(typeof n !== "number"){
        return;
    }
    if(n === 0){
        return arr;
    }
    for(let i = 0; i < n ; i++){
        arr[i] = Math.floor(Math.random() * (n + 1));
    }
    return arr;
}

我们通过获取当前的时间戳和运行算法后时间戳进行对比来比较，主要比较数组的大小为100， 1000， 10000时来观察三种算法。

//数组为100的情况
let arr = createArr(100);
let start = Date.now();
bubbleSort(arr);
let stop = Date.now();
cosnole.log(`冒泡排序用时${stop - start}`);
    start = Date.now();
selectionSort(arr);
    stop = Date.now();
cosnole.log(`选择排序用时${stop - start}`);    
    start = Date.now();
insertionSort(arr);
    stop = Date.now();
cosnole.log(`插入排序用时${stop - start}`);

最后得出的结果为

说明数组大小为100时，三种排序算法速度之间没有什么太大的差别。
我把数组扩大为1000得到的结果如下：

现在我们可以看到选择排序和插入排序比冒泡排序都快了很多。
接着我把数据增大为10000，得到的结果为：

现在我们可以很明显的看出三种排序算法的速度谁快谁慢了，特别是我们处理比较大的数据时，对算法的选择影响到程序的性能。

超融合服务器私有云 java三种排序算法最快的基于比较的排序算法负载均衡支持三种调度算法字母的排序算法

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/85212.html

基本排序算法

摘要：基本排序算法在计算机科学中，一个排序算法是一种能将一串数据依照特定的排列方式进行排列的一种算法。毕竟他们的效率都不太理想在实际应用中，应该选择高级排序算法快速排序在随机生成数据测试的时候，发现很多时候，插入排序要快于冒泡排序以及选择排序。基本排序算法在计算机科学中，一个排序算法是一种能将一串数据依照特定的排列方式进行排列的一种算法。这里简单的介绍三种最基本的排序，分别是：冒泡排序...

wupengyu 2019-08-23 14:10 评论0 收藏0
数据结构与算法——希尔、归并、快速排序

摘要：今天再来看看另外三种时间复杂度都是的排序算法，分别是希尔排序归并排序和快速排序。三数取中法求将放到数组的末尾总结这三种排序算法的平均时间复杂度都是，归并排序和快速排序的应用更广泛。 1. 回顾前面说完了三种较为简单的排序算法，分别是冒泡排序，选择排序和插入排序，它们的平均情况时间复杂度都是 O(n2)，比较的高，适合小规模的数据排序，其中插入排序的效率稍高，所以更推荐使用插入排序。今...

hersion 2019-08-16 15:58 评论0 收藏0
js数值排序中冒泡算法的4种简单实现

摘要：实现数组排序的算法很多其中冒泡算法是比较简单的冒泡的基本原理是相邻的两个数进行比较按照排序的条件进行互换例如对数值从小到大排序随着不断的互换最大的那个值会慢慢冒泡到数组的末端基于这个原理我们就可以写冒泡排序了为了简单起见下面的例子都是对数值实现数组排序的算法很多,其中冒泡算法是比较简单的冒泡的基本原理是相邻的两个数进行比较,按照排序的条件进行互换,例如对数值从小到大排序,随着不断的互...

wean 2019-08-22 16:44 评论0 收藏0
js数值排序中冒泡算法的4种简单实现

摘要：实现数组排序的算法很多其中冒泡算法是比较简单的冒泡的基本原理是相邻的两个数进行比较按照排序的条件进行互换例如对数值从小到大排序随着不断的互换最大的那个值会慢慢冒泡到数组的末端基于这个原理我们就可以写冒泡排序了为了简单起见下面的例子都是对数值实现数组排序的算法很多,其中冒泡算法是比较简单的冒泡的基本原理是相邻的两个数进行比较,按照排序的条件进行互换,例如对数值从小到大排序,随着不断的互...

zacklee 2019-08-29 15:10 评论0 收藏0
js数值排序中冒泡算法的4种简单实现

摘要：实现数组排序的算法很多其中冒泡算法是比较简单的冒泡的基本原理是相邻的两个数进行比较按照排序的条件进行互换例如对数值从小到大排序随着不断的互换最大的那个值会慢慢冒泡到数组的末端基于这个原理我们就可以写冒泡排序了为了简单起见下面的例子都是对数值实现数组排序的算法很多,其中冒泡算法是比较简单的冒泡的基本原理是相邻的两个数进行比较,按照排序的条件进行互换,例如对数值从小到大排序,随着不断的互...

zzzmh 2019-08-02 10:18 评论0 收藏0