外链论坛

 找回密码
 立即注册
搜索
查看: 27|回复: 2

十大排序算法(javascript)

[复制链接]

3054

主题

3万

回帖

9606万

积分

论坛元老

Rank: 8Rank: 8

积分
96065826
发表于 2024-10-10 04:22:26 | 显示全部楼层 |阅读模式

冒泡排序

经过相邻元素的比较和交换,使得每一趟循环都能找到未有序数组的最大值或最小值。

内循环: 运用相邻双指针 j , j + 1 从左至右遍历,依次比较相邻元素体积,若左元素大于右元素则将它们交换;遍历完成时,最大元素会被交换至数组最右边 。

外循环: 持续重复「内循环」,每轮将当前最大元素交换至 剩余未排序数组最右边 ,直至所有元素都被交换至正确位置时结束。

/**

* 冒泡

* 每一趟找出最大的,总共比较次数为arr.length-1次,每次的比较次数为arr.length-1-i次,依次递减

* @param {*} arr

* @returns array

*/

function bubbleSort(arr) {

/**

比较相邻的元素。倘若第1个比第二个大,就交换她们两个。

对每一对相邻元素作一样的工作,从起始第1对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

针对所有的元素重复以上的过程,除了最后一个。

连续每次对越来越少的元素重复上面的过程,直到任何一对数字需要比较。

相同元素的前后次序改变,因此冒泡排序是一种稳定排序算法。

原始数组: [ 99, 88, 66, 101, 90, 45 ]

第1次循环 [ 88, 66, 99, 90, 45, 101 ]

第2次循环 [ 66, 88, 90, 45, 99, 101 ]

第3次循环 [ 66, 88, 45, 90, 99, 101 ]

第4次循环 [ 66, 45, 88, 90, 99, 101 ]

第5次循环 [ 45, 66, 88, 90, 99, 101 ]

*/

let len = arr.length;

if (!len) {

return [];

}

console.log(原始数组:, arr);

//外循环,对被排序的数组进行遍历,轮数为数组的长度

for (let i = 0; i < len - 1; i++) {

// 内循环,循环比较相邻元素

for (let j = 0; j < len - 1 - i; j++) {

//倘若前一个元素大于后一个元素的话,就交换两个元素的位置,最后是以从大到小的次序输出

if (arr[j] > arr[j + 1]) {

[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; //元素交换

}

}

console.log(`第${i+1}次循环`, arr);

}

return arr;

}

优化

普通冒泡排序的时间繁杂度恒为 O(N2),与输入数组的元素分布无关。

经过增多一个标志位 flag ,若在某轮「内循环」中未执行任何交换操作,则说明数组已然完成排序,直接返回结果就可

优化后的冒泡排序的最差和平均时间繁杂度仍为 O(N2) ;在输入数组 已排序 时,达到 最佳时间繁杂度 (N)

function bubbleSort(arr) {

let len = arr.length;

if (!len) {

return [];

}

console.log(原始数组:, arr);

//外循环,对被排序的数组进行遍历,轮数为数组的长度

for (let i = 0; i < len - 1; i++) {

let flag = false; // 初始化标志位

// 内循环,循环比较相邻元素

for (let j = 0; j < len - 1 - i; j++) {

//倘若前一个元素大于后一个元素的话,就交换两个元素的位置,最后是以从大到小的次序输出

if (arr[j] > arr[j + 1]) {

[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]; //元素交换

flag = true; // 记录交换元素

}

}

if (!flag) break; // 内循环未交换任何元素,则跳出

console.log(`第${i+1}次循环`, arr);

}

return arr;

}

选取排序

思路:依次找到剩余元素的最小值最大值,安置在末尾开头。

/**

* 选取排序

* 依次找到剩余元素的最小值最大值,安置在末尾开头。

* @param {Array} arr

* @returns

*/

function selectionSort(arr) {

let len = arr.length;

let minIndex;

for (let i = 0; i < len - 1; i++) {

minIndex = i;//先假设第1个数字最小

for (let j = i + 1; j < len; j++) {

if (arr[j] < arr[minIndex]) { //寻找最小的数

minIndex = j; //将最小数的索引保留

}

}

[arr[minIndex], arr[i]] = [arr[i], arr[minIndex]]//交换两个元素

}

return arr;

}

插进排序

思路:第1个元素为有序数组,其后的元素经过再这个已有序的数组中找到合适的元素并插进

function insertSort(arr) {

let length = arr.length,

preIndex, current;

for (let i = 1; i < length; i++) {

preIndex = i - 1;

current = arr[i];

// 和已然排序好的序列进行比较,插进到合适的位置

while (preIndex >= 0 && arr[preIndex] > current) {

arr[preIndex + 1] = arr[preIndex];

preIndex--;

}

arr[preIndex + 1] = current;

console.log(`第${i}次循环`, arr);

}

return arr;

}

希尔排序

经过某个增量 gap,将全部序列分给若干组,从后往前进行组内成员的比较和交换,随后逐步缩小增量至 1。希尔排序类似于插进排序,只是一起始向前移动的步数从 1 变成为了 gap

function shellSort(arr) {

let len = arr.length;

// 初始步数

let gap = parseInt(len / 2);

// 逐步缩小步数

while (gap) {

// 从第gap个元素起始遍历

for (let i = gap; i < len; i++) {

// 逐步其和前面其他的构成员进行比较和交换

for (let j = i - gap; j >= 0; j -= gap) {

if (arr[j] > arr[j + gap]) {

[arr[j], arr[j + gap]] = [arr[j + gap], arr[j]];

} else {

break;

}

}

}

gap = parseInt(gap / 2);

}

}

归并排序

递归将数组分为两个序列,有序合并这两个序列。做为一种典型的分而治之思想的算法应用,归并排序的实现由两种办法

自上而下的递归(所有递归的办法能够用迭代重写,因此就有了第2种办法)。自下而上的迭代。

function /**

* 归并排序

*/

mergeSort(arr) {

let len = arr.length;

if (len < 2) {

return arr;

}

let middle = Math.floor(len / 2),

left = arr.slice(0, middle),

right = arr.slice(middle);

console.log(`处理过程:`, arr);

return this.merge(this.mergeSort(left), this.mergeSort(right));

},

/**

* 归并排序辅助办法

*/

function merge(left, right) {

let result = [];

while (left.length && right.length) {

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;

}

快速排序

快速排序算法是一种基于分治思想的排序算法,其核心思路在于经过选择一个基准值,将待排序数组划分为上下两个子序列,其中左侧序列所有元素均少于基准值,右侧序列所有元素均大于基准值。之后对上下子序列递归进行快排操作,最后全部序列排好序。

以下是运用 TypeScript 实现的快速排序算法代码:

function quickSort(arr: number[]): number[] {

if (arr.length <= 1) {

return arr;

}

const pivotIndex = Math.floor(arr.length / 2);

const pivot = arr[pivotIndex];

const left = [];

const right = [];

for (let i = 0; i < arr.length; i++) {

if (i === pivotIndex) {

continue;

}

const currentItem = arr[i];

if (currentItem < pivot) {

left.push(currentItem);

} else {

right.push(currentItem);

}

}

return [...quickSort(left), pivot, ...quickSort(right)];

}

堆排序

堆排序算法是一种基于堆数据结构的排序算法,其核心思路在于将待排序数组看做二叉树,经过构建大顶堆或小顶堆来实现排序。针对大顶堆,每一个节点的值均大于或等于它的子节点;针对小顶堆,每一个节点的值均少于或等于它的子节点。排序时,取堆顶元素,将其存储到已排序数组中,并从堆中删除;而后重新调节剩余元素形成新的堆,重复以上操作直至所有元素排序完成。

以下是运用 TypeScript 实现的堆排序算法代码:

function heapSort(arr: number[]): number[] {

const len = arr.length;

// 初始化大顶堆,从第1个非叶子结点起始

for (let i = Math.floor(len / 2) - 1; i >= 0; i--) {

heapify(arr, len, i);

}

// 排序,每次将堆顶元素与未排定部分的最后一个元素交换,并重新构造大顶堆

for (let i = len - 1; i > 0; i--) {

[arr[0], arr[i]] = [arr[i], arr[0]];

heapify(arr, i, 0);

}

return arr;

}

// 堆化函数,将以i为根节点的子树调节为大顶堆

function heapify(arr: number[], len: number, i: number) {

let largest = i; // 最大值默认为根节点

const left = 2 * i + 1; // 左子节点下标

const right = 2 * i + 2; // 右子节点下标

// 倘若左子节点比当前最大值大,则更新最大值

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, len, largest);

}

}

