经典⾯试题:JS常见的排序算法
1. 冒泡排序
// 冒泡排序
// ⽐较两个相邻的元素,将值⼤的元素交换⾄右端
// N个数字要排序完成,总共进⾏N-1趟排序
function bubbleSort(arr) {
if (arr.length === 0) {
return []
}
for(let i = 0; i < arr.length; i++) {
for(let j = 0; j<arr.length; j++) {
if (arr[j] > arr[j+1]) {
let temp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = temp
}
}
}
return arr
}
2. 选择排序
// 选择排序
/
/ 每⼀次从待排序的数据元素中选出最⼩的⼀个元素,存放在序列的开头,以此类推
// 第⼀次循环⽐较n-1次,第⼆次循环⽐较n-2次,依次类推,最后⼀个元素不需要⽐较,因此共进⾏n- 1次循环,最后⼀次循环⽐较1次。// 因此⼀共⽐较1+2+ ... +(n - 2)+(n - 1)次,求和得n2/2 - n/2 ,忽略系数,取最⾼指数项,该排序的时间复杂度为O(n2)
function selectSort(arr) {
if (arr.length === 0) {
return []
}
let minIndex;
for(let i = 0; i<arr.length-1; i++) {
minIndex = i
for(let j = i+1;j<arr.length;j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j // 记录最⼩的缩影
}
}
// ⽤到的最⼩值与默认的做交换(min 与 mowMin交换, 也就是i与minIndex交换)
let temp = arr[i]
arr[i] = arr[minIndex]
arr[minIndex] = temp
}
return arr
}
3. 插⼊排序
// 插⼊排序
sort函数 js// 设索引i之前的为已排过序的,让arr[i]与之前的数据在⼀个个⽐较
function insertSort(arr) {
if (arr.length === 0) {
return []
}
for (let i = 1; i<arr.length;i++) {
for(let j = 0; j < i ;j++) {
if (arr[j] > arr[i]) {
let temp = arr[j]
arr[j] = arr[i]
arr[i] = temp
}
}
}
return arr
}
4. 快速排序
// 快速排序
// 1. 从数组中选择⼀个元素作为基准点
// 2. 排序数组,所有⽐基准值⼩的元素摆放在左边,⽽⼤于基准值的摆放在右边。每次分割结束以后
基准值会插⼊到中间去。// 3. 最后利⽤递归,将摆放在左边的数组和右边的数组在进⾏⼀次上述的1和2操作。
function quickSort(arr) {
if (arr.length === 0) {
return []
}
let midlen = Math.floor(arr.length / 2) // 取数组长⼀半
let midValue = arr.splice(midlen, 1) // 删除,并取出中间值,相当于抠出中间值
let left = []
let right = []
for(let i = 0; i < arr.length; i++) {
if (arr[i] < midValue) {
left.push(arr[i])
} else {
right.push(arr[i])
}
}
return quickSort(left).concat(midValue, quickSort(right))
}
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198,我们将在24小时内删除。
发表评论