数据结构与算法之常见的排序算法 yinshibanxian

19 May 2020 3860字 13分 次
BY-SA 4.0（除特别声明或转载文章外）

一、冒泡排序

  1. 实现原理:

    数组中有n个数，每比较相邻的两个数，如果前者大于后者，就把两个数交换位置。

    这样一来，第一轮可以选出一个最大的数放在最后面，那么经过n-1轮，就完成了

    所有数的排序

  2. 性能:

    时间复杂度: 平均复杂度:O(n^2),最好情况O(n)，最坏情况O(n^2)

    稳定性: 稳定

    (什么是稳定性?对于数组中的两个元素a和b，且有a=b，若排序后a,b的相对位置没有发生变化，

    （比如排序前a在b的前面，排序后a仍在b的前面），则称该排序算法是稳定的，反之则称该排序算法不稳定)

    空间复杂度: O(1)

  3. 代码实现

    首先实现超出数组中的最大数，并把它放到数组的最后方

     const arr = [4,3,2,1];
 for(let j = 0;j < arr.length - 1;j ++) {
     if(arr[j] > arr[j+1]) {
         [arr[j],arr[j+1]] = [arr[j+1],arr[j]]; 
     }
 }
 console.log(arr); // [ 3, 2, 1, 4 ]

    这样的过程进行n-1轮

     const arr = [4,3,2,1];

 function bubbleSort(arr) {
     for(let i = 0;i < arr.length - 1;i ++) {
         for(let j = 0;j < arr.length - 1;j ++) {
             if(arr[j] > arr[j+1]) {
                 [arr[j],arr[j+1]] = [arr[j+1],arr[j]];  // 交换两个元素的位置
             }
         }
     }
 }

 bubbleSort(arr);
 console.log(arr); // [1,2,3,4]

    实际上，第一次已经找到数组中最大的元素了，因此在下一次循环，不需要再考虑最后一个元素，

    以此类推，内层循环当中可以减去外层循环的次数，优化如下:

     const arr = [4,3,2,1];

 function bubbleSort(arr) {
     for(let i = 0;i < arr.length - 1;i ++) {
         for(let j = 0;j < arr.length - 1 - i;j ++) { // 减去外层循环次数
             if(arr[j] > arr[j+1]) {
                 [arr[j],arr[j+1]] = [arr[j+1],arr[j]]; 
             }
         }
     }
 }

 bubbleSort(arr);
 console.log(arr); // [1,2,3,4]

二、选择排序

  1. 实现原理

  • 第一次遍历中，找到最小的数组元素然后用第一个数组元素交换它。

  • 第二次遍历中，找到第二小的数组元素然后用第二个数组元素交换它。

  • 依次类推。如果包含N个元素，那么将在最多N-1次遍历之后完成排序。

  1. 性能
  • 时间复杂度: 最好情况O(n)，最坏情况O(n^2)，平均复杂度O(n^2)
  • 稳定性: 不稳定
  • 空间复杂度： O(1)
  1. 代码实现
const arr = [4,3,2,1];

function selectionSort(arr) {
    let minIdex;
    for(let i = 0;i < arr.length - 1;i ++) {
        minIdex = i;
        // 找出最小的元素序号
        for(let j = i + 1;j < arr.length;j ++) {
            if(arr[j] < arr[minIdex]) {
                minIdex = j;
            }
        }
        if(i !== minIdex) {
            [arr[minIdex],arr[i]] = [arr[i],arr[minIdex]];
        }
    }
}
selectionSort(arr);
console.log(arr); // [1,2,3,4]

三、插入排序

  1. 实现原理 从待排序数组的第二个元素开始，依次与待插入元素前面的元素比较，若前面的元素

    比待插入元素大，则把前一个元素往后移动，一直到待插入元素大于或等于前一个元素为止。

  2. 性能

    • 时间复杂度: 最好情况(数组已正序)O(n)，最坏情况(数组逆序)O(n^2),平均复杂度O(n^2)
    • 稳定性： 稳定
    • 空间复杂度: O(1)

  3. 实现代码

const arr = [4,3,2,1];

