冒泡排序
排序的效果图
解法
当前解法为升序
冒泡排序的特点，是一个个数进行处理。第i个数，需要与后续的len-i-1个数进行逐个比较。
为什么是 `len-i-1`个数？
因为数组末尾的i个数，已经是排好序的，确认位置不变的了。
为什么确认位置不变，因为它们固定下来之前，已经和前面的数字都一一比较过了。
1. function bubbleSort(arr){
2. const len = arr.length;
3. for(let i = 0; i < len - 1; i++){
4. for(let j = 0; j < len - i - 1; j++){
5. if(arr[j] > arr[j+1]){
6. const tmp = arr[j+1];
7. arr[j+1] = arr[j];
8. arr[j] = tmp;
9. }
10. }
11. }
12.
13. return arr;
14.}
快速排序
概要
快速排序，使用的是分治法的思想。
通过选定一个数字作为比较值，将要排序其他数字，分为 >比较值 和 <比较值，两个部分。并不断重复这个步骤，直到只剩要排序的数字只有本身，则排序完成。
效果图
解法
1. function quickSort(arr){
2. sort(arr, 0, arr.length - 1);
3. return arr;
4. function sort(arr, low, high){
5. if(low >= high){
6. return;
7. }
8. let i = low;
9. let j = high;
10. const x = arr[i]; // 取出比较值x，当前位置i空出，等待填入
11. while(i < j){
12. // 从数组尾部，找出比x小的数字
13. while(arr[j] >= x && i < j){
14. j--;
15. }
16. // 将空出的位置，填入当前值， 下标j位置空出
17. // ps：比较值已经缓存在变量x中
18. if(i < j){
19. arr[i] = arr[j]
20. i++;
21. }
22. // 从数组头部，找出比x大的数字
23. while(arr[i] <= x && i < j){
24. i++;
25. }
26. // 将数字填入下标j中，下标i位置突出
27. if(i < j){
28. arr[j] = arr[i]
29. j--;
30. }
31. // 一直循环到左右指针i、j相遇，
32. // 相遇时，i==j, 所以下标i位置是空出的
33. }
34. arr[i] = x; // 将空出的位置，填入缓存的数字x，一轮排序完成
35. // 分别对剩下的两个区间进行递归排序
36. sort(arr, low, i - 1);
37. sort(arr, i+1, high);
38. }
39.}
希尔排序
概要
希尔排序是一种插入排序的算法，它是对简单的插入排序进行改进后，更高效的版本。由希尔（Donald Shell）于1959年提出。
特点是利用增量，将数组分成一组组子序列，然后对子序列进行插入排序。
由于增量是从大到小，逐次递减，所以也称为缩小增量排序。
效果图
解法
注意点
插入排序时，并不是一个分组内的数字一次性用插入排序完成，而是每个分组交叉进行。
执行插入时，使用交换法
1. function shellSort(arr){
2. // 分组规则 gap/2 递减
3. for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)){
4. for(let i = gap; i < arr.length; i++){
5. let j = i;
6. // 分组内数字，执行插入排序，
7. // 当下标大的数字，小于 下标小的数字，进行交互
8. // 这里注意，分组内的数字，并不是一次性比较完，需要i逐步递增，囊括下个分组内数字
9. while(j - gap >= 0 && arr[j] < arr[j - gap]){
10. swap(j, j-gap);
11. j = j - gap;
12. }
13. }
14. }
15.
16. return arr;
17.
18. function swap(a, b){
19. const tmp = arr[a];
20. arr[a] = arr[b];
21. arr[b] = tmp;
22. }
23.}
执行插入时，使用移动法
1. function shellSort(arr){
2.
3. for(let gap = Math.floor(arr.length/2); gap > 0; gap = Math.floor(gap/2)){
4. for(let i = gap; i < arr.length; i++){
5. let j = i;
6. const x = arr[j]; // 缓存数字，空出位置
7.
8. while(j - gap >= 0 && x < arr[j-gap]){
9. arr[j] = arr[j - gap]; // 将符合条件的数字，填入空出的位置
10. j = j - gap;
11. }
12. arr[j] = x; // 最后，将缓存的数字，填入空出的位置
13. }
14. }
15.
16. return arr;
17.}
选择排序
排序的效果图
解法
当前解法为升序
1. function selectionSort(arr){
2. const len = arr.length;
3.
4. for(let i = 0; i < len-1; i++){
5. let minIndex = i;
6. for(let j = i+1; j < len; j++){
7. if(arr[j] < arr[minIndex]){
8. minIndex = j; // 保存最小数的下标
9. }
10. }
11.
12. const tmp = arr[i];
13. arr[i] = arr[minIndex];
14. arr[minIndex] = tmp;
15. }
16.
17. return arr;
18.}
归并排序
概要
归并排序，利用分治思想，将大的数组，分解为小数组，直至单个元素。然后，使用选择排序的方式，对分拆的小数组，进行回溯，并有序合并，直至合并为一个大的数组。
效果图
小数组合并的过程
解法
1. function mergeSort(arr){
2. return sort(arr, 0, arr.length - 1); // 注意右区间是arr.length - 1
3. // sort方法，进行递归
4. function sort(arr, left, right){
5. // 当left !== right时，证明还没分拆到最小元素
6. if(left < right){
7. // 取中间值，分拆为两个小的数组
8. const mid = Math.floor((left+right) / 2);
9. const leftArr = sort(arr, left, mid);
10. const rightArr = sort(arr, mid+1, right);
11. // 递归合并
12. return merge(leftArr, rightArr)
13. }
14. // left == right, 已经是最小元素，直接返回即可
15. return left >= 0 ? [arr[left]] : [];
16. }
17. // 合并两个有序数组
18. function merge(leftArr, rightArr){
19. let left = 0;
20. let right = 0;
21. const tmp = [];
22. // 使用双指针，对两个数组进行扫描
23. while(left < leftArr.length && right < rightArr.length){
24. if(leftArr[left] <= rightArr[right]){
25. tmp.push(leftArr[left++]);
26. }else{
27. tmp.push(rightArr[right++]);
28. }
29. }
30. // 合并剩下的内容
31. if(left < leftArr.length){
32. while(left < leftArr.length){
33. tmp.push(leftArr[left++]);
34. }
35. }
36. if(right < rightArr.length){
37. while(right < rightArr.length){
38. tmp.push(rightArr[right++]);
39. }
40. }
41. return tmp;
42. }
43.}
插入排序
排序的效果图
解法
当前解法为升序
1. function insertionSort(arr){
2. const len = arr.length;
3. // 注意，i 从 1 开始
4. for(let i = 1; i < len; i++){
5. let preIndex = i - 1;
6. let current = arr[i];
7. // 位置i之前，是已排好序的数字，while的作用是找到一个坑位，给当前数字current插入
8. while(preIndex >= 0 && arr[preIndex] > current){
9. arr[preIndex+1] = arr[preIndex]; // 对大于current的值，往后移一位，给current的插入腾出位置
10. preIndex--;
11. }
12. arr[preIndex+1] = current;
13. }
14. return arr;
15.}
堆排序
概要
堆的表示形式
逻辑结构的表示如下：
在物理数据层的表示如下：
堆排序，是选择排序的优化版本，利用数据结构——树，对数据进行管理。
以大顶堆为例:
通过构建大顶堆
将堆顶的最大数拿出，与堆底的叶子节点进行交换
接着，树剪掉最大数的叶子
再对堆进行调整，重新变成大顶堆
返回步骤2，以此循环，直至取出所有数
效果图
在实现代码时，构建大顶堆时，先保证左右子树的有序，再逐步扩大到整棵树。
构建大顶堆
从第一个非叶子节点开始，调整它所在的子树
调整下标1节点的子树后，向上继续调整它的父节点（下标0）所在的子树
最后，完成整个树的调整，构建好大顶堆。
逐个抽出堆顶最大值
堆顶数字与最末尾的叶子数字交换，抽出堆顶数字9。
此时，数字9位置固定下来，树剪掉9所在的叶子。然后，重新构建大顶堆。
大顶堆构建好后，继续抽出堆顶数字8，然后再次重新构建大顶堆。
最后，所有节点抽出完成，代表排序已完成。
解法
以大顶堆为例，对数组进行升序排序
注意点
树的最后一个非叶子节点：(arr.length / 2) - 1
非叶子节点i的左叶子节点： i*2+1
非叶子节点i的右叶子节点： i*2+2
1. function heapSort(arr){
2. // 初次构建大顶堆
3. for(let i = Math.floor(arr.length/2) - 1; i >= 0; i--){
4. // 开始的第一个节点是 树的最后一个非叶子节点
5. // 从构建子树开始，逐步调整
6. buildHeap(arr, i, arr.length);
7. }
8. // 逐个抽出堆顶最大值
9. for(let j = arr.length -1 ; j > 0; j--){
10. swap(arr, 0, j); // 抽出堆顶（下标0）的值，与最后的叶子节点进行交换
11. // 重新构建大顶堆
12. // 由于上一步的堆顶最大值已经交换到数组的末尾，所以，它的位置固定下来
13. // 剩下要比较的数组，长度是j,所以这里的值length == j
14. buildHeap(arr, 0, j);
15. }
16. return arr;
17. // 构建大顶堆
18. function buildHeap(arr, i, length){
19. let tmp = arr[i];
20. for(let k = 2*i+1; k < length; k = 2*k+1){
21. // 先判断左右叶子节点，哪个比较大
22. if(k+1 < length && arr[k+1] > arr[k]){
23. k++;
24. }
25. // 将最大的叶子节点，与当前的值进行比较
26. if(arr[k] > tmp){
27. // k节点大于i节点的值，需要交换
28. arr[i] = arr[k]; // 将k节点的值与i节点的值交换
29. i = k; // 注意：交换后，当前值tmp的下标是k，所以需要更新
30. }else{
31. // 如果tmp大于左右子节点，则它们的子树也不用判断，都是小于当前值
32. break;
33. }
34. }
35. // i是交换后的下标，更新为tmp
36. arr[i] = tmp;
37. }
38. // 交换值
39. function swap(arr, i, j){
40. const tmp = arr[i];
41. arr[i] = arr[j];
42. arr[j] = tmp;
43. }
44.}
计数排序
概要
计数排序的要点，是开辟一块连续格子组成的空间，给数据进行存储。
将数组中的数字，依次读取，存入其值对应的下标中。
储存完成后，再按照空间的顺序，依次读取每个格子的数据，输出即可。
所以，计数排序要求排序的数据，必须是有范围的整数。
效果图
解法
1. function countingSort(arr){
2. let maxValue = Number.MIN_VALUE;
3. let minValue = Number.MAX_VALUE;
4. let offset = 0; // 位移，用于处理负数
5. const result = [];
6. // 取出数组的最大值, 最小值
7. arr.forEach(num => {
8. maxValue = num > maxValue ? num : maxValue;
9. minValue = num > minValue ? minValue : num;
10. });
11. if(minValue < 0){
12. offset = -minValue;
13. }
14. const bucket = new Array(maxValue+offset+1).fill(0); // 初始化连续的格子
15. // 将数组中的每个数字，根据值放入对应的下标中，
16. // `bucket[num] == n`格子的意义：存在n个数字，值为num
17. arr.forEach(num => {
18. bucket[num+offset]++;
19. });
20. // 读取格子中的数
21. bucket.forEach((store, index) => {
22. while(store--){
23. result.push(index - offset);
24. }
25. });
26. return result;
27.}
桶排序
概要
桶排序是计数排序的优化版，原理都是一样的：分治法+空间换时间。
将数组进行分组，减少排序的数量，再对子数组进行排序，最后合并即可得到结果。
效果图
解法
对桶内数字的排序，本文采用的是桶排序递归。其实它的本质是退化到计数排序。
1. function bucketSort(arr, bucketSize = 10){
2. // bucketSize 每个桶可以存放的数字区间(0, 9]
3. if(arr.length <= 1){
4. return arr;
5. }
6. let maxValue = arr[0];
7. let minValue = arr[0];
8. let result = [];
9. // 取出数组的最大值, 最小值
10. arr.forEach(num => {
11. maxValue = num > maxValue ? num : maxValue;
12. minValue = num > minValue ? minValue : num;
13. });
14. // 初始化桶的数量
15. const bucketCount = Math.floor((maxValue - minValue)/bucketSize) + 1; // 桶的数量
16. // 初始化桶的容器
17. // 注意这里的js语法，不能直接fill([])，因为生成的二维下标数组，是同一个地址
18. const buckets = new Array(bucketCount).fill(0).map(() => []);
19. // 将数字按照映射的规则，放入桶中
20. arr.forEach(num => {
21. const bucketIndex = Math.floor((num - minValue)/bucketSize);
22. buckets[bucketIndex].push(num);
23. });
24. // 遍历每个桶内存储的数字
25. buckets.forEach(store => {
26. // 桶内只有1个数字或者空桶，或者都是重复数字，则直接合并到结果中
27. if(store.length <= 1 || bucketSize == 1){
28. result = result.concat(store);
29. return;
30. }
31. // 递归，将桶内的数字，再进行一次划分到不同的桶中
32. const subSize = Math.floor(bucketSize/2); // 减少桶内的数字区间，但必须是最少为1
33. const tmp = bucketSort(store, subSize <= 1 ? 1: subSize);
34. result = result.concat(tmp);
35. });
36. return result;
}
基数排序
概述
基数排序，一般是从右到左，对进制位上的数字进行比较，存入[0, 9]的10个桶中，进行排序。
从低位开始比较，逐位进行比较，让每个进制位（个、十、百、千、万）上的数字，都能放入对应的桶中，形成局部有序。
为什么10个桶？
因为十进制数，是由0-9数字组成，对应的进制位上的数字，都会落在这个区间内，所以是10个桶。
基数排序有两种方式：
MSD 从高位开始进行排序
LSD 从低位开始进行排序
效果图
解法
当前解法，只适用正整数的场景。
负数场景，需要加上偏移量解决。可参考 计数排序 的解法。
1. function radixSort(arr){
2. let maxNum = arr[0];
3. // 求出最大的数字，用于确定最大进制位
4. arr.forEach(num => {
5. if(num > maxNum){
6. maxNum = num;
7. }
8. });
9. // 获取最大数字有几位
10. let maxDigitNum = 0;
11. while(maxNum > 0){
12. maxNum = Math.floor(maxNum / 10);
13. maxDigitNum++;
14. }
15. // 对每个进制位上的数进行排序
16. for(let i = 0; i < maxDigitNum; i++){
17. let buckets = new Array(10).fill(0).map(() => []); // 初始化10个桶
18. for(let k = 0; k < arr.length; k++){
19. const bucketIndex = getDigitNum(arr[k], i); // 获取当前进制位上的数字
20. buckets[bucketIndex].push(arr[k]); // 排序的数字放入对应桶中
21. }
22. // 所有数字放入桶中后，现从0-9的顺序将桶中的数字取出
23. const res = [];
24. buckets.forEach(store => {
25. store.forEach(num => {
26. res.push(num); // 注意这里，先存入桶中的数字，先取出，这样才能保持局部有序
27. })
28. });
29. arr = res;
30. }
31. return arr;
32. /**
33. 求出数字每个进制位上的数字，只支持正整数
34. @param num 整数
35. @param digit 位数，从0开始
36. */
37. function getDigitNum(num, digit){
38. return Math.floor(num / Math.pow(10, digit) % 10)
39. }
40.}
算法复杂度
该文章在 2023/6/29 18:29:14 编辑过
400 186 1886
