六种排序算法的Js实现

来源:http://www.chinese-glasses.com 作者:Web前端 人气:153 发布时间:2020-03-31
摘要:时间: 2019-11-01阅读: 118标签: 算法 基本排序算法 用到的技术是一组嵌套的for循环。其中外循环会遍历数组中的每一项,内循环则用于比较元素。选择排序和插入排序要比冒泡排序快,插

时间: 2019-11-01阅读: 118标签: 算法

基本排序算法

用到的技术是一组嵌套的for循环。其中外循环会遍历数组中的每一项,内循环则用于比较元素。选择排序和插入排序要比冒泡排序快,插入排序是这三种最快的。

本文将介绍数据排序的基本算法和高级算法。这些算法都只依赖数组来存储数据。

冒泡排序

按照升序排列,较大的值会浮动到数组的右侧,而较小的值会浮动到数组的左侧。算法会多次在数组中移动,比较相邻的数据,当左侧值大于右侧值时将它们进行互换

function bubbleSort() {
    var numElements = this.dataStore.length;
    var temp;
    for ( var outer = numElements; outer >= 2; --outer) {
        for ( var inner = 0; inner <= outer -1; ++inner) {
            if(this.dataStore[inner] > this.dataStore[inner - 1]) {
                swap(this.dataStore, inner, inner+1);
            }
        }
    }
}

假设数组大小为N,外部循环N-1次,内部分别循环循环N、N-1...2次。

  • 第一次循环(0, N-1),循环结束后最大值在数据最右侧。
  • 第二次循环(0, N-2),循环结束后倒数第二大的数据位于序号为N-2的位置。
  • ...
  • 第N-1次循环(0,1),循环结束后,排序完成。

数组测试平台

选择排序

从数组的开头开始,将第一个元素和其他元素进行比较,检查完所有元素后,最小的元素会被放到数组的第一个位置,然后算法会从第二个位置继续。这个过程一直进行,当进行到数组的倒数第二个位置时,所有的数据便完成了排序。

外循环从数组的第一个元素移动到倒数第二个元素,内循环从第二个数组元素移动到最后一个元素,查找比当前外循环所指向的元素小的元素。

function selectionSort() {
    var min, temp;
    for (var outer = 0; outer <= this.dataStore.length-2; ++outer) {
        min = outer;
        for (var inner = outer +1; inner <= this.dataStore.length-1; ++inner) {
            if (this.dataStore[inner] < this.dataStore[min]) {
                min = inner;
            }
            swap(this.dataStore, outer, min);
        }
    }
}

数组位置是互换,不是移动。这是与插入排序的区别

首先我们构造一个数组测试平台类

插入排序

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

function insertionSort(){
    var temp, inner;
    for (var outer = 1; outer <= this.dataStore.length - 1; ++outer) {
        temp = this.dataStore[outer];
        inner = outer;
        while (inner > 0 && (this.dataStore[inner -1] >= temp)) {
            this.dataStore[inner] = this.dataStore[inner -1];
            --inner
        }
        this.dataStore[inner] = temp
    }
}
function CArray(numElements) { this.dataStore = []; this.numElements = numElements; this.toString = toString; this.clear = clear; this.setData = setData; this.swap = swap;}function setData() { for (var i = 0; i  this.numElements; ++i) { this.dataStore[i] = Math.floor(Math.random() * (this.numElements + 1)); }}function clear() { for (var i = 0; i  this.numElements; ++i) { this.dataStore[i] = 0; }}function toString() { var restr = ""; for (var i = 0; i  this.numElements; ++i) { restr += this.dataStore[i] + " "; if (i  0  i % 10 == 0) { restr += "n"; } } return restr;}function swap(arr, index1, index2) { var temp = arr[index1]; arr[index1] = arr[index2]; arr[index2] = temp;}

高级排序算法

使用测试平台类

希尔排序

在插入排序的基础上做了很大的改善。希尔排序的核心理念与插入排序不同,它会首先比较距离较远的元素,而非相邻的元素,这样可以使离正确位置很远的元素更快的回到合适的位置。

在开始做最后一次处理时,大部分元素都将在正确的位置,算法就不必对很多元素进行交换。这就是希尔排序比插入排序更高效的地方。

...
this.gaps = [5,3,1];
function shellsort() {
    for (var g = 0; g < this.gaps.length; ++g) {
        for (var i = this.gaps[g]; i < this.dataStore.length; ++i) {
            var temp = this.dataStore[i];
            for (var j = i; j >= this.gaps[g] && this.dataStore[j-this.gaps[g]] > temp; j -= this.gaps[g]){
                this.dataStore[j] = this.dataStore[j - this.gaps[g]];
            }
            this.dataStore[j] = temp;
        }
    }
}

间隔序列,静态和动态效率是一样的

var numElements = 100;var myNums = new CArray(numElements);myNums.setData();console.log(myNums.toString());

归并排序