function insertionSort(arr) {
    let temp;
    for(let i = 1;i < arr.length;i ++) {
        let j = i;
        temp = arr[i];
        while(j > 0 && arr[j-1] > temp) {
            arr[j] = arr[j-1];
            j --;
        }
        arr[j] = temp;
    }
}
insertionSort(arr);
console.log(arr); // [1,2,3,4]

四、归并排序

  1. 实现原理

    归并排序是一种分而治之的算法。其原理是将原始数组切分成较小的数组，直到每个小数组只有一个位置，接着将小数组

    归并成较大的数组，到最后只有一个排序完毕的大数组。

  2. 性能

  • 时间复杂度: 最好情况O(nlgn)，最坏情况下O(nlgn),平均复杂度O(nlgn)
  • 稳定性: 稳定
  • 空间复杂度: O(n)
  1. 实现代码:
const nums = [3,1,2,4,5];

const mergeSort = function(nums) {
    if(nums.length < 2) return nums;
    const middle = Math.floor(nums.length / 2);
    const left = nums.slice(0,middle);
    const right = nums.slice(middle);
    return merge(mergeSort(left),mergeSort(right));
}

const merge = function(left,right) {
    const result = [];
    while(left.length && right.length) {
        if(left[0] <= right[0]) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }
    while(left.length) {
        result.push(left.shift());
    }
    while(right.length) {
        」「09I*J result.pus
        h(right.shift());
    }
    return result;
}

console.log(mergeSort(nums)); // 1 2 3 4 5

五、快速排序

  1. 原理: 快排是一种分治的思想，首先从数组中选出一个值作为基准值，数组中比基准小的元素放到左边序列，大的元素放到右边序列。 然后再递归地对左边序列和右边序列进行相同的操作，最终得到一个有序的数组.

  2. 性能

  • 时间复杂度: 最坏情况O(n^2)，最好情况O(nlgn),平均复杂度O(nlgn)
  • 稳定性: 不稳定
  • 空间复杂度： O(n)
  1. 代码实现
const nums = [3,1,2,4,5];

const quickSort = function(nums) {
    if(nums.length < 2) return nums;
    const left = [];
    const right = [];
    const middleIndex = Math.floor(nums.length / 2);
    const basic = nums[middleIndex];
    for(let i = 0;i < nums.length;i ++) {
        if(i == middleIndex) continue;
        if(nums[i] <= basic) {
            left.push(nums[i]);
        } else {
            right.push(nums[i]);
        }
    }
    return quickSort(left).concat(basic,quickSort(right));
}

console.log(quickSort(nums)); // [1,2,3,4,5]

六、计数排序

  1. 原理: 计数排序使用一个用来存储每个元素在原始数组中出现次数的临时数组。在所有元素都计数完成之后，临时数组已排好序并可迭代以构建排序后的结果数组。

     计数排序用来排序整数。

  2. 性能:

    • 时间复杂度: O(n+k)，k为临时数组的长度
    • 空间复杂度: O(k),k为临时数组的长度

  3. 代码实现

/**
 * 范围在 start - end 之间的排序
 * 计数排序需要辅助数组，该辅助数组的长度是待排序数组的范围，所以一般用作范围小于100的排序
 */
const nums = [2,1,3,4];
function countingSort(nums) {
  if(nums.length < 2) return nums;
  // 找到数组中的最大值
  const maxValue = findMaxValue(nums);
  // 常见一个从0 ~ maxValue的临时数组，用于记录数组中每个元素出现的次数
  const counts = new Array(maxValue + 1).fill(0);
  nums.forEach((num) => {
    counts[num] ++;
  });
  let sortedIndex = 0;
  counts.forEach((count,i) => {
    while(count > 0) {
      nums[sortedIndex++] = i;
      count --;
    }
  })
  return nums;
}

function findMaxValue(nums) {
  let maxValue = nums[0];
  for(let i = 1;i < nums.length;i ++) {
    maxValue = Math.max(maxValue,nums[i]);
  }
  return maxValue;
}

console.log(countingSort(nums));

参考文章:https://juejin.im/post/5bdf13fe51882516f039ff7c