阅读 9

排序算法小结

问题:

常见的稳定排序算法有: 快速排序,冒泡排序,选择排序,归并排序,插入排序等。

1. 快速排序

快速排序采用的分治法的思想,每次递归将数组一份为三,最中间的是参考值,参考值左边的所有值都小于它,参考值右边的所有值都大于它。在此基础上进迭代,直到迭代输入的array长度小于2, 此时说明数组已经排序完成。

备注: 在JS中可以用filter方法过滤数据

代码实现:

function quickSort(array) {
    if (array.length < 2) return array;  // 递归出口
    let pivot = array[array.length-1];
    let left = array.filter((val, index) => val <= pivot && index !== array.length-1);  // 排除原来元素的情况
    let right = array.filter(val => val > pivot);  // 左右有一边判断相等情况即可
    return [...quickSort(left), pivot, ...quickSort(right)]
}
复制代码

时间复杂度:O(nlogn)

空间复杂度:O(nlogn)

2.冒泡排序

冒泡排序采用连续比较相邻两个数据的大小来更换位置,从而经过n次遍历到了所有的元素后就排好了顺序。

代码实现:

function bubbleSort(array) {
  // 两次循环套用即可实现排序,无需递归
  for (let i = 0; i < array.length; i++) {
    for (let j = 0; j < array.length -1 - i; j++) {
      if (array[j] > array[j + 1]) {
        [array[j], array[j+1]] = [array[j+1], array[j]];
      }
    }
  }
  return array;
}
复制代码

时间复杂度: O(n^2) 只适用于较少数据排序

3. 插入排序

从有序序列的尾部开始,逐个与目标元素比较,如果大于目标元素,该元素需要后移。在移动之前,要先缓存该带排序元素,腾出位置给其他元素移位。

function insertSort(array) {
  for (let i = 1; i < array.length; i++) {
    // 将数据缓存
    let j = i;
    let target = array[j];
    while(j > 0 && array[j-1] > target) {
      array[j] = array[j-1];
      j--;
    }
    array[j] = target;
  }
  return array;
}
复制代码

时间复杂度: O(n^2) 只适用于较少数据排序

4. 选择排序

每次遍历时,选择一个最小的交换到已排好序列的后面。所以关键点是怎么找到最小的那个元素。

function selectionSort(array) {
  for (let i = 0; i < array.length - 1; i++) {
    let minIndex = i;
    // 对还没有排序的元素遍历
    for (let j = i; j < array.length; j++) {
      if (array[minIndex] > array[j]) {
        minIndex = j;
      }
    }
    if (minIndex !== i) {
      [array[i], array[minIndex]] = [array[minIndex], array[i]];
    }
  }
  return array;
}
复制代码

时间复杂度: O(n^2) 只适用于较少数据排序

更新中......

关注下面的标签,发现更多相似文章
评论