把一系列排好序的子序列合并成一个大的完整有序序列。
基本上不会用到

基本排序算法

快速排序

处理大数据集最快的排序算法之一。通过递归的方式将数据依次分解为包含较小元素和较大元素的不同子序列。

首先要在列表中选择一个元素作为基准值。数据排序围绕基准值进行,将列表中小于基准值的元素移到数组的底部,将大于基准值的元素移到数组的顶部。

快速排序的算法如下:

  1. 选择一个基准元素,将列表分隔成两个子序列
  2. 对列表重新排序,将所有小于基准值得元素放在基准值的前面,所有大于基准值的元素放在基准值的后面
  3. 分别对较小元素的子序列和较大元素的子序列重复步骤1和2
function qSort(list) {
    if (list.length == 0) {
        return [];
    }
    var lesser = [];
    var greater = [];
    var pivot = list[0];
    for (var i = 1; i < list.length; i++) {
        if (list[i] < pivot) {
            lesser.push(list[i]);
        } else {
            greater.push(list[i]);
        }
    }
    return qSort(lesser).concat(pivot, qSort(greater));
}

快速排序算法非常适用于大型数据集合,在处理小数据集时性能反而会下降

这些算法非常逼真地模拟了人类在现实生活中对数据的排序。

参考

  • 《数据结构与算法 JavaScript 描述》

冒泡排序

它是最慢的排序算法之一,但也是一种最容易实现的排序算法。 之所以叫冒泡排序是因为使用这种排序算法排序时,数据值会像气泡一样从数组的一端漂浮到另一端。假设正在将一组数字按照升序排列,较大的值会浮动到数组的右侧,而较小的值则会浮动到数组的左侧。之所以会产生这种现象是因为算法会多次在数组中移动,比较相邻的数据,当左侧值大于右侧值时将它们进行互换。

冒泡排序的代码

function bubbleSort() { var numElements = this.dataStore.length; for (var outer = numElements; outer = 2; --outer) { for (var inner = 0; inner  outer - 1; ++inner) { if (this.dataStore[inner]  this.dataStore[inner + 1]) { this.swap(this.dataStore, inner, inner + 1); } } }}

排外层循环限定了未排序的范围(从numElements到2),内层循环从左侧的数据开始逐步比较交换,使得未排序范围中最大的数移动到了最右侧,外层排序范围不断缩小,直到还剩两个未排序元素时再比较交换便完成了排序

选择排序

选择排序从数组的开头开始,将第一个元素和其他元素进行比较。检查完所有元素后,最小的元素会被放到数组的第一个位置,然后算法会从第二个位置继续。这个过程一直进行,当进行到数组的倒数第二个位置时,所有数据便完成了排序。

function selectionSort() { var min; for (var outer = 0; outer = this.dataStore.length - 2; ++outer) { min = outer; for (var inner = outer + 1; inner = this.dataStore.length - 1; ++inner) { if (this.dataStore[inner]  this.dataStore[min]) { min = inner; } } swap(this.dataStore, outer, min); }}

插入排序

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

function insertionSort() { var temp, inner; for (var outer = 1; outer = this.dataStore.length - 1; ++outer) { temp = this.dataStore[outer]; inner = outer; while (inner  0  (this.dataStore[inner - 1] = temp)) { this.dataStore[inner] = this.dataStore[inner - 1]; --inner; } this.dataStore[inner] = temp; }}

基本排序算法的计时比较

10000个随机数测试

bubbleSort();// 100ms左右selectionSort();// 50ms左右insertionSort();// 27ms左右

选择排序和插入排序要比冒泡排序快,插入排序是这三种算法中最快的。

高级排序算法希尔排序

希尔排序在插入排序的基础上做了很大的改善。它会首先比较距离较远的元素,而非相邻的元素。这样可以使离正确位置很远的元素更快地回到合适的位置。当开始用这个算法遍历数据集时,所有元素之间的距离会不断减小,直到处理到数据集的末尾,这时算法比较的就是相邻元素了。希尔排序的工作原理是,通过定义一个间隔序列来表示排序过程中进行比较的元素之间有多远的间隔。我们可以动态定义间隔序列,不过大部分场景算法要用到的间隔序列可以提前定义好。

Marchin Ciura在发表的一篇论文中定义的间隔序列为:701,301,132,57,23,10,4,1。这里我们通过一个小的数据集合来看看这个算法是怎么运行的。

function shellsort() { var temp; for (var g = 0; g  this.gaps.length; ++g) { for (var i = this.gaps[g]; i  this.dataStore.length; ++i) { temp = this.dataStore[i]; for (var j = i; j = this.gaps[g]  this.dataStore[j-this.gaps[g]]  temp; j -= this.gaps[g]) { this.dataStore[j] = this.dataStore[j - this.gaps[g]]; } this.dataStore[j] = temp; } }}

本文由10bet发布于Web前端,转载请注明出处:六种排序算法的Js实现

关键词:

最火资讯