已经准备秋招一段时间了,因为这个关系也在各种巩固知识,顺便整理一下一些东西。这篇文章就是自己整理了一下各种JS的排序算法,以便自己以后回顾。
冒泡排序
function bubbleSort(arr){
var len = arr.length
for(var i=len-1;i>0;i--){
for(var j=0;j<i;j++){
var temp = 0
if(arr[j]>arr[j+1]){
//如果前一个元素大于后一个元素,则交换位置
var temp = 0
temp = arr[j+1]
arr[j+1] = arr[j]
arr[j] = temp
}
}
}
return arr
} var arr = [1,2,5,4,56,54,33,2,23]
bubbleSort(arr) //[1, 2, 2, 4, 5, 23, 33, 54, 56]
快速排序
function quickSort(arr){
if(arr.length<1){
return arr
}
//选取基数
var pivotIndex = Math.floor(arr.length/2)
var pivot = arr.splice(pivotIndex,1) var left = [] //放置小于基数的数
var right = [] //防止大于基数的数
for(var i=0;i<arr.length;i++){
if(arr[i]>pivot){
right.push(arr[i])
}else{
left.push(arr[i])
}
}
return quickSort(left).concat(pivot,quickSort(right))
} var arr = [1, 2, 3, 4, 5]
quickSort(arr) //[1, 2, 3, 4, 5]
选择排序
将待排序列中最小的值与第一个位置的值交换;
剩下的值中再取最小的值与第二个位置的值交换,以此类推直到所有的顺序都排好。
function selectSort(arr){
var len = arr.length
for(var i=0;i<len-1;i++){
var min = arr[i] //默认先将第i个值列为最小值
var minIndex = i //最小值的下标
for(var j = i+1;j<len;j++){
//从第i个值之后的值开始比较,因为i之前的值已经排好序
if(arr[j]<min){
min = arr[j]
minIndex = j
}
}
//将第i个值与最小值交换位置
arr[minIndex] = arr[i]
arr[i] = min
}
return arr
} var arr = [3,2,13,5,6,7]
selectSort(arr) //[2, 3, 5, 6, 7, 13]
插入排序
从第二个元素开始排序;
待排元素之前的元素已经排好序,将待排元素按照大小插入合适的位置,以此类推。
function insertSort(arr){
var len = arr.length
for(var i=1;i<len;i++){
var now = arr[i]
var j = i-1
while(j>=0 && arr[j]>now){
arr[j+1] = arr[j] //数组后移
j--
}
arr[j+1] = now
}
return arr
} var arr = [1,3,2,5,4]
selectSort(arr) //[1, 2, 3, 4, 5]