排序算法

发表于 更新于 分类于

冒泡排序

外循环会从数组的第一位迭代至最后一位，它控制了在数组中经过多少轮排序，每一轮比较都会把数组中最大的数放到最后。

下面的内循环代码中 减去了 i 是因为减去外循环中已经跑过的轮数，就可以避免内循环中所有不必要的比较。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 冒泡排序
function bubbleSort(arr) {
  const { length } = arr;
  console.time('冒泡排序耗时');
  for(let i = 0; i < length; i ++) {
    for(let j = 0; j < length - 1 - i; j ++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  console.timeEnd('冒泡排序耗时');
  return arr;
}

let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(bubbleSort(arr));

选择排序

选择排序算法是一种原址比较排序算法。大致思路是找到数据结构中的最小值并将其放置在第一位，接着找到第二小的值并将其放在第二位，以此类推。

下面代码中 minIndex 记录的是每一轮最小值的位置，内循环选出 minIndex 后外循环进行交换，一共需要进行 len - 1 轮

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 选择排序
function selectionSort(arr) {
  let { length } = arr;
  let minIndex;
  console.time('选择排序耗时');

  for(let i = 0; i < length - 1; i ++) {
    minIndex = i;
    for(let j = i + 1; j < length; j ++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (i !== minIndex) {
      [arr[minIndex], arr[i]] = [arr[i], arr[minIndex]];
    }
  }
  console.timeEnd('选择排序耗时');
  return arr;
}

let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(selectionSort(arr));

插入排序

原理很简单，就像打扑克牌的时候一样按顺序整理牌。如果后一个大于前一个，那么就插入，小于的话就不做交换。

  1. 从第一个元素开始，该元素可以认为已经被排序；

  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；

  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；

  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

  5. 将新元素插入到该位置后；

  6. 重复步骤2~5。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 插入排序
function insertionSort(arr) {
    let len = arr.length;
    console.time('插入排序耗时');
    for (let i = 1; i < len; i++) {
        for (let j = i; j > 0; j--) {
            if (arr[j] < arr[j - 1]) {
                [ arr[j], arr[j - 1] ] = [ arr[j - 1], arr[j] ];
            } else {
                continue;
            }
        }
    }
    console.timeEnd('插入排序耗时');
    return arr;
}

let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(insertionSort(arr));

希尔排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 希尔排序
function shellSort(arr,gap) {
    console.log(arr)//为了方便观察过程，使用时去除
    for(let i = 0; i<gap.length; i ++) {  //最外层循环，一次取不同的步长，步长需要预先给出
        let n = gap[i]; //步长为n
        for(let j = i + n; j < arr.length; j ++) { //接下类和插入排序一样，j循环依次取后面的数
            for(let k = j; k > 0; k-=n) { //k循环进行比较，和直接插入的唯一区别是1变为了n
                if(arr[k] < arr[k-n]) {
                    [arr[k],arr[k-n]] = [arr[k-n],arr[k]];
                    console.log(`当前序列为[${arr}] \n 交换了${arr[k]}和${arr[k-n]}`)//为了观察过程
                } else {
                    continue;
                }
            }
        }
    }
    return arr;
}

let arr = [3, 2, 45, 6, 55, 23, 5, 4, 8, 9, 19, 0];
let gap = [3,2,1];
console.log(shellSort(arr,gap))

归并排序

分而治之思想的算法应用：算法首先将原始数组分割直至只有一个元素的子数组，然后开始归并。

  1. 把长度为n的输入序列分成两个长度为n/2的子序列；

  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
24
25
26
27
28
29
30
31
32
33
34
35
// 归并排序
function mergeSort(arr) {  //采用自上而下的递归方法
    var len = arr.length;
    if (len < 2) {
        return arr;
    }
    var middle = Math.floor(len / 2),
        left = arr.slice(0, middle),
        right = arr.slice(middle);
    return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
    let 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) {
        result.push(right.shift());
    }

    return result;
}

let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(mergeSort(arr));

快速排序

分而治之思想在排序算法上的典型应用

  1. 从数列中挑出一个元素，称为 “基准”（pivot）；

  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；

  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// 快速排序
function quickSort(arr) {
  if (arr.length <= 1) {
    return arr;
  }
  let pivotIndex = Math.floor(arr.length / 2);
  let pivot = arr.splice(pivotIndex, 1)[0];
  let left = [];
  let right = [];
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] < pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }
  return [...quickSort(left), pivot, ...quickSort(right)]
  // return quickSort(left).concat([pivot], quickSort(right));
};

let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
console.log(quickSort(arr));

参考

十大经典排序算法总结（JavaScript描述）