冒泡排序
var sort = function(input){
for(let i=0; i<input.length; i++){
let flag = false
for(let j= 0; j<input.length; j++){
if(input[j]>input[j+1]){
temp = input[j]
input[j] = input[j+1]
input[j+1] = temp
flag = true
}
}
if(!flag){
break;
}
}
return input
}
平均时间复杂度 O(n2)
稳定排序
原地排序
插入排序
var sort = function(input){
for(let i=1; i<input.length; i++){
let value = input[i]
let j = i-1
for(; j>=0; --j){
if(value<input[j]){
input[j+1] = input[j]
}else{
break
}
}
input[j+1] = value
}
return input
}
平均时间复杂度 O(n2)
稳定排序
原地排序
冒泡排序 VS 插入排序
两者时间复杂度和空间复杂度相同
逆序度相同的情况下,需要做相同次数的比较和交换操作,但对于交换操作本身,冒泡排序需要三次:
temp = input[j]
input[j] = input[j+1]
input[j+1] = temp
插入排序只需要一次
input[j+1] = input[j]
归并排序
先分解再合并,合并的过程实际就是合并有序数组的过程
var sort = function(array){
if(array.length <=1 ){
return array
}
const m = Math.floor((array.length-1)/2)
const leftArray = array.slice(0,m+1)
const rightArray = array.slice(m+1,array.length+1)
const left = sort(leftArray)
const right = sort(rightArray)
return merge(left,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 && left.length){
result.push(left.shift())
}
while(right && right.length){
result.push(right.shift())
}
return result
}
平均时间复杂度 O(nlogn)
稳定排序
非原地排序
快速排序
数组中选择一个元素为pivot,然后比较其余元素和pivot,小于放左边,大于放右边,再对左右两边的数组分别执行以上逻辑。
var sort = function(array){
if(array.length <=1 ){
return array
}
let pivot = array[0]
let left =[] , right = []
for(let i=1; i<array.length; i++){
if(array[i]<= pivot){
left.push(array[i])
}else{
right.push(array[i])
}
}
const leftArray = sort(left)
const rightArray = sort(right)
return [...leftArray,pivot,...rightArray]
}
平均时间复杂度 O(nlogn)
不稳定排序
以上这一种实现是非原地排序
网友评论