前言
大家好,我是梁木由,一个有想头的前端,明天温习到了如何排序,那么给大家来分享下,冒泡排序与疾速排序
冒泡排序
概念
从第一个元素开始,把以后元素与下一个元素进行比拟,元素大的往后排,小的往前排,顺次比拟到最初一个元素,进行替换地位。
实现步骤
- 先遍历一共有多少个数须要跟其它数进行比拟
- 再遍历每个数须要跟其它数比拟多少次
- 如果前一个数小于后一个数,就替换地位
function bubbleSort(arr){
let len = arr.length;
// 遍历多少个数跟其它数进行比拟
for(let i = 0; i < len; i++){
// 再遍历每个数须要跟其它数比拟多少次
for(let j = 0; j < len - i - 1; j++){
// 如过前一个数小于后一个数
if(arr[j+1] < arr[j]){
// 替换地位
[arr[j+1],arr[j]] = [arr[j],arr[j+1]]
}
}
}
return arr
}
// 验证
let arr = [1,44,6,77,3,7,99,12]
console.log(bubbleSort(arr))
// [1, 3, 6, 7, 12, 44, 77, 99]
疾速排序
概念
在数据集之中,找一个基准点,建设两个数组,别离存储右边和左边的数组,利用递归进行下次比拟。
实现步骤
- 先做边界解决
- 定一个左右两侧的数组
- 查找数组两头地位,并获取两头地位这个数值,并在原数组删除它
- 遍历数组,判断以后项与两头地位数值的大小,大的 push 到右侧数组,小的 push 到左侧数组
- 再对两侧数组进行递归,拼接两头数值
function quickSort(arr){
// 解决边界
if(!Array.isArray(arr)) return arr;
if(arr.length <=1) return arr;
// 定义左右两侧的数组
const leftArr = [],
rightArr = [];
// 查找数组两头地位,并获取两头地位这个数值,并在原数组删除它
const midValue = arr.splice(Math.ceil(arr.length/2),1)[0];
// 遍历数组,判断以后项与两头地位数值的大小,大的 push 到右侧数组,小的 push 到左侧数组
for(let i = 0; i < arr.length; i++){if(arr[i] > midValue){rightArr.push(arr[i])
}else{leftArr.push(arr[i])
}
}
// 再对两侧数组进行递归,拼接两头数值
return [...quickSort(leftArr), midValue,...quickSort(rightArr)]
}
// 验证
let arr = [1,44,6,77,3,7,99,12]
console.log(quickSort(arr))// [1, 3, 6, 7, 12, 44, 77, 99]