• 24小时服务热线:400-088-1128

当前位置 南顺网络>> 知识拓展

js排序

冒泡排序

工作原理
重复遍历序列,比较相邻的两个元素,如果这两个元素顺序不正确,则交换。重复以上步骤直到排序完成。

js代码实现 + 效率测试
运算10次,平均耗时1018 ms

// 创建 20000 个随机数,数值范围:1 - 100000

let ary = [];

for (let i = 0; i < 20000; i++) {

  ary.push( Math.floor( Math.random()*99999 + 1 ) );

// 冒泡排序

console.time( '冒泡排序' );

let len = ary.length;

while (len > 0) {

  for (let i = 0; i < len; i++) {

    if (ary[i] > ary[i+1]) {

      let temp = ary[i];

      ary[i] = ary[i+1];

      ary[i+1] = temp;

    }

  }

  len--;

}

console.timeEnd( '冒泡排序' );

选择排序

工作原理
首先在未排序的序列中找到最小(或最大)的元素。然后将其与未排序的序列中最左侧的元素进行交换。以此类推,直到排序完成。

js代码实现 + 效率测试
运算10次,平均耗时344 ms

// 创建 20000 个随机数,数值范围:1 - 100000

let ary = [];

for (let i = 0; i < 20000; i++) {

  ary.push( Math.floor( Math.random()*99999 + 1 ) );

}

// 选择排序 以每次找到最小的元素为例

console.time( '选择排序' );

let start = 0, len = ary.length;

while (start < len - 1) {

  let minIdx = start, min = ary[start];

  for (let i = start; i < len; i++) {

    if (ary[i] < min) {

      minIdx = i;

      min = ary[i];

    }

  }

  if (minIdx !== start) {

    let temp = ary[start];

    ary[start] = ary[minIdx];

    ary[minIdx] = temp;

  }

  start++;

}

console.timeEnd( '选择排序' );

插入排序

工作原理
通过构建有序序列,对未排序的数据,在已排序序列中从后向前扫描,找到相应位置并插入。

js代码实现 + 效率测试
运算10次,平均耗时121 ms

// 创建 20000 个随机数,数值范围:1 - 100000

let ary = [];

for (let i = 0; i < 20000; i++) {

  ary.push( Math.floor( Math.random()*99999 + 1 ) );

}

// 插入排序

console.time( '插入排序' );

let len = ary.length;

for (let i = 1; i < len; i++) {

  let curr = ary[i],

      j = i - 1;

  while (j >= 0) {

    if (ary[j] > curr) {

      ary[j+1] = ary[j];

    }

    else {

      break;

    }

    j -= 1;

  }

  ary[j+1] = curr;

}

console.timeEnd( '插入排序' );

希尔排序

工作原理

希尔排序,是插入排序的一种更高效的改进版本。

它是基于插入排序的以下两点性质而提出改进方法的:

插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。

但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。希尔排序通过将序列分为几个区域来提升插入排序的性能,这样可以让一个元素一次性地朝最终位置前进一大步。然后再取越来越小的步长进行排序,算法的最后一步就是普通的插入排序。但是到了这步,需排序的数据几乎是已排好 的了(此时插入排序较快)。

js代码实现 + 效率测试

运算10次,平均耗时16.79 ms

// 创建 20000 个随机数,数值范围:1 - 100000

let ary = [];

for (let i = 0; i < 20000; i++) {

  ary.push( Math.floor( Math.random()*99999 + 1 ) );

}

// 希尔排序

console.time( '希尔排序' );

let len = ary.length,

    step = Math.floor(len / 2 );

while (step > 0) {

  for (let i = 0; i < len; i++) {

    let curr = ary[i];

    let j = i;

    while (j >= step && ary[j - step] > curr) {

      ary[j] = ary[j - step];

      j -= step;

    }

    ary[j] = curr;

  }

  step = Math.floor(step / 2);

}

console.timeEnd( '希尔排序' );

快速排序(应用最为广泛)

工作原理

使用分治法来把一个序列分为两个子序列,然后递归地排序这两个子序列。

快速排序步骤为:

挑选基准值:从数列中挑出一个元素,称为“基准”。

分割:重新排序数列,所有比基准值小的元素放在基准前面,所有比基准值大的元素放在基准后面。在这个分割结束之后,对基准值的排序就已经完成。

递归排序子序列:分别递归地将小于和大于基准值元素的子序列排序。

js代码实现 + 效率测试

运算10次,平均耗时19.58 ms

// 创建 20000 个随机数,数值范围:1 - 100000

let ary = [];

for (let i = 0; i < 20000; i++) {

  ary.push( Math.floor( Math.random()*99999 + 1 ) );

}

// 快速排序 基准默认总是取当前区间的最后一个元素

function quickSort(ary, start, end) {

  let _quickSort = function(ary, start, end) {

    if (end <= start) {

      return ;

    }

    let pivot = ary[end],

        left = start,

        right = end - 1;

    while (left < right) {

      while (ary[left] < pivot && left < right) left++;

      while (ary[right] >= pivot && left < right) right--;

      [ary[left], ary[right]] = [ary[right], ary[left]];

    }

    if (ary[left] >= pivot) {

      [ary[left], ary[end]] = [ary[end], ary[left]];

    }

    else {

      left++;

    }

    _quickSort(ary, start, left - 1);

    _quickSort(ary, left + 1, end);

  }

  _quickSort(ary, start, end);

}

console.time( '快速排序' );

quickSort(ary, 0, ary.length - 1);

console.timeEnd( '快速排序' );