记数排序

记数排序(Counting Sort)是一种非基于比较的排序算法,其时间繁杂度为O(n+k),其中k暗示待排序数组中最大元素与最小元素之差加1。该算法的基本思想是统计每一个元素在待排序数组中显现的次数,而后按照统计结果构建有序序列。

/**

* 计数排序

* @param arr 待排序数组

* @returns 排序后数组

*/

function countingSort(arr: number[]): number[] {

const max = Math.max(...arr);

const count = new Array(max + 1).fill(0);

for (let i = 0; i < arr.length; i++) {

count[arr[i]]++;

}

const res = [];

for (let i = 0; i <= max; i++) {

while (count[i]--) {

res.push(i);

}

}

return res;

}

桶排序

桶排序(Bucket Sort)是一种线性排序算法,它利用了函数的映射关系,将要排序的数据分到有限数量的桶子里,每一个桶子再分别排序。桶排序的时间繁杂度取决于桶的数量和桶内运用的排序算法,一般状况下是O(n+k)。

/**

* 桶排序

* @param arr 待排序数组

* @param bucketSize 桶体积

* @returns 排序后数组

*/

function bucketSort(arr: number[], bucketSize = 5): number[] {

if (arr.length === 0) {

return arr;

}

// 找出最大值和最小值

let min = arr[0];

let max = arr[0];

for (let i = 1; i < arr.length; i++) {

if (arr[i] < min) {

min = arr[i];

} else if (arr[i] > max) {

max = arr[i];

}

}

// 计算桶的数量

const bucketCount = Math.floor((max - min) / bucketSize) + 1;

const buckets: number[][] = [];

for (let i = 0; i < bucketCount; i++) {

buckets[i] = [];

}

// 将元素分配到桶中

for (let i = 0; i < arr.length; i++) {

const index = Math.floor((arr[i] - min) / bucketSize);

buckets[index].push(arr[i]);

}

// 对每一个桶进行排序,并将结果合并

const res = [];

for (let i = 0; i < buckets.length; i++) {

if (buckets[i]) {

const sortedBucket = countingSort(buckets[i]);

for (let j = 0; j < sortedBucket.length; j++) {

res.push(sortedBucket[j]);

}

}

}

return res;

}

