0%

十大排序算法

发表于 更新于

一天两个，这周学完

我似乎不太能够写出分而治之、递归、二叉树的实现，能够理解，但是写不出来。

  • 归并排序（分而治之、递归）
  • 快排（递归）
  • 希尔排序（未知）（理解不了）
  • 堆排序（二叉树，递归）（理解不了）

https://www.runoob.com/w3cnote/ten-sorting-algorithm.html

冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢”浮”到数列的顶端。

算法步骤:

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// 插入排序（自己实现的）
function bubbleSort(arr: number[]) {
  let count = arr.length;
  // 每一次循环之后最后的值都是最大值
  // 所以每次循环之后减少往后一个的排序
  while (count >= 0) {
    for (let i = 1; i < count; i++) {
      // 之前这里写的是 i < arr.length，这明显是错误的，如果是arr.length 的话就没有意义了
      if (arr[i] < arr[i - 1]) {
        const temp = arr[i];
        arr[i] = arr[i - 1];
        arr[i - 1] = temp;
      }
    }
    count--;
  }
  return arr;
}

let arr = [];
let i = 100_000;
while (i > 0) {
  arr.push(i);
  i--;
}

// 插入排序（菜鸟教程实现的）
function bubbleSort2(arr) {
  var len = arr.length;
  for (var i = 0; i < len - 1; i++) {
    for (var j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        // 相邻元素两两对比
        var temp = arr[j + 1]; // 元素交换
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }
  return arr;
}

console.time("bubbleSort");
console.log(bubbleSort(arr)); // 平均运行时间 13s 将 i < arr.length 修改成 i < count 之后变成了 8s（略快于两个for）
console.timeEnd("bubbleSort");

console.time("bubbleSort2");
console.log(bubbleSort2(arr)); // 平均运行时间 8s
console.timeEnd("bubbleSort2");

选择排序

选择排序是一种简单直观的排序算法，无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。

算法步骤:

  1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
  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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
// 选择排序（自己实现的）
function selectionSort(arr: number[]) {
  let len = arr.length;
  for (let i = 0; i < len - 1; i++) {
    let min = arr[i];
    let minI = i;
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < min) {
        minI = j;
        min = arr[j];
      }
    }
    arr[minI] = arr[i];
    arr[i] = min;
  }
  return arr;
}

let arr = [];
let i = 100_000;
while (i > 0) {
  arr.push(i);
  i--;
}

