冒泡排序 排序的效果图
解法
当前解法为升序
冒泡排序的特点,是一个个数进行处理。第i个数,需要与后续的len-i-1
个数进行逐个比较。
为什么是 `len-i-1`个数?
因为数组末尾的i个数,已经是排好序的,确认位置不变的了。
为什么确认位置不变,因为它们固定下来之前,已经和前面的数字都一一比较过了。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 function bubbleSort (arr ){ const len = arr.length ; for (let i = 0 ; i < len - 1 ; i++){ for (let j = 0 ; j < len - i - 1 ; j++){ if (arr[j] > arr[j+1 ]){ const tmp = arr[j+1 ]; arr[j+1 ] = arr[j]; arr[j] = tmp; } } } return arr; }
快速排序 概要 快速排序,使用的是分治法 的思想。 通过选定一个数字作为比较值,将要排序其他数字,分为 >比较值 和 <比较值 ,两个部分。并不断重复这个步骤,直到只剩要排序的数字只有本身,则排序完成。
效果图
解法 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 function quickSort (arr ){ sort (arr, 0 , arr.length - 1 ); return arr; function sort (arr, low, high ){ if (low >= high){ return ; } let i = low; let j = high; const x = arr[i]; while (i < j){ while (arr[j] >= x && i < j){ j--; } if (i < j){ arr[i] = arr[j] i++; } while (arr[i] <= x && i < j){ i++; } if (i < j){ arr[j] = arr[i] j--; } } arr[i] = x; sort (arr, low, i - 1 ); sort (arr, i+1 , high); } }
希尔排序 概要 希尔排序是一种插入排序 的算法,它是对简单的插入排序进行改进后,更高效的版本。由希尔(Donald Shell)于1959年提出。 特点是利用增量 ,将数组分成一组组子序列,然后对子序列进行插入排序。 由于增量是从大到小,逐次递减,所以也称为缩小增量排序 。
效果图
解法
注意点 插入排序时,并不是一个分组内的数字一次性用插入排序完成,而是每个分组交叉进行。
执行插入时,使用交换法 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 ){ for (let gap = Math .floor (arr.length /2 ); gap > 0 ; gap = Math .floor (gap/2 )){ for (let i = gap; i < arr.length ; i++){ let j = i; while (j - gap >= 0 && arr[j] < arr[j - gap]){ swap (j, j-gap); j = j - gap; } } } return arr; function swap (a, b ){ const tmp = arr[a]; arr[a] = arr[b]; arr[b] = tmp; } }
执行插入时,使用移动法 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 function shellSort (arr ){ for (let gap = Math .floor (arr.length /2 ); gap > 0 ; gap = Math .floor (gap/2 )){ for (let i = gap; i < arr.length ; i++){ let j = i; const x = arr[j]; while (j - gap >= 0 && x < arr[j-gap]){ arr[j] = arr[j - gap]; j = j - gap; } arr[j] = x; } } return arr; }
选择排序 排序的效果图
解法
当前解法为升序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 function selectionSort (arr ){ const len = arr.length ; for (let i = 0 ; i < len-1 ; i++){ let minIndex = i; for (let j = i+1 ; j < len; j++){ if (arr[j] < arr[minIndex]){ minIndex = j; } } const tmp = arr[i]; arr[i] = arr[minIndex]; arr[minIndex] = tmp; } return arr; }
归并排序 概要 归并排序,利用分治 思想,将大的数组,分解为小数组,直至单个元素。然后,使用选择排序 的方式,对分拆的小数组,进行回溯,并有序合并,直至合并为一个大的数组。
效果图
小数组合并的过程
解法 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 54 function mergeSort (arr ){ return sort (arr, 0 , arr.length - 1 ); function sort (arr, left, right ){ if (left < right){ const mid = Math .floor ((left+right) / 2 ); const leftArr = sort (arr, left, mid); const rightArr = sort (arr, mid+1 , right); return merge (leftArr, rightArr) } return left >= 0 ? [arr[left]] : []; } function merge (leftArr, rightArr ){ let left = 0 ; let right = 0 ; const tmp = []; while (left < leftArr.length && right < rightArr.length ){ if (leftArr[left] <= rightArr[right]){ tmp.push (leftArr[left++]); }else { tmp.push (rightArr[right++]); } } if (left < leftArr.length ){ while (left < leftArr.length ){ tmp.push (leftArr[left++]); } } if (right < rightArr.length ){ while (right < rightArr.length ){ tmp.push (rightArr[right++]); } } return tmp; } }
插入排序 排序的效果图
解法
当前解法为升序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 function insertionSort (arr ){ const len = arr.length ; for (let i = 1 ; i < len; i++){ let preIndex = i - 1 ; let current = arr[i]; while (preIndex >= 0 && arr[preIndex] > current){ arr[preIndex+1 ] = arr[preIndex]; preIndex--; } arr[preIndex+1 ] = current; } return arr; }
堆排序 概要
堆的表示形式
逻辑结构的表示如下:
在物理数据层的表示如下:
堆排序,是选择排序 的优化版本,利用数据结构——树,对数据进行管理。
以大顶堆为例:
通过构建大顶堆
将堆顶的最大数拿出,与堆底的叶子节点进行交换
接着,树剪掉最大数的叶子
再对堆进行调整,重新变成大顶堆
返回步骤2,以此循环,直至取出所有数
效果图
在实现代码时,构建大顶堆时,先保证左右子树的有序,再逐步扩大到整棵树。
构建大顶堆 从第一个非叶子节点开始,调整它所在的子树
调整下标1节点的子树后,向上继续调整它的父节点(下标0)所在的子树
最后,完成整个树的调整,构建好大顶堆。
逐个抽出堆顶最大值 堆顶数字与最末尾的叶子数字交换,抽出堆顶数字9。
此时,数字9位置固定下来,树剪掉9所在的叶子。然后,重新构建大顶堆。
大顶堆构建好后,继续抽出堆顶数字8,然后再次重新构建大顶堆。
最后,所有节点抽出完成,代表排序已完成。
解法
以大顶堆为例,对数组进行升序排序
注意点 树的最后一个非叶子节点:(arr.length / 2) - 1
非叶子节点i
的左叶子节点: i*2+1
非叶子节点i
的右叶子节点: i*2+2
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 54 function heapSort (arr ){ for (let i = Math .floor (arr.length /2 ) - 1 ; i >= 0 ; i--){ buildHeap (arr, i, arr.length ); } for (let j = arr.length -1 ; j > 0 ; j--){ swap (arr, 0 , j); buildHeap (arr, 0 , j); } return arr; function buildHeap (arr, i, length ){ let tmp = arr[i]; for (let k = 2 *i+1 ; k < length; k = 2 *k+1 ){ if (k+1 < length && arr[k+1 ] > arr[k]){ k++; } if (arr[k] > tmp){ arr[i] = arr[k]; i = k; }else { break ; } } arr[i] = tmp; } function swap (arr, i, j ){ const tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } }
计数排序 概要 计数排序的要点,是开辟一块连续格子组成的空间,给数据进行存储。 将数组中的数字,依次读取,存入其值对应的下标中。 储存完成后,再按照空间的顺序,依次读取每个格子的数据,输出即可。
所以,计数排序要求排序的数据,必须是有范围的整数 。
效果图
解法 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 function countingSort (arr ){ let maxValue = Number .MIN_VALUE ; let minValue = Number .MAX_VALUE ; let offset = 0 ; const result = []; arr.forEach (num => { maxValue = num > maxValue ? num : maxValue; minValue = num > minValue ? minValue : num; }); if (minValue < 0 ){ offset = -minValue; } const bucket = new Array (maxValue+offset+1 ).fill (0 ); arr.forEach (num => { bucket[num+offset]++; }); bucket.forEach ((store, index ) => { while (store--){ result.push (index - offset); } }); return result; }
桶排序 概要 桶排序是计数排序的优化版,原理都是一样的:分治法+空间换时间。 将数组进行分组,减少排序的数量,再对子数组进行排序,最后合并即可得到结果。
效果图
解法
对桶内数字的排序,本文采用的是桶排序 递归。其实它的本质是退化到计数排序 。
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 function bucketSort (arr, bucketSize = 10 ){ if (arr.length <= 1 ){ return arr; } let maxValue = arr[0 ]; let minValue = arr[0 ]; let result = []; arr.forEach (num => { maxValue = num > maxValue ? num : maxValue; minValue = num > minValue ? minValue : num; }); const bucketCount = Math .floor ((maxValue - minValue)/bucketSize) + 1 ; const buckets = new Array (bucketCount).fill (0 ).map (() => []); arr.forEach (num => { const bucketIndex = Math .floor ((num - minValue)/bucketSize); buckets[bucketIndex].push (num); }); buckets.forEach (store => { if (store.length <= 1 || bucketSize == 1 ){ result = result.concat (store); return ; } const subSize = Math .floor (bucketSize/2 ); const tmp = bucketSort (store, subSize <= 1 ? 1 : subSize); result = result.concat (tmp); }); return result; }
基数排序 概述 基数排序,一般是从右到左,对进制位上的数字进行比较,存入[0, 9]的10个桶中,进行排序。 从低位开始比较,逐位进行比较,让每个进制位(个、十、百、千、万)上的数字,都能放入对应的桶中,形成局部有序。
为什么10个桶?
因为十进制数,是由0-9数字组成,对应的进制位上的数字,都会落在这个区间内,所以是10个桶。
基数排序有两种方式:
MSD 从高位开始进行排序
LSD 从低位开始进行排序
效果图
解法
当前解法,只适用正整数的场景。 负数场景,需要加上偏移量解决。可参考 计数排序 的解法。
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 function radixSort (arr ){ let maxNum = arr[0 ]; arr.forEach (num => { if (num > maxNum){ maxNum = num; } }); let maxDigitNum = 0 ; while (maxNum > 0 ){ maxNum = Math .floor (maxNum / 10 ); maxDigitNum++; } for (let i = 0 ; i < maxDigitNum; i++){ let buckets = new Array (10 ).fill (0 ).map (() => []); for (let k = 0 ; k < arr.length ; k++){ const bucketIndex = getDigitNum (arr[k], i); buckets[bucketIndex].push (arr[k]); } const res = []; buckets.forEach (store => { store.forEach (num => { res.push (num); }) }); arr = res; } return arr; function getDigitNum (num, digit ){ return Math .floor (num / Math .pow (10 , digit) % 10 ) } }
算法复杂度
参考