基数排序

基数排序(Radix Sort)是一种多关键字排序算法,可用于对数字序列进行排序。基数排序先根据最低有效位(LSB)对元素进行排序,而后依次根据次低有效位、次次低有效位……最高有效位进行排序。该算法的时间繁杂度为O(d*(n+k)),其中d暗示数字位数,k暗示每一个数字可能的取值范围。

/**

* 基数排序

* @param arr 待排序数组

* @returns 排序后数组

*/

function radixSort(arr: number[]): number[] {

const max = Math.max(...arr);

const buckets: number[][] = [];

// 初始化桶

for (let i = 0; i < 10; i++) {

buckets[i] = [];

}

// 计算最大数字的位数

let digitCount = 0;

while (max > 0) {

max = Math.floor(max / 10);

digitCount++;

}

// 按照每一位进行排序

for (let i = 0; i < digitCount; i++) {

for (let j = 0; j < arr.length; j++) {

const num = arr[j];

const digit = Math.floor(num / Math.pow(10, i)) % 10;

buckets[digit].push(num);

}

arr = [];

for (let k = 0; k < buckets.length; k++) {

while (buckets[k].length) {

arr.push(buckets[k].shift()!);

}

}

}

return arr;

}




上一篇:快速排序的JS实现(JavaScript)
下一篇:2017 码云最火热开源项目 TOP 50,你都用过哪些?
回复

使用道具 举报

2952

主题

3万

回帖

9997万

积分

论坛元老

Rank: 8Rank: 8

积分
99979405
发表于 2024-10-14 13:14:43 | 显示全部楼层
论坛外链网  http://www.fok120.com/
回复

使用道具 举报

3049

主题

3万

回帖

9910万

积分

论坛元老

Rank: 8Rank: 8

积分
99109041
发表于 2024-11-7 09:36:27 | 显示全部楼层
你的话语如春风拂面,让我心生暖意。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

站点统计|Archiver|手机版|小黑屋|外链论坛 ( 非经营性网站 )|网站地图

GMT+8, 2024-11-24 20:30 , Processed in 0.132707 second(s), 21 queries .

Powered by Discuz! X3.4

Copyright © 2001-2023, Tencent Cloud.