算法分类
- 比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
- 非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
算法复杂度
相关概念
- 稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面。
- 不稳定：如果a原本在b的前面，而a=b，排序之后 a 可能会出现在 b 的后面。
- 时间复杂度：对排序数据的总的操作次数。反映当n变化时，操作次数呈现什么规律。
- 空间复杂度：是指算法在计算机
比较类排序
冒泡排序
冒泡排序是比较基础的排序算法之一，其思想是相邻的元素两两比较，较大的数冒起来，较小的数下沉，这样一趟比较下来，最大值就会排列在一端。整个过程如同气泡冒起，因此被称作冒泡排序。
使用场景: 冒泡排序适用于数据量很小的排序场景，因为冒泡的实现方式较为简单。
算法描述:
- 比较相邻的元素。如果第一个比第二个大，就交换它们两个
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数
- 针对所有的元素重复以上的步骤，除了最后一个
- 重复步骤1~3，直到排序完成
动画演示
代码实现
let bubblearr = [3, 2, 4, 9, 1, 5, 7, 6, 8];
function bubbleSort(arr) {
let i = arr.length, j;
let maxnum;
while (i > 0) {
for (j = 0; j < i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 换了新方式
// maxnum = arr[j];
// arr[j] = arr[j + 1];
// arr[j + 1] = maxnum;
//解构方式替换
[arr[j + 1], arr[j]] = [arr[j], arr[j + 1]]
}
}
i--;
}
return arr;
}
console.log(bubbleSort(bubblearr), '冒泡排序')
选择排序
选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，继续放在起始位置知道未排序元素个数为0。
使用场景: 待排序序列中，元素个数较少时。
算法描述: n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：
- 初始状态：无序区为R[1…n]，有序区为空
- 第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1…i-1]和R(i…n）。该趟排序从当前无序区中-选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1…i]和R[i+1…n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区
- n-1趟结束，数组有序化了
动画演示
代码实现
let selectarr = [3, 2, 4, 9, 1, 5, 7, 6, 8];
function selectSort(arr) {
let minnum;
for (let i = 0; i < arr.length; i++) {
minnum = i; // 拿到当前值 去和后面的值比对
for (let k = i; k < arr.length; k++) {
if (arr[minnum] > arr[k]) {
minnum = k;
}
}
if (minnum !== i) {// 最小值不是当前值 则互换
[arr[i], arr[minnum]] = [arr[minnum], arr[i]]
}
}
return arr
}
console.log(selectSort(selectarr), '选择排序')
插入排序
插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
使用场景: 待排序序列的元素个数不多(<=50)，且元素基本有序。
算法描述: 插入排序的步骤如下：每次从无序部分中取出一个元素，与有序部分中的元素从后向前依次进行比较，并找到合适的位置，将该元素插到有序组当中。具体算法描述如下：
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
动画演示
代码实现
let insertionarr = [3, 2, 4, 9, 1, 5, 7, 6, 8];
function insertionSort(array) {
if (Object.prototype.toString.call(array).slice(8, -1) === 'Array') {
console.time('插入排序耗时：');
for (let i = 1; i < array.length; i++) {
let key = array[i];
let j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j--;
}
array[j + 1] = key;
}
console.timeEnd('插入排序耗时：');
return array;
} else {
return 'array is not an Array!';
}
}
console.log(insertionSort(insertionarr), '插入排序')
快速排序
快速排序的基本思想：每趟排序时选出一个基准值，然后将所有元素与该基准值比较，并按大小分成左右两堆，然后递归执行该过程，直到所有元素都完成排序。
使用场景: 待排序序列元素较多，并且元素较无序。
算法描述: 快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
- 从数列中挑出一个元素，称为 “基准”（pivot）
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序
动画演示
代码实现
let celerityarr = [3, 2, 4, 9, 1, 5, 7, 6, 8];
function celeritySort(arr) {
if (arr.length <= 1) {
return arr
}
let Snum = Math.floor(arr.length / 2);
let sZnum = arr.splice(Snum, 1)[0];//中间数
let left = [];//左部
let right = [];//右部
for (let i = 0; i < arr.length; i++) {
if (sZnum < arr[i]) {// 可以改变排序递增 递减
right.push(arr[i])
} else {
left.push(arr[i])
}
}
//concat 合并数组 左 加 中间数 加 右
return celeritySort(left).concat([sZnum], celeritySort(right))
}
console.log(celeritySort(celerityarr), '快速排序')
希尔排序
1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
使用场景: 待排序序列元素较少时。
算法描述:
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
- 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1
- 按增量序列个数k，对序列进行k 趟排序
- 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度
动画演示
代码实现
let shellarr = [3, 2, 4, 9, 1, 5, 7, 6, 8];
function shellSort(arr) {
//逐步降低步长直至为1为止
for (let i = Math.floor(arr.length / 2); i > 0; i = Math.floor(i / 2)) {
//根据步长，将数组进行分组，并使用插入排序法进行交换排序
//从增量大小的那组数据进行插入排序
for (let atom = i; atom < arr.length; atom++) {
//atom-i 表示和该元素同组的隔壁相邻的元素，对于同一组的元素，进行插入排序
if (arr[atom - i] > arr[atom]) {//判断大小
[arr[atom - i], arr[atom]] = [arr[atom], arr[atom - i]]
}
}
}
return arr
}
console.log(shellSort(shellarr), '希尔排序')
归并排序
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。
使用场景: 数据量大，并且对稳定性有要求的情况。代价是需要额外的内存空间。
算法描述:
- 把长度为n的输入序列分成两个长度为n/2的子序列
- 对这两个子序列分别采用归并排序
- 将两个排序好的子序列合并成一个最终的排序序列
动画演示
代码实现
let mergearr = [3, 2, 4, 9, 1, 5, 7, 6, 8];
function mergeSort(arr) {
if (arr.length < 2) {
return arr
}
let middle = Math.floor(arr.length / 2)
//拆分成两个子数组
let left = arr.slice(0, middle)
let right = arr.slice(middle)
//递归拆分
let mergeSortLeft = mergeSort(left)
let mergeSortRight = mergeSort(right)
//合并 比较
return merge(mergeSortLeft, mergeSortRight);
}
function merge(left, right) {
// 比较之后push到新数组中
const result = [];
while (left.length && right.length) {
// 注意: 判断的条件是小于或等于，如果只是小于，那么排序将不稳定.
//每次都要删除left或者right的第一个元素，将其加入result中
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;
};
console.log(mergeSort(mergearr), '归并排序')
堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
算法描述:
- 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆，此堆为初始的无序区
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]<=R[n]
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成
动画演示
代码实现
let heaparr = [3, 2, 4, 9, 1, 5, 7, 6, 8];
let len; // 因为声明的多个函数都需要数据长度，所以把len设置成为全局变量
function buildMaxHeap(arr) { // 建立大顶堆
len = arr.length;
for (let i = Math.floor(len / 2); i >= 0; i--) {
heapify(arr, i);
}
}
function heapify(arr, i) { // 堆调整
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) {// 每次最大值脱离堆 堆调整上下层关系
[arr[i], arr[largest]] = [arr[largest], arr[i]];
heapify(arr, largest);
}
}
function heapSort(arr) {
buildMaxHeap(arr); // 建立大顶堆
for (let i = arr.length - 1; i >= 0; i--) {
[arr[i], arr[0]] = [arr[0], arr[i]]
len--;
heapify(arr, 0);// 找到最大的然后放到最后 len--
}
return arr;
}
console.log(heapSort(heaparr), '堆排序')
非比较类排序
计数排序
计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
算法描述:
- 找出待排序的数组中最大和最小的元素
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
动画演示
代码实现
let countingarr = [3, 2, 4, 9, 1, 5, 7, 6, 8, 1, 8, 1];
function countingSort(arr, maxValue) {
let bucket = new Array(maxValue + 1),
sortedIndex = 0;
for (let i = 0; i < arr.length; i++) {// 计数
if (!bucket[arr[i]]) bucket[arr[i]] = 0;// 没有设置初始值
bucket[arr[i]]++;// 有 自增
}
for (let j = 0; j <= maxValue; j++) {
while (bucket[j] > 0) {// 重新书写arr 排序
arr[sortedIndex++] = j;
bucket[j]--;
}
}
return arr;
}
console.log(countingSort(countingarr, 9), '计数排序')// 传数组 和 数组中最大值
桶排序
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理：假设输入数据服从均匀分布，将数据分到有限数量的桶里，每个桶再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排）。
算法描述:
- 设置一个定量的数组当作空桶
- 遍历输入数据，并且把数据一个一个放到对应的桶里去
- 对每个不是空的桶进行排序
- 从不是空的桶里把排好序的数据拼接起来。
动画演示
代码实现
let bucketarr = [3, 2, 4, 9, 1, 5, 7, 6, 8];
function bucketSort(arr, bucketSize) {
if (arr.length === 0) {
return arr;
}
let i, minValue = arr[0], maxValue = arr[0];
for (i = 1; i < arr.length; i++) {// 循环找到最小值和最大值
if (arr[i] < minValue) minValue = arr[i]; // 输入数据的最小值
else if (arr[i] > maxValue) maxValue = arr[i]; // 输入数据的最大值
}
// 桶的初始化
let DEFAULT_BUCKET_SIZE = 5; // 设置桶的默认数量为5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
let bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1;
let buckets = new Array(bucketCount);
for (i = 0; i < buckets.length; i++) buckets[i] = [];// buckets编程二维数组
// 利用映射函数将数据分配到各个桶中
for (i = 0; i < arr.length; i++) {// 把数组中的值放入创建的桶中
buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);
}
arr.length = 0;// 清空数组
for (i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]); // 对每个桶进行排序，这里使用了插入排序
for (let j = 0; j < buckets[i].length; j++) {
arr.push(buckets[i][j]);// 依次将排序好的加入数组
}
}
return arr;
}
console.log(bucketSort(bucketarr), '桶排序')
基数排序
基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。有时候有些属性是有优先级顺序的，先按低优先级排序，再按高优先级排序。最后的次序就是高优先级高的在前，高优先级相同的低优先级高的在前。
算法描述:
- 取得数组中的最大数，并取得位数
- arr为原始数组，从最低位开始取每个位组成radix数组
- 对radix进行计数排序（利用计数排序适用于小范围数的特点）
动画演示
代码实现
let radixarr = [3, 2, 1, 5, 7, 6, 8, 21, 42, 31, 83, 62, 58, 51];
function radixSort(arr, maxDigit) {
let counter = [];
let mod = 10;
let dev = 1;
for (let i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
for (let j = 0; j < arr.length; j++) {
let bucket = parseInt((arr[j] % mod) / dev);
if (counter[bucket] == null) {// 将其转为二维数组
counter[bucket] = [];
}
counter[bucket].push(arr[j]);// push到相应的基数中
}
let pos = 0;
for (let j = 0; j < counter.length; j++) {
let value = null;
if (counter[j] != null) {
while ((value = counter[j].shift()) != null) {
arr[pos++] = value;// 重构数组
}
}
}
}
return arr;
}
console.log(radixSort(radixarr, 2), '基数排序')// 传递数组 和 最大位数 83是两位数所以是 2
可能代码不是最好的, 因为是靠我的理解和参考书写的记录.
参考:十大经典排序算法