冒泡排序

:两个指针循环，遇到不合适就交换，直到将符合要求的浮到边界

function bubbleSort(list){
	for(let i=0;i<list.length;i++){
		for(let j=0;j<list.length-i-1;j++){
			if(list[j]>list[j+1]){
				let tmp=list[j]
				list[j]=list[j+1]
				list[j+1]=tmp
			}
		}
	}
}

快速排序

function swap(list , i ,j){
	let tmp=list[i]
	list[i]=list[j]
	list[j]=tmp
}
// function partition(list,left,right){
//     let index=left+1
//     let piovt=list[left]
//     for(let i=index;i<=right;i++){
//         if(list[i]<piovt){
//             swap(list,index++,i)
//         }
//     }
//     swap(list,left,index-1)
//     return index-1
// }

function partition(list,left,right){
	let pivot=list[left]
	while(left<right){
		while(left<right&&list[right]>pivot){
			right--
		}
		list[left]=list[right]
		while(left<right&&list[left]<=pivot){
			left++
		}
		list[right]=list[left]
	}
	list[left]=pivot
	return left
}
function quickSort(list,left,right){
	if(left<right){
		let pivot=partition(list,left,right)
		quickSort(list,left,pivot-1)
		quickSort(list,pivot+1,right)
	}
}

选择排序

function selectSort(list){
	for(let i=0;i<list.length;i++){
		let min=i
		for(let j=i+1;j<list.length;j++){
			if(list[min]>list[j]){
				min=j
			}
		}
		let tmp=list[i]
		list[i]=list[min]
		list[min]=tmp
	}
}

插入排序

function insertSort(list){
	for(let i=1;i<list.length;i++){
		let key=list[i]
		let j
		for(j=i-1;(j>=0)&&(key>list[j]);j--){
			list[j+1]=list[j]
		}
		list[j+1]=key
	}
}

希尔排序

function shellSort(list){
	let gap=1
	while(gap<list.length/3){
		gap=gap*3+1
	}
	for(gap;gap>0;gap=Math.trunc(gap/3)){
		for(let i=gap;i<list.length;i+=1){
			let key=list[i],j
			for(j=i-gap;list[j]>list[j+gap];j-=gap){
				list[j+gap]=list[j]
			}
			list[j+gap]=key
		}
	}
}

归并排序

function merge(left,right){
	let res=[]
	while(left.length&&right.length){
		if(left[0]<right[0]){
			res.push(left.shift())
		}else{
			res.push(right.shift())
		}
	}
	while(left.length){
		res.push(left.shift())
	}
	while(right.length){
		res.push(right.shift())
	}
	return res
}
function mergeSort(list){
	if(list.length<2){
		return list
	}
	let mid=Math.trunc(list.length/2)
	return merge(mergeSort(list.slice(0,mid)),mergeSort(list.slice(mid)))
}

堆排序

//完全二叉树，第一个非叶子节点index=n/2-1
//父节点index=(n-1)/2
//子节点index=n2+1 n2+2

function heapfy(list,i,len){
	let left=i*2+1
	let right=i*2+2
	let largest=i
	if(left<len&&list[left]>list[largest]){
		largest=left
	}
	if(right<len&&list[right]>list[largest]){
		largest=right
	}
	if(i!=largest){
		swap(list,largest,i)
		heapfy(list,largest,len)
	}
}
function heapSort(list){
	for(let i=Math.trunc((list.length-1)/2);i>=0;i--){
		heapfy(list,i,list.length)
	}
	for(let i=list.length-1;i>0;i--){
		swap(list,0,i)
		heapfy(list,0,i)
	}
	return list
}