JavaScript-排序算法
丰誉
冒泡排序
思路:
基于比较,交换的算法,双重循环,当前元素与下一个元素比较,若比小一个元素大,则交换两个元素的位置.
function bubbleSort(arr) {
for (let i = arr.length - 1; i > 0; i--) {//外层循环从后往前遍历,控制j的边界值
for (let j = 0; j < i; j++) {// 内存循环控制需要比较的次数
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
}
}
}
return arr;
}
// 交换位置
function swap(arr, a, b) {
let temp = arr[b];
arr[b] = arr[a];
arr[a] = temp;
}
function test(sortFn) {
let arr = Array.from({ length: 10 }).map(() =>
Math.floor(Math.random(0) * 100)
);
console.log("排序前::>>", arr);
const res = sortFn(arr);
console.log("排序后::>>", res);
}
test(bubbleSort);
选择排序
思路 :
基于比较的排序算法,从未排序的数组中循环比较求出最小数,放在已排序数组的尾部,依次循环比较选择.也是双重循环,外层循环控制未比较的数组,内层循环控制比较大小.
function selectionSort(arr) {
for (let i = 0; i < arr.length; i++) {
let minIndex = i; // 当前最小值索引
for (let j = i; j < arr.length - 1; j++) {
if (arr[minIndex] > arr[j + 1]) {
// 最小值大于后一位,改变最小值
minIndex = j + 1;
}
}
// 一轮循环完,找到最小值索引,与当前比较的位置i交换
swap(arr, i, minIndex);
}
return arr;
}
function swap(arr, a, b) {
let temp = arr[b];
arr[b] = arr[a];
arr[a] = temp;
}
function test(sortFn) {
let arr = Array.from({ length: 10 }).map(() =>
Math.floor(Math.random(0) * 100)
);
console.log("排序前::>>", arr);
const res = sortFn(arr);
console.log("排序后::>>", res);
}
test(selectionSort);
插入排序
思路:
基于比较的双重循环,将数组分为两部分,一部分是已排序,一部分未排序,遍历未排序的数组,与已排序的数组从后往前比较,要排序元素比当前元素小,则将当前元素位置后移,直到找到要插入的位置.
function insertionSort(arr) {
for (let i = 1; i < arr.length; i++) {
// 从第2个开始比较起
let j = i,
cur = arr[i];
while (j > 0 && cur < arr[j - 1]) {
// 当前元素比要cur要大,则后移
arr[j] = arr[j - 1]; // 前一个元素后移
--j;
}
arr[j] = cur; // 找到位置插入
}
return arr;
}
function swap(arr, a, b) {
let temp = arr[b];
arr[b] = arr[a];
arr[a] = temp;
}
function test(sortFn) {
let arr = Array.from({ length: 10 }).map(() =>
Math.floor(Math.random(0) * 100)
);
console.log("排序前::>>", arr);
const res = sortFn(arr);
console.log("排序后::>>", res);
}
test(insertionSort);
希尔排序
思路:
直接插入排序的改进版,按照不同的间隔(如根据数组长度一直除以2生成的间隔数组[10,5,2,1]),来进行插入排序,
function shellSort(arr) {
// 产生间隔
function genGaps(arr) {
let gaps = [];
let len = arr.length;
while ((len = Math.floor(len / 2)) >= 1) {
gaps.push(len);
}
return gaps;
}
let gaps = genGaps(arr);
for (let g = 0; g < gaps.length; g++) {
// 依次按照不同间隔来插入排序
for (let i = gaps[g]; i < arr.length; i++) {
let cur = arr[i],
j;
for (j = i - gaps[g]; j >= 0; j -= gaps[g]) {
//以间隔gaps[g]来分组进行插入排序,索引的跨度也是gaps[g]
if (cur < arr[j]) {
arr[j + gaps[g]] = arr[j]; // 后移
} else {
break;
}
}
arr[j + gaps[g]] = cur; // 插入
}
}
return arr;
}
function swap(arr, a, b) {
let temp = arr[b];
arr[b] = arr[a];
arr[a] = temp;
}
function test(sortFn) {
let arr = Array.from({ length: 10 }).map(() =>
Math.floor(Math.random(0) * 100)
);
console.log("排序前::>>", arr);
const res = sortFn(arr);
console.log("排序后::>>", res);
}
test(shellSort);
归并排序
思路:
- 1.把长度为n的输入序列分成两个长度为n/2的子序列；
- 2.对这两个子序列分别采用归并排序；
- 3.将两个排序好的子序列合并成一个最终的排序序列。
function mergeSort(arr) {
if (!arr || arr.length < 2) {
return arr || []; //递归退出条件
}
// 左右分区
let middle = Math.floor(arr.length / 2);
let left = arr.slice(0, middle);
let right = arr.slice(middle);
// 合并已排序数组
return mergeArray(mergeSort(left), mergeSort(right));
}
// 排序两个数组,合成并返回
function mergeArray(arr1, arr2) {
let result = [];
while (arr1.length && arr2.length) {
if (arr1[0] <= arr2[0]) {
result.push(arr1.shift());
} else {
result.push(arr2.shift());
}
}
while (arr1.length) {
result.push(arr1.shift());
}
while (arr2.length) {
result.push(arr2.shift());
}
return result;
}
function test(sortFn) {
const arr = Array.from({ length: 20 })
.fill(0)
.map(() => Math.floor(Math.random() * 1000));
console.log("排序前::>>");
console.log(arr);
const res = sortFn(arr);
console.log("排序后::>>");
console.log(res);
}
test(mergeSort);
快速排序
思路
取一个基准pivot,将排序数组分成小于基准值的数组和大于等于基准值的数组,然后依次递归剩余的数组,最后完成排序
function quickSort(arr) {
if (!arr || arr.length < 2) {
return arr;
}
let pivot = arr[0];//基准值
let lessers = [];
let greaters = [];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < pivot) {
lessers.push(arr[i]);// 小数组
} else {
greaters.push(arr[i]);//大数组
}
}
// 递归 concat
return quickSort(lessers).concat(pivot, quickSort(greaters));
}
function test(sortFn) {
let arr = Array.from({ length: 10 }).map(() =>
Math.floor(Math.random(0) * 100)
);
console.log("排序前::>>", arr);
const res = sortFn(arr);
console.log("排序后::>>", res);
}
test(quickSort);
堆排序
1. 什么是堆?
堆:是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
2. 大顶堆,小顶堆
大顶堆:每个节点的值都大于或等于其子节点的值,可用于升序排序.
小顶堆:每个节点的值都小于或等于其子节点的值,可用于降序排序.
3. 堆排序中第一个非叶子节点的索引是arr.length/2-1
可以用数组来表示堆,索引i(i从0开始)对应的节点如果有子节点,那么其子节点的索引分别是2i+1,2i+2
4. 堆排序思想
将无序序列构建成大顶堆buildMaxHeap,将堆顶与最后一个元素交换,然后调整剩余元素组成的堆成大顶堆,然后再与最后一个元素交换,依次循环完成排序.关键代码在于从后往前依次根据大小调整当前节点与子节点的位置,就是以下代码的heapify方法
// 构建大顶堆
function buildMaxHeap(arr, len) {
// 从最后一个非叶子节点开始向前遍历,调整节点性质,使之成为大顶堆
for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {
heapify(arr, i, len);
}
}
function swap(arr, i1, i2) {
let temp = arr[i1];
arr[i1] = arr[i2];
arr[i2] = temp;
}
/**
* 堆调整,成为大顶堆
* 关键代码
* @param {*} arr
* @param {*} index
* @param {*} len 堆的数组长度
*/
function heapify(arr, index, len) {
// 左右子节点索引
let left = 2 * index + 1;
let right = 2 * index + 2;
// 默认当前节点是最大值
let largestIndex = index;
if (left < len && arr[left] > arr[largestIndex]) {
// 左节点值更大,更新最大值索引
largestIndex = left;
}
if (right < len && arr[right] > arr[largestIndex]) {
// 右节点值更大,更新最大值索引
largestIndex = right;
}
if (largestIndex !== index) {
// 如果最大值不是当前非叶子节点,那么就把当前节点和最大值的子节点交换
swap(arr, index, largestIndex);
// 互换后,子节点的值变了,如果该子节点也有自己的子节点,仍需要再次调整
heapify(arr, largestIndex, len);
}
}
// 堆排序
function heapSort(arr) {
if (!arr || arr.length == 0) {
return;
}
let len = arr.length;
buildMaxHeap(arr, len);
// 从后往前遍历,交换堆顶和当前堆数组末尾元素,重置大顶堆
for (let i = len - 1; i > 0; i--) {
swap(arr, 0, i);
len--;
heapify(arr, 0, len);
}
}
const arr = [5, 6, 2, 9, 3, 1, 8, 7, 4, 0];
heapSort(arr);
console.log(arr);
//[
// 0, 1, 2, 3, 4,
// 5, 6, 7, 8, 9
//]
计数排序
思路
用一个计数数组countArr,下标对应待排序数组中的元素,遍历原数组,每出现一次,则计数加1.然后新建一个输出数组output,依次遍历计数数组,将计数数组下标对应的原数组元素存进数组output,计数多少个,就存多少个,最后完成排序.对于一定整数范围k内的排序,计数排序要比基于比较的排序要快.
步骤
- 计算待排序数组中的最大值max,最小值min,
- 新建一个长度为k=max-min+1的数组countArr,其下标i+min就是排序数组中的值
- 遍历待排序数组,每一个元素对应的countArr的下标的值就加1,计数
- 新建一个输出数组output,遍历countArr,依次按照下标的计数次数往输出数组里添加i+min
代码
function countSort(arr) {
let len = arr.length,
max = (min = arr[0]);
// 1. 求最大值和最小值max,min
for (let i = 0; i < len; i++) {
max = arr[i] > max ? arr[i] : max;
min = arr[i] < min ? arr[i] : min;
}
// 2. 新建长度为max-min+1的计数数组countArr,数组下标对应原数组里元素,计数
const countArr = new Array(max - min + 1);
for (let i = 0; i < len; i++) {
countArr[arr[i] - min] = (countArr[arr[i] - min] || 0) + 1;
}
// 3. 新建输出数组output,循环遍历countArr和对应元素的次数,赋值给output数组并返回
const output = [];
let begin = 0;
for (let i = 0; i < countArr.length; i++) {
for (let j = 0; j < countArr[i]; j++) {
output[begin++] = min + i;
}
}
return output;
}
let arr = [];
for (let i = 0; i < 50; i++) {
arr.push(Math.floor(Math.random() * 101));
}
const ret = countSort(arr);
console.log(ret);//[0,1,2,3,4,5,6,7,8,9]
桶排序
1. 桶排序的思想
桶排序是计数排序的升级版,与计数排序不同的是:计数排序是以数组中每个值作为下标来计数,而桶是将每个数组元素放进容纳不同范围的"桶"里,然后在桶里进行排序,最后依次输出.这里最终要的就是确定桶的数量和桶的长度
2. 代码
// 插入排序
function insertionSort(arr) {
if (!arr || arr.length == 0) return;
for (let i = 1; i < arr.length; i++) {
let cur = arr[i],
j;
for (j = i - 1; j >= 0; j--) {
if (cur < arr[j]) {
//从后往前比较,往后移
arr[j + 1] = arr[j];
} else {
break;
}
}
// 插入
arr[j + 1] = cur;
}
}
// 桶排序
function bucketSort(arr) {
// 求最大值和最小值
let max = arr[0];
let min = arr[0];
for (let i = 0; i < arr.length; i++) {
max = arr[i] > max ? arr[i] : max;
min = arr[i] < min ? arr[i] : min;
}
let bucketCount = 5; // 桶的数量
let bucketSize = Math.floor((max - min) / 5 + 1); //桶的长度
// 放进桶
let buckets = [];
for (let i = 0; i < bucketCount; i++) {
buckets[i] = [];
}
for (let i = 0; i < arr.length; i++) {
// 根据映射选择桶Math.floor((arr[i] - min) / bucketSize)
buckets[Math.floor((arr[i] - min) / bucketSize)].push(arr[i]);
}
// 桶内使用插入排序,依次输出
let output = [];
for (let i = 0; i < buckets.length; i++) {
insertionSort(buckets[i]);
for (let j = 0; j < buckets[i].length; j++) {
output.push(buckets[i][j]);
}
}
return output;
}
let arr = [];
Array.from({ length: 100 }).map((_) => {
arr.push(Math.floor(Math.random() * 101));
});
const ret = bucketSort(arr);
console.log(ret);
基数排序
// /**
// * 基数排序
// * 将整数按位数切割成不同的数字,然后按每个位数分别比较,从地位到高位
// * 根据键值的每个数字来分配桶
// * 步骤:
// * 1. 取得数组中的最大数,并取得数位
// * 2. 遍历不同的数位,遍历排序数组,取得数位,放入对应的桶
// * 3. 按顺序输出桶里的元素
// * @param {*} arr
// */
function radixSort(arr) {
let maxDigit = getMaxDigit(arr); //位数
function getMaxDigit(arr) {
let max = 0;
for (let i = 0; i < arr.length; i++) {
max = arr[i] > max ? arr[i] : max;
}
let mod = 10,
i = 1;
while (max % mod !== max) {
mod *= 10;
i++;
}
return i;
}
let mod = 10;
let div = 1;
let buckets = []; // 桶,存放不同基数的值
for (let i = 0; i < 10; i++) {
buckets[i] = [];
}
for (let i = 0; i < maxDigit; i++) {
let digit = 0;
for (let j = 0; j < arr.length; j++) {
digit = Math.floor((arr[j] % mod) / div); // 数位上的值,取余再除
// 存进对应数位的桶里
buckets[digit].push(arr[j]);
}
mod *= 10;
div *= 10;
// 依次取出,放回原数组
let index = 0;
for (let k = 0; k < buckets.length; k++) {
let value = null;
while ((value = buckets[k].shift())) {
arr[index++] = value;
}
}
}
return arr;
}
let arr = Array.from({ length: 20 }).map(() => Math.floor(Math.random() * 300));
// let arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48];
const res = radixSort(arr);
console.log(res);
[
23, 38, 46, 60, 64, 79, 86, 96, 107, 112, 123, 129, 144, 170, 183, 232, 265,
277, 279, 287,
];
类似资料：