JavaScript 之排序集锦
1⃣️ 快速排序
快速排序
单独开辟两个存储空间 left 和 right 来存储每次递归比 target 小和大的序列,每次递归直接返回 left 、 target 、 right 拼接后的数组.
浪费大量存储空间,写法简单.
function quickSort(array) {
if (array.length < 2) {
return array;
}
const target = array[0];
const left = [];
const right = [];
for (let i = 0; i < array.length; i++) {
if (array[i] < target) {
left.push(array[i]);
} else {
right.push(array[i]);
}
}
return;
quickSort(left).concat([target], quickSort(right));
}
2⃣️ 归并排序
利用归并的思想实现的排序方法。
该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。（分治法将问题分成一些小的问题然后递归求解，而治的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)。
- 将已有序的子序列合并，得到完全有序的序列
- 即先使每个子序列有序，再使子序列段间有序
- 若将两个有序表合并成一个有序表，称为二路归并
归并排序
归并排序
分割数组时直接将数组分割为两个数组，合并时直接合并数组
function merge(front, end) {
const temp = [];
while (front.length && end.length) {
if (front[0] < end[0]) {
temp.push(front.shift());
} else {
temp.push(end.shift());
}
}
while (front.length) {
temp.push(front.shift());
}
while (end.length) {
temp.push(end.shift());
}
return temp;
}
function mergeSort(array) {
if (array.length < 2) {
return array;
}
const mid = Math.floor(array.length / 2);
const front = array.slice(0, mid);
const end = array.slice(mid);
return merge(mergeSort(front), mergeSort(end));
}
3⃣️ 选择排序
选择排序
每次循环选取一个最小的数字放到前面的有序序列中.
function selectionSort(array) {
for (let i = 0; i < array.length - 1; i++) {
let minIndex = i;
for (let j = i + 1; j < array.length; j++) {
if (array[j] < array[minIndex]) {
minIndex = j;
}
}
[array[minIndex], array[i]] = [array[i], array[minIndex]];
}
return array;
}
4⃣️ 插入排序
将左侧序列看成一个有序序列，每次将一个数字插入该有序序列。
插入时，从有序序列最右侧开始比较，若比较的数较大，后移一位。
插入排序
function insertSort(array) {
for (let i = 1; i < array.length; i++) {
let target = i;
for (let j = i - 1; j >= 0; j--) {
if (array[target] < array[j]) {
[array[target], array[j]] = [array[j], array[target]];
target = j;
} else {
break;
}
}
}
return array;
}
5⃣️ 冒泡排序
冒泡排序
- 循环数组，比较当前元素和下一个元素，如果当前元素比下一个元素大，向上冒泡。
- 这样一次循环之后最后一个数就是本数组最大的数。
- 下一次循环继续上面的操作，不循环已经排序好的数。
- 优化：当一次循环没有发生冒泡，说明已经排序完成，停止循环。
function bubbleSort(array) {
for (let j = 0; j < array.length; j++) {
let complete = true;
for (let i = 0; i < array.length - j - 1; i++) {
// 比较相邻数
if (array[i] > array[i + 1]) {
[array[i], array[i + 1]] = [array[i + 1], array[i]];
complete = false;
}
}
// 没有冒泡结束循环
if (complete) {
break;
}
}
return array;
}
6⃣️ 堆排序
- 创建一个大顶堆，大顶堆的堆顶一定是最大的元素。
- 交换第一个元素和最后一个元素，让剩余的元素继续调整为大顶堆。
- 从后往前以此和第一个元素交换并重新构建，排序完成。
堆排序
堆排序
// 构建大顶堆, 从第一个非叶子节点开始, 进行下沉操作.
function createHeap(array) {
const len = array.length;
const start = parseInt(len / 2) - 1;
for (let i = start; i >= 0; i--) {
adjust(array, i, len);
}
}
// 将第target个元素进行下沉, 孩子节点有比他大的就下沉
function adjust(array, target, len) {
for (let i = 2 * target + 1; i < len; i = 2 * i + 1) {
// 找到孩子节点中最大的
if (i + 1 < len && array[i + 1] > array[i]) {
i = i + 1;
}
// 下沉
if (array[i] > array[target]) {
[array[i], array[target]] = [array[target], array[i]];
target = i;
} else {
break;
}
}
}
function heapSort(array) {
createHeap(array);
// 交换第一个和最后一个元素, 然后重新调整大顶堆
for (let i = array.length - 1; i > 0; i--) {
[array[i], array[0]] = [array[0], array[i]];
adjust(array, 0, i);
}
return array;
}
7⃣️ 希尔排序
希尔排序的核心在于间隔序列的设定.既可以提前设定好间隔序列,也可以动态的定义间隔序列.动态定义间隔序列的算法是《算法(第4版)》 的合著者 Robret Sedgewick 提出的.
- 先将整个待排序记录序列分割成若干个子序列
- 在序列内分别进行直接插入排序,待整个序列基本有序时,在对全体记录进行一次直接插入排序
希尔排序
希尔排序
function shellSort(array) {
let len = array.length;
let gap = parseInt(len / 2);
let i, j, temp, result;
// 复制数组
result = array.slice(0);
while (gap > 0) {
for (i = gap; i < len; i++) {
temp = result[i];
j = i - gap;
while (j >= 0 && temp < result[j]) {
result[j + gap] = result[j];
j = j - gap;
}
result[j + gap] = temp;
}
gap = parseInt(gap / 2);
}
return result;
}
8⃣️ 计数排序
- 找出待排序的数组中最大和最小的元素；
- 统计数组中每个值为 i 的元素出现的次数，存入数组 C 的第 i 项；
- 对所有的计数累加（从 C 中的第一个元素开始，每一项和前一项相加）
- 反向填充目标数组：将每个元素 i 放在新数组的第 C(i)项，每放一个元素就将 C(i)减去 1
计数排序
计数排序
function countingSort(array, maxValue) {
let bucket = new Array(maxValue + 1);
let sortIndex = 0;
let bucketLen = maxValue + 1;
for (let i = 0; i < array.length; i++) {
if (!bucket[array[i]]) {
bucket[array[i]] = 0;
}
bucket[array[i]]++;
}
for (let j = 0; j < bucketLen; j++) {
while (bucket[j] > 0) {
array[sortIndex++] = j;
bucket[j]--;
}
}
return array;
}
9⃣️ 桶排序
- 设置一个定量的数组当作空桶；
- 遍历输入数据，并且把数据一个一个放到对应的桶里去；
- 对每个不是空的桶进行排序；
- 从不是空的桶里把排好序的数据拼接起来。
桶排序
桶排序
function bucketSort(arr, bucketSize) {
if (arr.length === 0) {
return arr;
}
let minValue = arr[0];
let maxValue = arr[0];
for (let i = 1; i < arr.length; i++) {
if (arr[i] < minValue) {
minValue = arr[i]; //输入数据的最小值
} else if (arr[i] > maxValue) {
maxValue = arr[i]; //输入数据的最大值
}
} //桶的初始化
const DEFAULT_BUCKET_SIZE = 5; //设置桶的默认数量为5
bucketSize = bucketSize || DEFAULT_BUCKET_SIZE;
let bucketCount = Math.floor((maxValue - minValue) / 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] - minValue) / bucketSize)].push(arr[i]);
}
arr.length = 0;
for (let 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;
}
🔟 基数排序
- 该算法是稳定的排序法；
- 在所有的情况下，时间复杂度均为 O(nlog(p)k)，空间复杂度为 O(n*p)
（其中 K 为关键词位数，p 为数据字符数(即基数 radix)）； - 若 n 很大，p 固定或很小，此方法将很有效。
- 基数排序不需要进行元素间的比较，属于分配/分布排序；
- 根据起始方向可分为 最高位优先 MSD 和 最低位优先 LSD
基数排序
基数排序
function radixSort(arr, n, radix) {
if (!radix) {
//默认为十进制
radix = 10;
}
if (!n) {
//如果未指定关键词位数将自动使用首个元素的位数作为n
n = arr[0].toString().length;
}
var i,
j,
tmp,
num,
queues = [],
q = arr.slice();
for (i = 0; i < radix; i++) {
queues.push([]); //生成Q[0]~Q[radix-1]
}
for (i = 0; i < n; i++) {
//LSD低位起始
while (q.length > 0) {
tmp = q.shift();
num = Math.floor((tmp / Math.pow(radix, i)) % radix); //获取某位数值
//这里这个转换只能搞得动十进制= =其他就会有问题 因为不能直接用其他进制来进行运算 所以考虑使用字符串处理
queues[num].push(tmp);
}
for (j = 0; j < radix; j++) {
//重构q
while (queues[j].length > 0) {
q.push(queues[j].shift());
}
}
}
return q;
}
