Js常见排序算法整理

左手的ㄟ右手 2022-10-13 13:59 183阅读 0赞

1、冒泡排序

冒泡排序只会操作相邻的两个数据。

每次冒泡操作都会对相邻的两个元素进行比较，看是否满足大小关系要求。如果不满足就让它俩互换。

一次冒泡会让至少一个元素移动到它应该在的位置，重复 n 次，就完成了 n 个数据的排序工作。

2、归并排序

排序一个数组，我们先把数组从中间分成前后两部分，然后对前后两部分分别排序，再将排好序的两部分合并在一起，这样整个数组就都有序了。

采用的是分治思想。

const mergeSort = (arr) => { 
    	//采用自上而下的递归方法
    	const len = arr.length;
    	if (len < 2) { 
    		return arr;
    	}
    	// length >> 1 和 Math.floor(len / 2) 等价
    	let middle = Math.floor(len / 2),
    		left = arr.slice(0, middle),
    		right = arr.slice(middle); // 拆分为两个子数组
    	return merge(mergeSort(left), mergeSort(right));
    };

3、快速排序

先找到一个基准点（一般指数组的中部【个人习惯取num\[0\]），然后数组被该基准点分为两部分，依次与该基准点数据比较，如果比它小，放左边；反之，放右边。

左右分别用一个空数组去存储比较后的数据。

最后递归执行上述操作，直到数组长度 <= 1;

4、希尔排序

先将整个待排序的记录序列分割成为若干子序列。

分别进行直接插入排序。

待整个序列中的记录基本有序时，再对全体记录进行依次直接插入排序。

5、对比

名称：平均时间复杂度：空间复杂度：稳定性

冒泡 On2 O1 稳定  
归并 Onlogn On 稳定  
快排 Onlogn Ologn 不稳定  
希尔 Onlogn O1 不稳定