专栏首页FinGet前端之路JavaScript常用排序算法

JavaScript常用排序算法

冒泡算法

原理:从第一个元素开始,往后比较,遇到自己小的元素就交换位置

代码实现:

// 冒泡算法
function bubbleSort(arr) {
  var len = arr.length;
  for (var i = 0; i < len; i++) {
	for (var j = 0; j < len-1-i; j++) {
	// 为什么要减一,数组从0开始,先取第一个与第二个比,再将较大值与第三个比,一直比到最后一个,再拿第二个值与第三个比……(外层循环一次,内层循环多次)
	  if (arr[j] > arr[j+1]) { // 比较相邻两个值的大小
		var temp = arr[j+1]; // 临时变量存储arr[j+1]的值
		arr[j+1] = arr[j]; // 将arr[j]的值赋值给arr[j+1],即把较大值往后放
		arr[j] = temp; // 又将temp的值赋值给arr[j],即将较小值往前放
	  }
	}
  }
  return arr;
}
var arr = [2, 3, 4, 5, 6, 1, 90, 16, 35, 7];
console.log(bubbleSort(arr)); // [1, 2, 3, 4, 5, 6, 7, 16, 35, 90]

插入排序

Gif图:

特点: 插入排序把要排序的数组分成两部分: 第一部分包含了这个数组的所有元素,但将第一个元素除外(让数组多一个空间才有插入的位置)。 第二部分就是包含了这一个元素(即待插入元素)。在第一部分排序完成后,再将这个最后元素插入到已排好序的第一部分 比冒泡排序快一点

代码实现:

// 插入排序
function insertSort(arr) {
  // 从第二个元素开始,因为要留一个坑
  for (var i = 1; i < arr.length; i++) {
    var x = arr[i]; // 现将arr[i]的值存下来
	for (var j = i-1; arr[j] > x; j--) {
	  arr[j+1] = arr[j]; // i=3时 [2, 3, 6, 6, ...]
	}
	if (arr[j+1] != x) {
	  arr[j+1] = x; // i=3时 j=2 [2, 3, 4, 6, ...]
	}
  }
  return arr;
}
var arr = [2, 3, 6, 4, 2, 1, 90, 100, 20, 5];
console.log(insertSort(arr)); //[1, 2, 2, 3, 4, 5, 6, 20, 90, 100]

希尔排序

代码实现:

// 希尔排序
function shellSort(arr) {
  var gap = Math.floor(arr.length / 2);
  while (gap > 0) {
    for (var i = gap; i < arr.length; i++) {
	  temp = arr[i];
	  for (var j = i; j >= gap && arr[j-gap] > temp; j -= gap) {
	    arr[j] = arr[j - gap];
	  }
	  arr[j] = temp;
	}
	gap = Math.floor(gap / 2);
  }
  return arr;
}
var arr = [2, 3, 6, 4, 2, 1, 90, 100, 20, 5];
console.log(shellSort(arr)); //[1, 2, 2, 3, 4, 5, 6, 20, 90, 100]

快速排序

3、对”基准”左边和右边的两个子集,不断重复第一步和第二步,直到所有子集只剩下一个元素为止。

特点:速度最快。和归并排序不同的是,归并排序是先分为两组再继续排,而快速排序是边分边排

代码实现:

// 大致分三步:
// 1、找基准(一般以中间项为基准)
// 2、遍历数组,小于基准的放在left,大于基准的放在right
// 3、递归
function quickSort(arr) {
// 如果数组<=1,则直接返回
  if (arr.length <= 1) {
    return arr;
  }
  var pivotIndex = Math.floor(arr.length / 2);
  // 找基准,并把基准从原数组删除
  var pivot = arr.splice(pivotIndex, 1)[0];
  // 定义左右数组
  var left = [];
  var right = [];
  // 比基准小的放在left,比基准大的放在right
  for (var i = 0; i < arr.length; i++) {
    if(arr[i] <= pivot) {
 	  left.push(arr[i]);
 	} else {
 	  right.push(arr[i]);
 	}
  }
  // 递归
  return quickSort(left).concat([pivot], quickSort(right));
} 
var arr = [2, 3, 6, 4, 2, 1, 90, 100, 20, 5];
console.log(quickSort(arr)); //[1, 2, 2, 3, 4, 5, 6, 20, 90, 100]

奇偶排序

代码实现:

//奇偶排序
function oddEvenSort(arr) {
// swaped用来控制循环是否要继续,如果左边的都比右边的小,则退出循环,返回排好的数组
  var swaped = true;
  var k = 0;
  while(swaped) {
    if(k > 0) {
	  swaped = false;
	}
	for (var i = k;i < arr.length-1; i += 2) {
	  if(arr[i] > arr[i+1]) {
	    // 如果左边的数字比右边的大,两边交换位置
	    arr[i] = [arr[i+1], arr[i+1] = arr[i]][0];
		swaped = true;
	  }
	}
	k = [1, 0][k]; // 奇偶数之间的转换
  }
  return arr;
}
var arr = [2, 3, 6, 4, 2, 1, 90, 100, 20, 5];
console.log(oddEvenSort(arr)); // [1, 2, 3, 4, 5, 6, 20, 90, 100]

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • JavaScript数据结构与算法-Sort

    这个方法需要 (n + 1 + n + 1) = 2n + 2 次运算。 我们把 算法需要执行的运算次数 用 输入大小n 的函数 表示,即 T(n) 。

    FinGet
  • JavaScript数据结构与算法-String

    思路:数字变字符串再变数组,这个主要就是运用的数组的常用api了,pop、shift、 unshift、join。

    FinGet
  • JavaScript数据结构与算法-Array

    例如:1 ^ 1 = 0 、 2 ^ 2 = 0、 0 ^ 1 = 1 、1 ^ 1 ^ 2 ^ 3 ^ 2 ^ 4 ^ 3 = 4

    FinGet
  • 快速排序(quick sort)C++实现

    每次选一个轴pivot(我选数组的第一个元素arr[p]),遍历其余数组元素使得比arr[p]大的数都在arr[p]的右边,比arr[p]小的数都在arr[p]...

    kalifa_lau
  • 常用算法比较,js实现

    <!DOCTYPE html> <html> <head> <meta charset="utf-8"> <title></title> <style>...

    前朝楚水
  • 排序算法之选择排序-java版

    选择排序类似于冒泡排序,均属于内排,也可以看做是对冒泡排序的优化。因为冒泡排序是比较相邻的两个值,然后直接交换。而选择排序是找到一个最大值或者最小值之后,再进行...

    shengjk1
  • JavaScript数组排序总结

    将数组中的相邻两个元素进行比较,将比较大(较小)的数通过两两比较移动到数组末尾(开始),执行一遍内层循环,确定一个最大(最小)的数,外层循环从数组末尾(开始)遍...

    用户4831957
  • 选择排序

    选择排序的思想,每次从剩余元素中最小的元素与当前元素交换,第一次从arr[0]arr[n-1]中选取最小值,与arr[0]交换;第二次从arr[1]arr[n-...

    桑鱼
  • JavaScript实现八大内部排序算法

    ? 注:基数排序中:r是关键字的基数,d是长度,n是关键字的个数 1.插入排序 基本思想:在序号i之前的元素(0到i-1)已经排好序,本趟需要找到i对应的元素...

    用户1149564
  • 快速排序

    参考:http://www.cnblogs.com/skywang12345/p/3596746.html  下面上代码: #include<iostream>...

    xcywt

扫码关注云+社区

领取腾讯云代金券