// 选择排序（菜鸟实现的）
function selectionSort2(arr) {
  var len = arr.length;
  var minIndex, temp;
  for (var i = 0; i < len - 1; i++) {
    minIndex = i;
    for (var j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        // 寻找最小的数
        minIndex = j; // 将最小数的索引保存
      }
    }
    temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

// 在数量较少时，菜鸟实现的略快于自己实现的，随着数量增多，自己实现的更快

console.time("selectionSort");
console.log(selectionSort(arr)); // 4s
console.timeEnd("selectionSort");

console.time("selectionSort2");
console.log(selectionSort2(arr)); // 5s
console.timeEnd("selectionSort2");

插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

平均插入排序算法的时间复杂度为 O(n²)。因而，插入排序不适合对于数据量比较大的排序应用。但是，如果需要排序的数据量很小（eg：量级小于千），那么插入排序是一个不错的选择

算法步骤:

  1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
  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
// 插入排序
// 空间复杂度 O(1)
// 时间复杂度 O(n) - O(n^2)
function insertionSort(arr: number[]) {
  let preI: number, current: number;
  for (let i = 1; i < arr.length; i++) {
    current = arr[i];
    preI = i - 1;
    while (preI >= 0 && arr[preI] > current) {
      arr[preI + 1] = arr[preI];
      preI--;
    }
    arr[preI + 1] = current;
  }
  return arr;
}

let arr = [];
let i = 10;
while (i > 0) {
  arr.push(i);
  i--;
}

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
23
// 希尔排序
function shellSort(arr: number[]) {
  let len = arr.length,
    temp: number,
    gap = 1;
  while (gap < len / 3) {
    //动态定义间隔序列
    gap = gap * 3 + 1;
  }
  for (gap; gap > 0; gap = Math.floor(gap / 3)) {
    for (let i = gap; i < len; i++) {
      temp = arr[i];
      let j = i - gap;
      for (; j >= 0 && arr[j] > temp; j -= gap) {
        arr[j + gap] = arr[j];
      }
      arr[j + gap] = temp;
    }
  }
  return arr;
}

console.log(shellSort([5,4,1,2,3,21,3,54,6,78,23,4,6,2,34,345,345,1,35,457,345,5,543,423,45,1,221,1,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
// 归并排序
function merge(left: number[], right: number[]) {
  let res = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) {
      res.push(left.shift());
    } else {
      res.push(right.shift());
    }
  }
  while (left.length) {
    res.push(left.shift());
  }
  while (right.length) {
    res.push(right.shift());
  }
  return res;
}

function mergeSort(arr: number[]) {
  let len = arr.length;
  if (len < 2) {
    return arr;
  }
  let middle = Math.floor(len / 2),
    left = arr.slice(0, middle),
    right = arr.slice(middle);
  return merge(mergeSort(left), mergeSort(right));
}

快速排序

不行，我能够理解快排，但是完全没有办法实现快排。

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
36
37
function swap(arr: number[], i: number, j: number) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

// 分区操作
function partition(arr: number[], left: number, right: number) {
  let pivot = left; // 设定基准值（pivot）
  let index = pivot + 1;
  for (let i = index; i <= right; i++) {
    if (arr[i] < arr[pivot]) {
      swap(arr, i, index);
      index++;
    }
  }
  swap(arr, pivot, index - 1);
  return index - 1;
}

function quickSort(arr: number[], left?: number, right?: number) {
  let len = arr.length;
  let partitionIndex: number;
  left = typeof left != "number" ? 0 : left;
  right = typeof right != "number" ? len - 1 : right;

  if (left < right) {
    partitionIndex = partition(arr, left, right);
    console.log(partitionIndex)
    quickSort(arr, left, partitionIndex - 1);
    quickSort(arr, partitionIndex + 1, right);
  }
  return arr;
}


const arr = quickSort([5, 4, 1, 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
36
37
38
39
40
41
42
43
44
45
46
let len: number; // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量

function swap(arr: number[], i: number, j: number) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function heapify(arr: number[], i: number) {
  // 堆调整
  let left = 2 * i + 1,
    right = 2 * i + 2,
    largest = i;

  if (left < len && arr[left] > arr[largest]) {
    largest = left;
  }

  if (right < len && arr[right] > arr[largest]) {
    largest = right;
  }

  if (largest != i) {
    swap(arr, i, largest);
    heapify(arr, largest);
  }
}

function buildMaxHeap(arr: number[]) {
  // 建立大顶堆
  len = arr.length;
  for (let i = Math.floor(len / 2); i >= 0; i--) {
    heapify(arr, i);
  }
}

function heapSort(arr: number[]) {
  buildMaxHeap(arr);

  for (let i = arr.length - 1; i > 0; i--) {
    swap(arr, 0, i);
    len--;
    heapify(arr, 0);
  }
  return arr;
}

计数排序

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。

算法步骤

  1. 找出待排序的数组中最大和最小的元素
  2. 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
  3. 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
  4. 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
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
36
37
38
39
40
41
42
function countingSort(arr: number[]) {
  let min = arr[0],
    max = arr[0];
  // 第一步找出最大值和最小值
  for (let i = 0; i < arr.length; i++) {
    const num = arr[i];
    if (num < min) {
      min = num;
    } else if (num > max) {
      max = num;
    }
  }

  // 第二部根据最大值最小值给出存储范围
  const array = new Array(max - min + 1);
  for (let i = 0; i < arr.length; i++) {
    const num = arr[i];
    // 第三步，对计数累加
    array[num - min] = array[num - min] ? array[num - min] + 1 : 1;
  }
  arr = [];
  // 遍历临时存储数组中每项出现的次数，反向添加到结果数组中
  for (let i = 0; i < array.length; i++) {
    const num = array[i];
    for (let j = 0; j < num; j++) {
      // 这里加上 min 是因为在第三步的时候减去了。
      // 在不减去的情况下，当min数值很大的时候就会出现很多空间被浪费掉
      arr.push(i + min);
    }
  }
  return arr;
}

let arr = [];
let i = 100;
while (i > 0) {
  arr.push(i);
  i--;
}
console.time("countingSort");
console.log(countingSort(arr));
console.timeEnd("countingSort");

桶排序

桶排序是计数排序的升级版，计数排序适用于紧凑型的数据进行排序，当数据间隔大了之后就会出现空间浪费的问题。

它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：

  1. 在额外空间充足的情况下，尽量增大桶的数量
  2. 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中

同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。

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
36
37
38
39
40
41
42
43
44
45
46
47
// 桶排序
function bucketSort(arr: number[], bucketSize = 5) {
  let min = arr[0];
  let max = arr[0];

  for (let i = 0; i < arr.length; i++) {
    const e = arr[i];
    if (e < min) {
      min = e;
    } else if (e > max) {
      max = e;
    }
  }

  const bucketCount = Math.floor((max - min) / bucketSize) + 1;

  let buckets = new Array(bucketCount);

  for (let i = 0; i < buckets.length; i++) {
    buckets[i] = [];
  }

  for (let i = 0; i < arr.length; i++) {
    buckets[Math.floor((arr[i] - min) / bucketSize)].push(arr[i]);
  }

  arr.length = 0;
  for (let i = 0; i < buckets.length; i++) {
    insertionSort(buckets[i]); // 对每个桶进行排序，这里使用了插入排序
    for (var j = 0; j < buckets[i].length; j++) {
      arr.push(buckets[i][j]);
    }
  }

  return arr;
}

let arr = [];
let i = 100_000;
while (i > 0) {
  arr.push(i);
  i--;
}

console.time("a");
console.log(bucketSort(arr));
console.timeEnd("a");

基数排序

基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。

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
36
37
38
39
40
41
42
43
/**
 * 获取数组中最长的元素
 * @returns number
 */
function getMaxLen(arr: number[]) {
  let maxLen = 0;
  for (let i = 0; i < arr.length; i++) {
    const num = arr[i];
    if (num.toString().length > maxLen) maxLen = num.toString().length;
  }
  return maxLen;
}
// 基数排序
// 这个没办法排序负数呀
function radixSort(arr: number[]) {
  const maxDigit = getMaxLen(arr);
  for (let i = 0; i < maxDigit; i++) {
    // 创建一个二维数组，用于临时存放
    const arrays: number[][] = [];
    for (let j = 0; j < arr.length; j++) {
      const numS = arr[j].toString();
      // 由后往前，根据下标分配到相应的数组中，当位数不足时分配到0
      const n = Number(numS[numS.length - i - 1]) || 0;
      if (arrays[n] === undefined) arrays[n] = [];
      arrays[n].push(arr[j]);
    }
    arr = [];
    for (let j = 0; j < arrays.length; j++) {
      const array = arrays[j] || [];
      // 先进先出，放入arr中
      for (let k = 0; k < array.length; k++) {
        const num = array[k];
        arr.push(num);
      }
    }
    console.log(arr);
  }
  return arr;
}

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