算法基础01 常用排序算法

发表于 更新于 分类于 阅读次数：

JS常用排序算法的总结。

所有算法的动画演示

冒泡排序（Bubble Sort）

对相邻的两个对象进行比较，如果后者小于前者，把小的放前面

时间复杂度：O(n²)

1
2
3
4
5
6
7
8
9
10
11
12
// 对比arr中的第j+1项和第j项，如果第j+1项小于第j项，就把第j+1项和第j项调换位置。
// 如果没达到最终的顺序（从小到大），就继续找，继续换，直到达到最终效果
function bubbleSort(arr) {
  for (var i = 0; i < arr.length - 1; i++) {
    for (var j = 0; j < arr.length - 1; j++) {
      if (arr[j + 1] < arr[j]) {
        [tempArr[j], tempArr[j + 1]] = [tempArr[j + 1], tempArr[j]];
      }
    }
  }
  return arr;
}

（2018.4.3补充）
发现在内层循环时，可以改变内层循环的范围为 j<arr.length-1-i, 原因是

  • 当 i=0 的时候，里面的循环完整执行，第一遍排序，结果是将最大的数排到了最后
  • 当 i=1 的时候，里面的循环再次完整执行，由于最大的数已经在最后了，没有必要去比较数组的最后两项，这也是 j<arr.length-1-i 的巧妙之处

优化冒泡排序算法

对冒泡排序进行优化，设定一个变量flag，用于表明是否进行了位置交换，如果没有交换位置，则说明当前排序完成，结束循环

时间复杂度：O(n²)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function bubbleSort(arr) {
  let isOver = false;
  for (var i = 0; i < arr.length - 1; i++) {
    isOver = true;
    for (var j = 0; j < arr.length - 1; j++) {
      if (arr[j + 1] < arr[j]) {
        [tempArr[j], tempArr[j + 1]] = [tempArr[j + 1], tempArr[j]];
        isOver = false;
      }
    }
    // 内部循环一轮都不需要调换位置，说明全部排序已完成，没有必要再继续外部循环
    if (isOver) {
      return arr;
    }
  }
  return arr;
}

选择排序（Selection Sort）

首先在乱序的数组中选择出最小的值，然后和每次循环后的数组第一位进行交换

时间复杂度：O(n²)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const x = [0, 5, 3, 2, 4, 1, 10];
function chooseSort (arr) {
  let tempArr = [...arr];
  for (let i = 0; i < tempArr.length; i++) {
    let maxIndex = i;
    for (let j = i; j < tempArr.length; j++) {
      if (tempArr[j] > tempArr[maxIndex]) {
        maxIndex = j
      }
    }
    if (maxIndex !== i) {
      [tempArr[i], tempArr[maxIndex]] = [tempArr[maxIndex], tempArr[i]];
    }
  }
  return tempArr;
}
console.log(chooseSort(x))

插入排序（Insert Sort）

对数组进行循环，当循环到i时，认为i之前的项目都已经排好序了，对i+1进行处理，将i+1项插入到已经排好序的队列中，插入的方法就是从i+1开始，向回循环，两两比较，根据比较结果进行换位

时间复杂度：O(n²)

1
2
3
4
5
6
7
8
9
10
11
12
const x = [0, 5, 3, 2, 4, 1, 10];
function insertSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j > 0; j--) {
      if (arr[j - 1] < arr[j]) {
        [arr[j], arr[j - 1]] = [arr[j - 1], arr[j]];
      }
    }
  }
  return arr;
}
console.log(insertSort(x))

归并排序（Merge Sort）

把一个数组分为两个数组，左边排好序，右边排好序，然后合并到一起排序。

归并排序是分治法的典型实例，指的是将两个已经排序的序列合并成一个序列的操作

时间复杂度：O(nlogn)

排序过程：

image

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
var arr = [-11, 17, 12, 19, 0, -222];
function mergeSort(arr, s, e) {
  if (s > e) {   //起始位置大于终点位置，返回空数组
    return [];
  } else if (s == e) {
    return [arr[s]]; //起始位置等于终点位置，说明数组里只有一个数字，返回只含一个数字的数组    
  }

  var mIndex = Math.floor((s + e) / 2); //中间位置的Index
  var arrL = mergeSort(arr, s, mIndex); //将左边的数组排序
  var arrR = mergeSort(arr, mIndex + 1, e); //将右边的数组排序

  var resultArr = []; //结果数组
  while (arrL.length > 0 && arrR.length > 0) { //当左右两个数组都不为空时
    if (arrL[0] < arrR[0]) {
      resultArr.push(arrL.shift());
    } else {
      resultArr.push(arrR.shift());
    }

    if (arrL.length == 0) {  //当左边的数组为空时
      resultArr = resultArr.concat(arrR);
      break;
    } else if (arrR.length == 0) {
      resultArr = resultArr.concat(arrL);
      break;
    }
  }
  return resultArr;
}

document.write(mergeSort(arr, 0, arr.length - 1));

快速排序（quickSort）

  1. 在数据集之中，选择一个元素作为”基准”（pivot）
  2. 所有小于”基准”的元素，都移到”基准”的左边；所有大于”基准”的元素，都移到”基准”的右边。
  3. 对”基准”左边和右边的两个子集，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var arr = [77, -33, 22, 32, 0, 2, 11];
function quickSort(arr) {
  // 递归结束条件
  if (arr.length <= 1) {
    return arr;
  }
  // 选择基准元素，并且从原数组中暂时剔除
  const index = Math.floor(arr.length / 2);
  const base = arr.splice(index, 1)[0];
  // 将数组分为左右组
  let left = [];
  let right = [];
  // 对所有元素进行遍历，将大于基准值的放在左边，小于基准值的放在右边
  for (let i = 0; i < arr.length; i++) {
    (arr[i] < base ? right : left).push(arr[i])
  }
  // quickSort(left)对左边的合集进行递归
  // quickSort(right)对右边的合集进行递归
  // 连接起来，再加上基准元素就是完整合集
  return quickSort(left).concat([base], quickSort(right))
}

document.write(quickSort(arr));

image

计数排序

时间复杂度为O(N)

用空间换时间的算法，适用于提前知道数字范围，并且相差范围不大的情况

将数字放到对应的数组对象中，然后进行排序

这种方法不能对应数组中有负数的情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
let arr = [100, 2, 3, 1, 5, 22, 33, 11, 22, 33];

function sort(arr) {
  let temp = [];

  for (let i = 0; i < arr.length; i++) {
    if (!temp[arr[i]]) {
      temp[arr[i]] = 1;
    }
    else {
      temp[arr[i]]++;
    }
  }
  
  let result = [];
  for (let j = 0; j < temp.length; j++) {
    if (temp[j]) {
      for (let k = 0; k < temp[j]; k++) {
        result.push(j)
      }
    }
  }
  return result;

}
console.log(sort(arr))

参考